Depois de ver um vídeo sobre um problemão como esse, não esqueçam de garantir o desconto de vocês no Cambly junto da aula grátis! :D -> PEDRO50OFF l bit.ly/3lB4Gwh
Já que são infinitas possibilidades, Não poderíamos implementar uma constate? Aplicando uma infinidade de resultados... Pode demorar bastante tempo mas poderíamos Tentar obter um possível resultado para essa pergunta. Ou encontrar um LOG final de um resultado constante ou nulo. Aplicando alguns modelos de fórmulas de ( *********) EM QUESTÃO DO LOG: Se tivermos um número finito de logaritmo poderíamos implementar umas leis temática tentando facilitar o resultado ou retirar modelos e implementar umas técnicas de cálculos Ou seja poderíamos retirar números e ao mesmo tempo ter a mesma Q_ EM NÚMERO MAS (-) O NÚMERO TOTAL
Eu tenho PAVOR de matemática, mas to aqui assistindo a esse vídeo somente pq o Pedro é um cara que se precisar explicar o funcionamento de uma makita pra um yorkshire, o cachorro entende (não que eu seja um yorkshire)
Uma pequena correção: NP não vem de não-polinomial mas sim de não-determinístico polinomial, pois para essa classe de problemas, algoritmos polinomiais existem, porém através de uma máquina de turing não deterministica.
@@ducasiqueira7554 também não se sabe de NP completo é diferente ou igual a P. O que tem especial na classe NP completo é que se um problema dela (o SAT por exemplo) for resolvido em tempo polinomial isso significa diretamente que P=NP.
@@rcrc1855 Eu também, Rc Rc! kkkk Zoeiras à parte, os Comentários de Zailton et Alli enriqueceram o vídeo! Parabéns! Além disso, os 5050 de 4:06 me relembrou uma famosa história ((( ? ))) do Príncipe da Matemática C. F. Gauss quando seu Professor pediu que as Crianças somassem os números de 1 a 100! Só que a solução daquele Menino de 7 anos veio de 50 x a Soma dos Números das "Pontas", digamos assim, que é sempre 101! (((1+100 = 101; 2+99 = 101; 3+98...))) Um GÊNIO!
Como estudante de Engenharia da Computação digo que vc explicou o conceito base de complexidade de algoritmo muito melhor do que muito profissional da área.
Pedro, meus parabéns pelo trabalho que já acompanho há anos! Sou mestrando em Ciência da Computação e trabalho na área de inteligência computacional e otimização, que busca resolver os problemas NP de forma rápida por aproximação com utilização de heurísticas. Adorei o vídeo! Espero que fale mais sobre essa área que tanto amo!
Há um tempo atrás ele falou de turbulência e citou esse instituto, me fez pesquisar e agr tá falando direto dele kkkkkkkk Além disso, a BBC tem um vídeo falando da hipótese de Riemann para a função zeta dos números primos (se solucionada acaba com a criptografia mundial) Esses são os 3 que eu sei alguma coisa kkkkkk
Acho difícil nós (um público leigo em grande parte) conseguir entender o enunciado de todos eles mesmo sendo o Ciência Todo Dia explicando, pq vários necessitam de um puta conhecimento de muita matemática acumulada de séculos até demonstrações recentes de teoremas
Excelente vídeo! Apenas um adendo. NP não significa Não Polinomial, mas sim, Polinomial Não determinístico (Non-deterministic polynomial time) e P é portanto uma subclasse de NP. NP são os problemas cujas soluções são verificáveis em tempo polinomial, por exemplo ordenar um vetor (que também é de P) ou o problema do vendedor viajante (que é de NP, mas n se sabe se é de P).
Pedro vc é realmente muito didático cara, esta de parabéns, nunca vi uma explicação tao simples sobre complexidade de tempo de algoritmos, poderia fazer mais alguns videos explicando todas as outras formas de complexidade de espaços e tempo! principalmente a parte logarítmica!
Acho que pra achar os caminhos mais curtos mais rápido, é so traçar uma linha reta entre dois pontos e adequa-la ao caminho mais próximo de sua tragetória
Faz um vídeo a respeito da hipótese de Riemann que também é um dos problemas de um milhão de dólares.É um assunto muito interessante com relação aos números primos. A resolução desse problema implica em grandes mudanças no sistema de criptografia e segurança do mundo todo.
@@tiorayquaza5210 ele gritou 3 pelo simples fato de que, exclamação (!) Sgnifica um ato de "exclamação" algo que chame a atenção do leitor. Fazendo uma piada com o "3!" Que é usado na matemática.
@@SazonTd se viajou cara, modalidade de frase com curva melódica própria, ger. iniciada por que, quanto etc., expressando algum sentimento do falante diante de algo (p.ex.: que dia lindo! ).
Excelente a sua didática. Na Engenharia de Produção lidamos com problemas NP dentro de Pesquisa Operacional. Para definir a sequência de Produção de produtos em um parque de máquinas, fatorial semelhante ao problema do caixeiro que você cita, podemos usar algumas heurísticas que vêm sendo melhoradas há décadas. Realmente um desafio e tanto.
Eu sou de Ciência da Computação, vou começar minha terceira iniciação científica. A primeira foi com strip packing e a segunda foi com o problema do escalonamento com minimização do makespan.
Pedro, faz um vídeo sobre as catedrais goticas explicando como essa arquitetura funciona, como chegaram na ideia de fazer essas catedrais naquela epoca e como funciona a distribuição de peso em construções e a ciencia por trás
@@HqBlays Olha, eu realmente acredito que exista muita ciência e matemática por trás dessas construções magníficas e complexas. Foi necessário o uso da física para conseguir manter o equilíbrio da estrutura, da matemática para a aplicação da profundidade nos desenhos de planejamento, etc. A princípio, eu aprendi um pouco sobre toda a complexidade dessas estrutura em aulas de literatura sobre o renascentismo (◠‿◕)
@@isatasmath6135 Ok ok gente calma não percisam me bombardear de argumentos bem colocados o que eu quis dizer é que esses assuntos não são muito do tipo de assunto que o ciencia todo dia trata e a maioria do publico não tem interesse essa piada q eu fiz do "historia todo dia" foi so uma piada sem realismo eu sei que arquitetura engenharia e praticamente tudo que existe neste mundo pode ser explicado pela fisica ou matematica mas é so uma piada não percisam estressar
Muito bom o vídeo, porém uma curiosidade, o significado real de NP é "não-deterministico polinomial". Você pode ler mais sobre no livro Algorithm Design do Jon Kleinberg e Eva Tardos.
vim aqui pra falar isso. mas essa simplificação é muito comum né. até pq a definição em si tem a ver com a máquina de turing e não é tod mundo que conhece isso
3 года назад+6
Tem um outro ponto também é que 'P' se refere a complexidade para *resolver* um problema e 'NP' se refere a complexidade para *checar* a solução do problema. Por exemplo, ordenar uma lista de números é resolvido com complexidade N*log(N) (como o Pedro disse). Checar que uma lista está ordenada, pode ser feito com complexidade N (basta percorrer a lista uma vez vendo se os números estão crescendo). Mas eu acho que esse assunto é complicado de explicar mesmo. Tenho dezenas de colegas que estudaram computação comigo e tenho certeza que mais de 90% deles se perderia neste assunto. Parabéns, Pedro! O vídeo ficou show de bola!
@ NP também se refere a complexidade para resolver, mas em uma máquina de turing *não determinística* (por isso o N em NP). Dizer que NP se refere ao tempo necessário para verificar uma solução é só uma forma equivalente de definir a classe NP, mas ambas estão corretas.
Sua explicação foi mais fácil do que a que tive na faculdade, em estrutura de dados II. Como sempre, mandando bem demais. Um abraço pra você e pro Greg. Amo o trabalho de vocês!
1:20 Bublle sort , estudei isso na faculdade de Sistemas, uma das exigências em uma das provas a minha Prof de Lógica de programação pediu para que reescrevessemos o código de ordenação (que resumindo, são dois loops um dentro do outro) e essa pergunta já encontrei diversas vezes em outros lugares como testes para trabalhar na Àrea, mas o mais curioso é que isso não serve para resolver a maioria dos problemas no dia a dia do Desenvolvedor, que na maioria das vezes, se vê obrigado a usar a Lógica dos outros, como arquitetura, o que leva tempo e torna mais caro o processo de desenvolvimento de APPS e Sites. Cada passo além na ciencia da computação custa caro, e o mercado não quer saber de criar nada, mas sim obter lucro e gastar menos com TI
Caraca Pedro, seus vídeos são praticamente motivacionais, o jeito que você explica faz parecer que qualquer parte da matemática é simples, obrigado mais uma vez.
Que simplicidade enorme ao clarificar um assunto senão o assunto de maior relevância para a computação. Brilhante. Como engenheiro da computação vejo isso está ao alcance de todos. Assim se faz ciência.
O teor didático para entendimento do problema ficou muito bom, parabéns! Só um adendo: indo ao conceito da questão, P trata-se da classe de solução de problemas em tempo polinomial, enquanto a classe NP são problemas que podem ser verificados/checados em tempo polinomial. Portanto, não é exatamente correto colocar que P está dentro de NP por ter um problema fácil tornado difícil, mas porque se segue que se podemos solucionar um problema em tempo polinomial, ele também pode ser verificado em tempo polinomial. Abraço!
Por muito tempo eu também achei que NP era de "não polinomial", mas na verdade NP vem de "nondeterministic polynomial". Você pode pensar em NP como os problemas que possuem um certificado de solução verificável em tempo polinomial por exemplo se queremos saber se o problema do caixeiro viajante tem solução
Lembro que nos idos de 1999, meu primeiro estágio como programador em uma startup de logística, era mexer com o problema do caixeiro viajante (em Java). Lembro que na época, quando o Google não calculava rotas ainda, o que havia de mais interessante era o Djikstra 2 Pilhas.
Acho que são problemas diferentes hein. No caixeiro viajante você tem que sair de uma cidade, passar por todas as cidades e voltar para a cidade inicial, já o Djikstra é para o problema de Caminho de Custo Mínimo. Nesse você tem que sair de uma cidade e ir para outra, mas escolhendo uma sequência de cidades em que custo total vai ser mínimo, não precisa passar por todas.
Estudo programação e confesso que antes de ter contato com algoritmos, eu odiava matemática e sempre me perguntava: "pra quê vou aprender essas fórmulas na escola? serve pra nada". Hoje eu digo pra mim mesmo que matemática, cálculos e etc estão em todo lugar, e quanto mais aprendemos sobre elas, mais facilitamos nossas vidas. Fico maravilhado vendo programas rodando com fórmulas feitas a séculos atrás e funcionando super bem ♥️
3 года назад+8
Tá estudando programação? Já vai aprendendo a resolver esse problema pra ficar milhonário. function showDoMilhao(float p,float np) { return p == np; }
Mais um dia de vida sem eu usar o teorema de Pitágoras ou as milhões de fórmulas da escola... É importante só pra quem usa, totalmente dispensável fora da escola
@@Freedom182 Sou professor de matemática, realmente concordo que o currículo pode ser enxugado. Mas a questão da utilidade é muito complexa. A matemática "inutil" tem a utilidade de desenvolver seu raciocínio lógico, mesmo que não venha a utilizar várias das fórmulas ensinadas, conseguir aprendê-las é um exercício de perceber padrões e isso certamente nós usamos o tempo todo.
3 года назад+12
@@Freedom182 o colégio não te ensinou isso, o colégio te ensinou a fazer funções e te deu como exemplo aplicar em matemática básica. Você pode exercitar o teorema citado, por exemplo, para calcular a base da sua conta de energia ou água, para reduzir suas contas, ou otimizar o espaço na sua casa organizando seus móveis, ou calculando uma razão de ataque para sua pirâmide alimentar, se você só sabe usar uma parafusadeira multiúsos só para aparafusar e desaparafusar não culpe o manual ou a fabricante
@@Freedom182 Por favor, continue assim! Dessa forma o mercado fica menos competitivo e mais fácil pra aqueles poucos que não desprezam as exatas. Eu realmente agradeço muito existirem manés como você pois se todo mundo enxergasse o poder das exatas eu não teria construído minha empresa (por excesso de competição) em cima de conhecimentos de física e matemática e hoje não estaria vivendo uma vida de luxo. Muito obrigado mesmo!
Nesse algoritmo de buscar do menor que você descreveu faz n-1 comparações. Quando o algoritmo é inciado o primeiro elemento é sempre tomado como o menor e adiciona na variável, só a partir do segundo que irá ocorrer as comparações.
Publiquei um livro sobre o assunto e outros relacionados em 2017. Há diversos mitos a esse respeito. Esse vídeo dá uma ideia geral, mas a definição do problema envolve necessariamente máquinas de Turing.
Sua explicação da organização de uma lista de números em ordem crescente foi excelente! É dessa maneira que se faz um código, a não ser que você apele pra comandos já prontos que certas linguagens oferecem
Me formei em Ciência da Computação, tive varias aulas falando sobre isso, achei maravilhosa a forma com que você explicou esse conceito, me lembrando da aula de complexidade de algoritmo kkkk
Só tem que tomar cuidado na hora de calcular pra não acontecer estouro de pilha, ou falando tecnicamente na informática "buffer overflow" excedendo a quantidade de memória disponível com a quantidade de números a serem calculados.
Olha, é meio tarde pra isso, pois normalmente ninguém observa comentários recentes em videos "antigos", no caso, não acabados de lançar mas... minha ideia é, se há problemas que são muito complexos para ter computacionalmente falando uma resolução simples, então o passo seria criar uma via direta com o análise de todos os dados obtidos e chutar algo lógico dentro do que se compreende. np=p somente quando p=x ; np=y e np+p=z
um exemplo prático seria que ao invés de analisar qual a melhor rota para visitar todas as cidades capitais dentro de todos os dados, é vendo qual dado faz mais sentido com outros recopilados e tomar uma decisão lógica não aferrada na total certeza, inclusive isso foi já feito outras vezes antes o problema seria aplicar isso computacionalmente, mas infelizmente não possuo o conhecimento necessário nessa área para expressar como aplicar alí
Pequena correção: NP não é o conjunto de problemas não polinomiais, mas dos problemas polinomiais em maquina de turing não-deterministicas. Há problemas mais dificeis que NP. Fonte: en.wikipedia.org/wiki/NP_(complexity) "In computational complexity theory, NP (nondeterministic polynomial time) "
8:15 As soluções pra esses problemas são algoritmos de otimização combinatória. Algoritmo genético, otimização por colônia de formigas, têmpera simulada. Mas eles não garantem o ótimo global
Parabéns pelo vídeo Pedro e a equipe do Ciência Todo Dia. Falem mais sobre Matemática, como por exemplo da Medalha Fields, Prêmio Abel, descoberta ou criação, principalmente pra dismestificar essa coisa de que a Matemática já está "acabada" (já fizeram td q tinham pra fzr) mostrando assim, q os avanços nela levam a avanços em Física, Química, Ciência da Computação, Economia, Biologia (surpreendentemente a princípio), etc, seja de modo imediato ou levando séculos para tais conceitos serem introduzidos no mundo "real", atuando assim como uma verdadeira maestra no desenvolvimento humano.
Pedrinho me ajudando a sintetizar uma resposta simples para uma prova que abrange as classes de solucionabilidade de problemas, desde já, muito obrigado!
Curso ciência da computação e amei esse vídeo, fiquei me perguntando se tem outros vídeos relacionados ao tema de computação no canal. Acho que seria muito interessante se tivesse divisão por temas na aba de playlists do canal, por exemplo, uma playlist com vídeos que abrangem algo do mundo da computação, enfim, só uma sugestão :)
A resposta está na pergunta: se "P" significa "Polinomial" e "NP" significa "Não-Polinomial", então NP NÃO é igual a P. Se fosse, seria SP (Sim-Polinomial). Onde pego o prêmio?
Se eu conseguisse provar p = non deterministic polinomial, eu jamais viria a publico entregar uma tecnologia tão fantástica por tão pouco. 1 milhão é o que você conseguiria ganhar por semana prestando serviços de otimização linear e otimização de rotas para companhias aéreas.
Para a pessoa ganhar o premio ela não precisa resolver o problema do caixeiro viajante. O contrário também vale, resolver o problema do caixeiro viajante não te garantirá o premio, por mais valioso que seja a solução.
Pensei em uma sugestão de início, no problema do valor mínimo notar que Soma_n = Mín + .... + Máx Máx = Soma_n - ... - Mín => Máx < Soma_n, se Mín > 0, portanto para achar o menor valor é possível fazer uma recursão fazendo apenas (Soma/kn) comparações de bits, isso faz que seja descartados em potências de 2, e ir diminuindo k até 1, pelo menos a solução para a maioria dos casos seria de complexidade < O(n). Teria que apertar o passo de diminuicao de k em log(n) pra manter o pior caso estável abaixo de O(np). Aí vale a continuação do raciocínio. Muito bom o vídeo. A inspiração que tive foi se pensarmos como nós humanos acharíamos a menor bola, nós simplesmente tiramos a média mental dos tamanhos e vamos comparando com as que são menores, com certeza o raciocínio humano é de ordem O(k) e não O(np). Para achar uma blusa preta no meio de 1 milhão de brancas, nós iríamos direto na preta, porque simplesmente dividimos exponencialmente nosso campo de visão (k) e descartamos rapidamente os conjuntos que não parecem na média.
Na realidade, NP significa “Nondeterministic Polinomial”, e não “não-polinomial”. Ou seja, problemas desse tipo são polinomiais em uma máquina não-determinístico. Muito bom o vídeo e parabéns pela explicação!
sobre o crescimento de proteinas é outra coisa facil de resolver: se a proteina tem um determinado padrão de organização de moleculas posso automatizar o processo e atraves de outras proteinas posso usar a IA pra construir uma outra proteina com base estatistica de proteinas reais.
Uma curiosidade interessante: encontrar um algoritmo polinomial para o problema do cacheiro viajante é suficiente para demonstrar que P = NP, já que esse problema faz parte de uma sub-classe de problemas chamado "NP-difícil".
Mano, nunca vi alguém explicar melhor que o Pedro, queria que ele fosse meu professor de Física e Matemática! Aliás eu me inspiro em vc Pedro e também no Albert Einstein
Trabalho com geração clusters de alvos por coordenada. Algumas soluções já foram tentadas em python, mas todas voltam para a análise combinatória, que tem por consequência o tempo em demasia. Estou nessa empreitada, mas realmente em tudo que se pensa, se volta para esse mesmo ponto de partida.
Na faculdade resolvia alguns problemas como o do Caixeiro Viajante, dentre outros parecidos, utilizando alguns algoritmos, como Busca A* e Algoritmo de Dijkstra. Quando falamos em rotas sem nenhum parâmetro de definição realmente criamos um mundo de possibilidades(conforme citado no vídeo). Porém, quando definimos custos para as rotas, ou parâmetros a serem priorizados, esses algoritmos funcionam bem, diminuindo significativamente o tempo que esse algoritmo resolve o problema. Os custos que serão os parâmetros de escolha podem ser baseados em alguns aspectos: Distancia territorial, tipo de terreno, dentre outros pontos que mudariam de problema para problema. Sendo assim, seleção de melhores rotas e decisões de pontos já são bem executadas, um exemplo micro seria a própria rota selecionada pelo nosso GPS. Acredito que problemas mais complexos, como os citados após foram realmente melhores para representar o quão impactante seriam os avanços com a solução desse problema. Especialistas me corrijam se falei alguma bobagem. Qualidade do vídeo incrível, como sempre! 3!!!
Já resolvi, P desigual a NP. Pelo fato de algumas partes de alguns problemas não terem ligação com outras, então cada parte deve ser resolvida separadamente, é tudo aquilo que fica entre parênteses nas fórmulas ou quando vc vai resolver por exemplo um problema em duas dimensões como a regra de três, ou quando vc deve somar uma dimensão obter o resultado total para depois trabalhar com este resultado. Havia ou há nas calculadoras o M+, M- e MR, se não me engado, onde vc poderia resolver somas e depois somar ou diminuir o resultado utilizando M+ ou M-, mas isso não quer dizer que vc pode deixar de resolver os cálculos em todas as suas dimensões.
@@wakamekat3805 se eu trabalhar com manicure e pedicure eu com certeza não vou usar, mas se eu quiser uma profissão que tem relação com exatas, aí eu vou usar, mas independente disso, conhecimento é conhecimento
@@kelvinmargotti325 sim sim, aprendi durante 12 anos da minha vida equações que nunca usei e hj não lembro de nada, enquanto em países desenvolvidos eu poderia estar aprendendo sobre econômia e as matérias que eu quisesse
Comecei a ler o Algoritmos hj, a tarde estava estudando sobre ordenação de números e esse lance de como o algoritmo escala de acordo com o n aí tu lança esse vídeo HOJE! QUE TIMING OBRIGADO, Pedro
Existe também outro problema que é parecido com esse do caixeiro viajante em termos de complexidade, chamado torre de Hanoi(é aquele que você tem 3 Torres com vários anéis e tem que tirar todos os anéis de uma torre e colocar em outra, sendo que um anel maior não pode ficar sobre um anel menor). Pra se ter uma noção, o número de movimentos necessários é obtido pela fórmula 2^n - 1. Se você tiver mil discos, o número de movimentos necessários é 1,07 elevado a 301 !!!. Fiz um teste em minha máquina e com 55 discos o código levou ± 4 horas, com 3,6 elevado a 16 movimentos. E não existe outra forma de resolver(mesmo) afinal essa é a forma mais rápida (pelo menos usando 3 Torres).
Existe sim algum algoritmo pra fazer algum tipo de atalho pois a velocidade da luz " atalha " o tempo e o tempo não é palpável fisicamente porém é " atravessavel" digamos assim assim também um cálculo pode sim atravessar muitas possibilidades
A resposta esta na relação entre a superficie externa e a area interna de diferentes coordenadas de dimensões, por exemplo um circulo para uma esfera,dps hiper esfera.vc ira perceber q o y de x*y vai aparecer c a soma dele, por exemplo,num circulo tera a area e circunferencia,numa esfera sera a circunferência, area e volume,numa hyperesfere seria circunferência, area,volume e algo a mais
Nossa o vídeo ficou muito bom e extremamente didático! Parabéns! Só uma correção: NP não vem de "não polinomial", mas sim de "nondeterministic polinomial time" (tempo polinomial não deterministico). Até porque a pergunta P=NP está interessada exatamente em saber se os problemas NP são, ou não, resolviveis em tempo polinomial hahaha. O termo NP é um pouco mais chatinho de se definir, mas resumidamente: "são os problemas para os quais as instâncias possuem um certificado pequeno de resposta (pode ou não ser a própria resposta) que pode ser usado para validar a solução em si em tempo polinomial" Ou seja, para um problema ser NP existe um algoritmo que resolve suas instâncias em tempo polinomial se você der um pouco de informação extra para ele, meio que o algoritmo "rouba" já que ele tem mais informações. Por exemplo: para o caixeiro viajante um certificado pequeno pode ser a própria rota (ordem em que você visita as cidades).
sou universitario da FATEC e estou fazendo o curso de DSM (Desenvolvimento de Solftware Multiplataforma) e meu professor passou um trabalho sobre complexidade de algoritmo e colocou seu video de referencia
Deixa eu ver se eu entendi, se eu encontrar esse novo algorismo ganho 1M, que podem ser descryptografados com o algorismo que encontrei. Ou seja eu posso quebrar algum outro algorismo usando esse novo e ganhar muito mais do que 1M
Bom o ciencia todo dia è de fato algo no qual quem tem curiosidade, ficar mais curiosidade ainda para aprender, devido a uma explicação bacana de se ouvir, onrigado mano pedro.
O vídeo tem uma informação errada, NP não significa "não polinomial" e sim um conceito mais complexo. Se NP fosse não polinomial o problema estaria resolvido não é verdade. Essa é uma confusão comum. Fora isso o vídeo é legal.
Se um dia alcançamos esse algoritmo, daria para avançar bem no xadrez também, e seria impossível uma pessoa ganhar no xadrez de uma máquina que use esse algoritmo, e em compensação, a máquina nos ensinaria muito
São vídeos seus que me fazem entender melhor matemática e a ciência de uma forma interessante e me faz gostar e muito disso,muito obrigado,Pedro❤(e pode deixar que se eu achar o resultado com provas,eu divido o dinheiro👀)
Em 4:10, aprendemos sobre o número de passos necessários para quantidade de números. Mas oq não entra na minha cabeça, é que o fato comparação, não se trataria do todo, porque comparativamente, se eu tivesse 100 números, e fosse colocá-los de forma decrescente, eu não precisaria comparar nenhum número com todos os demais pra saber que ali seria seu lugar, apenas o antecessor, exemplo, se estou no número 87, eu não preciso comparar o 86 com todos os outros 85 números para saber qual o próximo, precisaria apenas comparar com o antecessor "86", logo, não precisei de 85 comparações pra saber o lugar seu devido lugar, só precisaria de uma comparação, o número antecessor, então se ele fosse menor que 87, e o valor é 86, com apenas 1 comparação, e não 85, eu achei seu devido lugar. Faz sentido ????
@@mikebezerra3188 na verdade, dá pra fazer um bocado de coisa sim. Afinal, é o dinheiro de toda uma vida pra maioria dos brasileiros, mas não é como se vc fosse um Mark Zukerberg ou até mesmo um Gugu da vida, então invista esse dinheiro com consciência...
Depois de ver um vídeo sobre um problemão como esse, não esqueçam de garantir o desconto de vocês no Cambly junto da aula grátis! :D -> PEDRO50OFF l bit.ly/3lB4Gwh
compreensivel tenha um otimo dia
👁️🍿
Qual a diferença de um motor ciclo diesel para um motor flex ?
FAZ UM VÍDEO SOBRE COMBUSTÍVEIS
Pedro, por favor, faça uma playlist com os vídeos referentes aos Problemas do Milênio do Instituto Clay.
Já que são infinitas possibilidades, Não poderíamos implementar uma constate? Aplicando uma infinidade de resultados... Pode demorar bastante tempo mas poderíamos Tentar obter um possível resultado para essa pergunta. Ou encontrar um LOG final de um resultado constante ou nulo.
Aplicando alguns modelos de fórmulas de ( *********)
EM QUESTÃO DO LOG: Se tivermos um número finito de logaritmo poderíamos implementar umas leis temática tentando facilitar o resultado ou retirar modelos e implementar umas técnicas de cálculos
Ou seja poderíamos retirar números e ao mesmo tempo ter a mesma Q_ EM NÚMERO
MAS (-) O NÚMERO TOTAL
Eu tenho PAVOR de matemática, mas to aqui assistindo a esse vídeo somente pq o Pedro é um cara que se precisar explicar o funcionamento de uma makita pra um yorkshire, o cachorro entende (não que eu seja um yorkshire)
Fds?
@@ElaraArale Faustão de saia
Como vou saber se você realmente não é um Yorkshire?!
Vai jogar teu minecraft vai
Boa kkkkkkk
Uma pequena correção: NP não vem de não-polinomial mas sim de não-determinístico polinomial, pois para essa classe de problemas, algoritmos polinomiais existem, porém através de uma máquina de turing não deterministica.
Também é preciso dizer que P pertence a NP, porém existe o conjunto NP-Completo que também pertence a NP e é diferente de P.
@@ducasiqueira7554 também não se sabe de NP completo é diferente ou igual a P.
O que tem especial na classe NP completo é que se um problema dela (o SAT por exemplo) for resolvido em tempo polinomial isso significa diretamente que P=NP.
Ahh, por isso que eu nao tinha entendido nada.
@@rcrc1855 Eu também, Rc Rc! kkkk Zoeiras à parte, os Comentários de Zailton et Alli enriqueceram o vídeo! Parabéns! Além disso, os 5050 de 4:06 me relembrou uma famosa história ((( ? ))) do Príncipe da Matemática C. F. Gauss quando seu Professor pediu que as Crianças somassem os números de 1 a 100! Só que a solução daquele Menino de 7 anos veio de 50 x a Soma dos Números das "Pontas", digamos assim, que é sempre 101! (((1+100 = 101; 2+99 = 101; 3+98...))) Um GÊNIO!
Só nerd
Sou professor de Engenharia da Computação. Fantástica sua explicação! Parabéns!
Muito obrigado! :D
Me diz a resposta ai pra eu ganhar 1 milhão de reais
professor, se vc colocar isso na prova. os seus alunos vão chorar
p = np
p - np = 0
p(1-n) = 0
p = 0 ou n = 1
Logo: np = p
KD meu 1 milhão de dólares???
Professor ensine seus alunos a criar o algorítimo do Solver (PL), vão te odiar, mas daqui a 2 anos vão te amar
Como estudante de Engenharia da Computação digo que vc explicou o conceito base de complexidade de algoritmo muito melhor do que muito profissional da área.
Eles falam sobre coisas nesse nível na faculdade? Eu não esperava tanto, bem interessante.
A moça que escreveu o roteiro é da área kkkkkkkk.
Pedro, podia virar uma série isso né? De fazer vídeos sobre problemas da matemática em aberto.
Já estamos trabalhando nisso 👀
@@CienciaTodoDia poderia começar com as bases e evoluir para programação linear e depois grafos
@ um curso de teoria da computação básica então?
Não só de matemática
Tenho quase certeza que o problema da Torre de Hanói entraria nessa série.
Pedro, meus parabéns pelo trabalho que já acompanho há anos!
Sou mestrando em Ciência da Computação e trabalho na área de inteligência computacional e otimização, que busca resolver os problemas NP de forma rápida por aproximação com utilização de heurísticas. Adorei o vídeo! Espero que fale mais sobre essa área que tanto amo!
3! Com o grito foi bom demais! Kkkkk melhorando suas piadas!
uai... quando eu aprendi fatorial o professor fez a mesma piada rsrs
Sempre foi assim que eu lia mentalmente os exercícios que tinham fatorial
essa me pegou bonito
Eu tava comendo e quase cuspi a comida quando ele fez isso kkkkkkkkkkkk
Concordo
Excelente video!! Uma correcao que é importantissima, NP é "Não deterministico polinomial", e não "não-polinomial". Isso faz muita diferença! Rsrs
Pedro, por favor, faça uma playlist com os vídeos referentes aos Problemas do Milênio do Instituto Clay.
o Brasil deveria está incluído nessa lista [Hu3 Br politizando tudo kkkk]
Há um tempo atrás ele falou de turbulência e citou esse instituto, me fez pesquisar e agr tá falando direto dele kkkkkkkk
Além disso, a BBC tem um vídeo falando da hipótese de Riemann para a função zeta dos números primos (se solucionada acaba com a criptografia mundial)
Esses são os 3 que eu sei alguma coisa kkkkkk
@@fegobe mais um é a conjectura de Poincaré que é o único resolvido até agr
Acho difícil nós (um público leigo em grande parte) conseguir entender o enunciado de todos eles mesmo sendo o Ciência Todo Dia explicando, pq vários necessitam de um puta conhecimento de muita matemática acumulada de séculos até demonstrações recentes de teoremas
seria foda
Excelente vídeo! Apenas um adendo. NP não significa Não Polinomial, mas sim, Polinomial Não determinístico (Non-deterministic polynomial time) e P é portanto uma subclasse de NP. NP são os problemas cujas soluções são verificáveis em tempo polinomial, por exemplo ordenar um vetor (que também é de P) ou o problema do vendedor viajante (que é de NP, mas n se sabe se é de P).
Eu sou um homem simples, eu vejo Ciência Todo Dia, eu clico
Eu também
Somos 2
Exatamente
Pedro vc é realmente muito didático cara, esta de parabéns, nunca vi uma explicação tao simples sobre complexidade de tempo de algoritmos, poderia fazer mais alguns videos explicando todas as outras formas de complexidade de espaços e tempo! principalmente a parte logarítmica!
Acho que pra achar os caminhos mais curtos mais rápido, é so traçar uma linha reta entre dois pontos e adequa-la ao caminho mais próximo de sua tragetória
Faz um vídeo a respeito da hipótese de Riemann que também é um dos problemas de um milhão de dólares.É um assunto muito interessante com relação aos números primos. A resolução desse problema implica em grandes mudanças no sistema de criptografia e segurança do mundo todo.
kkkkkkkkkkkkkk TRES!!! vou usar essa na próxima aula hahahahahah
Por ele gritou o 3?
Muitos não sabem responder
@@tiorayquaza5210 ele gritou 3 pelo simples fato de que, exclamação (!) Sgnifica um ato de "exclamação" algo que chame a atenção do leitor.
Fazendo uma piada com o "3!" Que é usado na matemática.
@@SazonTd se viajou cara, modalidade de frase com curva melódica própria, ger. iniciada por que, quanto etc., expressando algum sentimento do falante diante de algo (p.ex.: que dia lindo! ).
@@tiorayquaza5210 ainda bem que as relações humanas não são sempre monótonas como o estudo da frase... Bom dia! (gritando)
@@HumorDemais kkk
Excelente a sua didática. Na Engenharia de Produção lidamos com problemas NP dentro de Pesquisa Operacional. Para definir a sequência de Produção de produtos em um parque de máquinas, fatorial semelhante ao problema do caixeiro que você cita, podemos usar algumas heurísticas que vêm sendo melhoradas há décadas. Realmente um desafio e tanto.
Eu sou de Ciência da Computação, vou começar minha terceira iniciação científica. A primeira foi com strip packing e a segunda foi com o problema do escalonamento com minimização do makespan.
Foram seus vídeos que aumentaram ainda mais minha paixão por ciência e física! Vou tentar ingressar na faculdade de física esse ano ❤
Pedro, faz um vídeo sobre as catedrais goticas explicando como essa arquitetura funciona, como chegaram na ideia de fazer essas catedrais naquela epoca e como funciona a distribuição de peso em construções e a ciencia por trás
Obvio q ele n vai fz um video desses o nome do canal é ciencia todo dia não historia todo dia
@@HqBlays *como essa arquitetura funciona, como funciona a distribuição de peso e a ciencia por trás* isso responde sua pergunta?
@@HqBlays Olha, eu realmente acredito que exista muita ciência e matemática por trás dessas construções magníficas e complexas. Foi necessário o uso da física para conseguir manter o equilíbrio da estrutura, da matemática para a aplicação da profundidade nos desenhos de planejamento, etc. A princípio, eu aprendi um pouco sobre toda a complexidade dessas estrutura em aulas de literatura sobre o renascentismo (◠‿◕)
@@isatasmath6135 Ok ok gente calma não percisam me bombardear de argumentos bem colocados o que eu quis dizer é que esses assuntos não são muito do tipo de assunto que o ciencia todo dia trata e a maioria do publico não tem interesse essa piada q eu fiz do "historia todo dia" foi so uma piada sem realismo eu sei que arquitetura engenharia e praticamente tudo que existe neste mundo pode ser explicado pela fisica ou matematica mas é so uma piada não percisam estressar
@@violletladonpin Mas so para deixar claro que pessoalmente até achei um assunto interessante mas não é exatamente feito para este canal
Os videos do pedro te mostram algo que sempre existiu mas vc nunca parou pra pensar sobre, é uma sensação incrivel
Muito bom o vídeo, porém uma curiosidade, o significado real de NP é "não-deterministico polinomial". Você pode ler mais sobre no livro Algorithm Design do Jon Kleinberg e Eva Tardos.
vim aqui pra falar isso. mas essa simplificação é muito comum né. até pq a definição em si tem a ver com a máquina de turing e não é tod mundo que conhece isso
Tem um outro ponto também é que 'P' se refere a complexidade para *resolver* um problema e 'NP' se refere a complexidade para *checar* a solução do problema.
Por exemplo, ordenar uma lista de números é resolvido com complexidade N*log(N) (como o Pedro disse). Checar que uma lista está ordenada, pode ser feito com complexidade N (basta percorrer a lista uma vez vendo se os números estão crescendo).
Mas eu acho que esse assunto é complicado de explicar mesmo. Tenho dezenas de colegas que estudaram computação comigo e tenho certeza que mais de 90% deles se perderia neste assunto.
Parabéns, Pedro! O vídeo ficou show de bola!
Corrigi isso também porque não tinha visto sua resposta kkk
@ NP também se refere a complexidade para resolver, mas em uma máquina de turing *não determinística* (por isso o N em NP). Dizer que NP se refere ao tempo necessário para verificar uma solução é só uma forma equivalente de definir a classe NP, mas ambas estão corretas.
Sua explicação foi mais fácil do que a que tive na faculdade, em estrutura de dados II. Como sempre, mandando bem demais. Um abraço pra você e pro Greg. Amo o trabalho de vocês!
Pedro, por favor. Faça video pra entender mecanica quantica. Seus videos me ajudam muito nas aulas!! Seu canal é sensacional!!
Mas ele só tem teorias, não cálculo
@@maniadesonic1225 O objetivo do canal não é a parte quantitativa, e sim qualitativa
@@eduardoz398 exatamente
tem um monte de video de mecanica quantica o que não tem é um de atomo quantico
1:20 Bublle sort , estudei isso na faculdade de Sistemas, uma das exigências em uma das provas a minha Prof de Lógica de programação pediu para que reescrevessemos o código de ordenação (que resumindo, são dois loops um dentro do outro) e essa pergunta já encontrei diversas vezes em outros lugares como testes para trabalhar na Àrea, mas o mais curioso é que isso não serve para resolver a maioria dos problemas no dia a dia do Desenvolvedor, que na maioria das vezes, se vê obrigado a usar a Lógica dos outros, como arquitetura, o que leva tempo e torna mais caro o processo de desenvolvimento de APPS e Sites.
Cada passo além na ciencia da computação custa caro, e o mercado não quer saber de criar nada, mas sim obter lucro e gastar menos com TI
Caraca Pedro, seus vídeos são praticamente motivacionais, o jeito que você explica faz parecer que qualquer parte da matemática é simples, obrigado mais uma vez.
Que simplicidade enorme ao clarificar um assunto senão o assunto de maior relevância para a computação. Brilhante. Como engenheiro da computação vejo isso está ao alcance de todos. Assim se faz ciência.
Faz um video sobre a Gravitação Quantica em Loop
O teor didático para entendimento do problema ficou muito bom, parabéns! Só um adendo: indo ao conceito da questão, P trata-se da classe de solução de problemas em tempo polinomial, enquanto a classe NP são problemas que podem ser verificados/checados em tempo polinomial. Portanto, não é exatamente correto colocar que P está dentro de NP por ter um problema fácil tornado difícil, mas porque se segue que se podemos solucionar um problema em tempo polinomial, ele também pode ser verificado em tempo polinomial. Abraço!
Caraí... :0
Por muito tempo eu também achei que NP era de "não polinomial", mas na verdade NP vem de "nondeterministic polynomial". Você pode pensar em NP como os problemas que possuem um certificado de solução verificável em tempo polinomial por exemplo se queremos saber se o problema do caixeiro viajante tem solução
Lembro que nos idos de 1999, meu primeiro estágio como programador em uma startup de logística, era mexer com o problema do caixeiro viajante (em Java). Lembro que na época, quando o Google não calculava rotas ainda, o que havia de mais interessante era o Djikstra 2 Pilhas.
Acho que são problemas diferentes hein. No caixeiro viajante você tem que sair de uma cidade, passar por todas as cidades e voltar para a cidade inicial, já o Djikstra é para o problema de Caminho de Custo Mínimo. Nesse você tem que sair de uma cidade e ir para outra, mas escolhendo uma sequência de cidades em que custo total vai ser mínimo, não precisa passar por todas.
Pedro, por favor faça um vídeo sobre cada proposta do premio do milenio de matemática, por favor
Sempre quis entender isso... vc explicou de um jeito mt claro... parabens!
Estudo programação e confesso que antes de ter contato com algoritmos, eu odiava matemática e sempre me perguntava: "pra quê vou aprender essas fórmulas na escola? serve pra nada".
Hoje eu digo pra mim mesmo que matemática, cálculos e etc estão em todo lugar, e quanto mais aprendemos sobre elas, mais facilitamos nossas vidas.
Fico maravilhado vendo programas rodando com fórmulas feitas a séculos atrás e funcionando super bem ♥️
Tá estudando programação?
Já vai aprendendo a resolver esse problema pra ficar milhonário.
function showDoMilhao(float p,float np) {
return p == np;
}
Mais um dia de vida sem eu usar o teorema de Pitágoras ou as milhões de fórmulas da escola... É importante só pra quem usa, totalmente dispensável fora da escola
@@Freedom182 Sou professor de matemática, realmente concordo que o currículo pode ser enxugado. Mas a questão da utilidade é muito complexa. A matemática "inutil" tem a utilidade de desenvolver seu raciocínio lógico, mesmo que não venha a utilizar várias das fórmulas ensinadas, conseguir aprendê-las é um exercício de perceber padrões e isso certamente nós usamos o tempo todo.
@@Freedom182 o colégio não te ensinou isso, o colégio te ensinou a fazer funções e te deu como exemplo aplicar em matemática básica. Você pode exercitar o teorema citado, por exemplo, para calcular a base da sua conta de energia ou água, para reduzir suas contas, ou otimizar o espaço na sua casa organizando seus móveis, ou calculando uma razão de ataque para sua pirâmide alimentar, se você só sabe usar uma parafusadeira multiúsos só para aparafusar e desaparafusar não culpe o manual ou a fabricante
@@Freedom182 Por favor, continue assim! Dessa forma o mercado fica menos competitivo e mais fácil pra aqueles poucos que não desprezam as exatas. Eu realmente agradeço muito existirem manés como você pois se todo mundo enxergasse o poder das exatas eu não teria construído minha empresa (por excesso de competição) em cima de conhecimentos de física e matemática e hoje não estaria vivendo uma vida de luxo. Muito obrigado mesmo!
Você podia fazer um vídeo falando sobre a universal wave function, adoraria saber mais sobre o assunto
Sempre trazendo vídeos muito interessantes, e apresentando de forma bem dinâmica, parabéns.
Verdade linda
Nesse algoritmo de buscar do menor que você descreveu faz n-1 comparações. Quando o algoritmo é inciado o primeiro elemento é sempre tomado como o menor e adiciona na variável, só a partir do segundo que irá ocorrer as comparações.
Pedro, um grande prazer assistir seus vídeos. Será que você poderia fazer um vídeo sobre o efeito piezoelétrico?
Vou dar uma olhada nessa questão sobre NP versus P mas o premio de 1 milhão de dollares acho bem pouco pra tudo que ele proporciona.
Publiquei um livro sobre o assunto e outros relacionados em 2017. Há diversos mitos a esse respeito. Esse vídeo dá uma ideia geral, mas a definição do problema envolve necessariamente máquinas de Turing.
Sua explicação da organização de uma lista de números em ordem crescente foi excelente! É dessa maneira que se faz um código, a não ser que você apele pra comandos já prontos que certas linguagens oferecem
sort()
min()
max()
Me formei em Ciência da Computação, tive varias aulas falando sobre isso, achei maravilhosa a forma com que você explicou esse conceito, me lembrando da aula de complexidade de algoritmo kkkk
Só tem que tomar cuidado na hora de calcular pra não acontecer estouro de pilha, ou falando tecnicamente na informática "buffer overflow" excedendo a quantidade de memória disponível com a quantidade de números a serem calculados.
Olha, é meio tarde pra isso, pois normalmente ninguém observa comentários recentes em videos "antigos", no caso, não acabados de lançar mas... minha ideia é, se há problemas que são muito complexos para ter computacionalmente falando uma resolução simples, então o passo seria criar uma via direta com o análise de todos os dados obtidos e chutar algo lógico dentro do que se compreende. np=p somente quando p=x ; np=y e np+p=z
um exemplo prático seria que ao invés de analisar qual a melhor rota para visitar todas as cidades capitais dentro de todos os dados, é vendo qual dado faz mais sentido com outros recopilados e tomar uma decisão lógica não aferrada na total certeza, inclusive isso foi já feito outras vezes antes o problema seria aplicar isso computacionalmente, mas infelizmente não possuo o conhecimento necessário nessa área para expressar como aplicar alí
Pedro, você podia fazer uma série de vídeos sobre os outros Problemas do Milênio, fiquei curioso pra saber quais são eles!
Trás mais vídeos com problemas não resolvidos, adorei o conteúdo!
obs: Faz um sobre Química.
Valeu!
Pequena correção: NP não é o conjunto de problemas não polinomiais, mas dos problemas polinomiais em maquina de turing não-deterministicas. Há problemas mais dificeis que NP.
Fonte: en.wikipedia.org/wiki/NP_(complexity) "In computational complexity theory, NP (nondeterministic polynomial time) "
8:15 As soluções pra esses problemas são algoritmos de otimização combinatória. Algoritmo genético, otimização por colônia de formigas, têmpera simulada. Mas eles não garantem o ótimo global
Como eu queria que meu professor de Análise de Algoritmos ensinasse bem como você ahahaaha. Excelente vídeo! Traz mais desse tipo de conteúdo!
Parabéns pelo vídeo Pedro e a equipe do Ciência Todo Dia. Falem mais sobre Matemática, como por exemplo da Medalha Fields, Prêmio Abel, descoberta ou criação, principalmente pra dismestificar essa coisa de que a Matemática já está "acabada" (já fizeram td q tinham pra fzr) mostrando assim, q os avanços nela levam a avanços em Física, Química, Ciência da Computação, Economia, Biologia (surpreendentemente a princípio), etc, seja de modo imediato ou levando séculos para tais conceitos serem introduzidos no mundo "real", atuando assim como uma verdadeira maestra no desenvolvimento humano.
As vezes sinto saudade das aulas de algoritmos na faculdade.. As coisas eram fáceis e não imaginava o quanto kkk
Pedrinho me ajudando a sintetizar uma resposta simples para uma prova que abrange as classes de solucionabilidade de problemas, desde já, muito obrigado!
O enigma do milênio mais conhecido(depois daqueles do yu-gi-oh), gostaria de saber mais sobre os outros 9
6*
E é Yang-Miles, um problema do milênio sobre física-quântica.
Curso ciência da computação e amei esse vídeo, fiquei me perguntando se tem outros vídeos relacionados ao tema de computação no canal. Acho que seria muito interessante se tivesse divisão por temas na aba de playlists do canal, por exemplo, uma playlist com vídeos que abrangem algo do mundo da computação, enfim, só uma sugestão :)
A resposta está na pergunta: se "P" significa "Polinomial" e "NP" significa "Não-Polinomial", então NP NÃO é igual a P. Se fosse, seria SP (Sim-Polinomial). Onde pego o prêmio?
0_0
Nao pega,por que pra pegar tem que provar que P = a NP e nao P != NP
@@feliperodrigues3958
(P = NP) = V ∨ F
V = (P = NP)
F = (P ≠ NP)
No buteco, é lá que o povo se convence com essa demonstração
Kkkkkkkkkkkk
Que Vídeo ótimo! Minha admiração! Indico o Canal sem dúvidas! Deus te abençoe sempre grandemente!
Se eu conseguisse provar p = non deterministic polinomial, eu jamais viria a publico entregar uma tecnologia tão fantástica por tão pouco. 1 milhão é o que você conseguiria ganhar por semana prestando serviços de otimização linear e otimização de rotas para companhias aéreas.
Imagina o governo conseguir quebrar a criptografia das criptomoedas e dos nossos dados pessoais.......rapazz
por isso a questão é: será que esse realmente é um problema que ainda não foi solucionado?
Capitalista
@@gabe4416 pode ser q sim, pode ser q não. Mas acho difícil ninguém ter se manifestado publicamente ou não sobre a descoberta
Para a pessoa ganhar o premio ela não precisa resolver o problema do caixeiro viajante. O contrário também vale, resolver o problema do caixeiro viajante não te garantirá o premio, por mais valioso que seja a solução.
Pensei em uma sugestão de início, no problema do valor mínimo notar que Soma_n = Mín + .... + Máx Máx = Soma_n - ... - Mín => Máx < Soma_n, se Mín > 0, portanto para achar o menor valor é possível fazer uma recursão fazendo apenas (Soma/kn) comparações de bits, isso faz que seja descartados em potências de 2, e ir diminuindo k até 1, pelo menos a solução para a maioria dos casos seria de complexidade < O(n). Teria que apertar o passo de diminuicao de k em log(n) pra manter o pior caso estável abaixo de O(np). Aí vale a continuação do raciocínio. Muito bom o vídeo. A inspiração que tive foi se pensarmos como nós humanos acharíamos a menor bola, nós simplesmente tiramos a média mental dos tamanhos e vamos comparando com as que são menores, com certeza o raciocínio humano é de ordem O(k) e não O(np). Para achar uma blusa preta no meio de 1 milhão de brancas, nós iríamos direto na preta, porque simplesmente dividimos exponencialmente nosso campo de visão (k) e descartamos rapidamente os conjuntos que não parecem na média.
Eu me sinto o meme da nazaré calculando, vendo os vídeos do Pedro.
NASA ré
Hahahahahahahaha exatamente isso mano
Eu achei q era só eu kkkk
Tu é foda demais cara, amo o teu trabalho! TMJ
Na realidade, NP significa “Nondeterministic Polinomial”, e não “não-polinomial”. Ou seja, problemas desse tipo são polinomiais em uma máquina não-determinístico.
Muito bom o vídeo e parabéns pela explicação!
sobre o crescimento de proteinas é outra coisa facil de resolver: se a proteina tem um determinado padrão de organização de moleculas posso automatizar o processo e atraves de outras proteinas posso usar a IA pra construir uma outra proteina com base estatistica de proteinas reais.
Uma curiosidade interessante: encontrar um algoritmo polinomial para o problema do cacheiro viajante é suficiente para demonstrar que P = NP, já que esse problema faz parte de uma sub-classe de problemas chamado "NP-difícil".
Isso vale pra outros problemas? O strip packing por exemplo?
Sim, strip packing também é NP-Hard(difícil).
Mano, nunca vi alguém explicar melhor que o Pedro, queria que ele fosse meu professor de Física e Matemática!
Aliás eu me inspiro em vc Pedro e também no Albert Einstein
7:15 me senti muito geek rindo da piada do 3! hahahahahaha mto boa.
KKKKKKKKKKKK EU RI MTO VEI
Cara, estou até agora dando risadas
Trabalho com geração clusters de alvos por coordenada. Algumas soluções já foram tentadas em python, mas todas voltam para a análise combinatória, que tem por consequência o tempo em demasia. Estou nessa empreitada, mas realmente em tudo que se pensa, se volta para esse mesmo ponto de partida.
O problema do Ciência Todo Dia é que eu fico paquerando Pedro Loos e esqueço de prestar atenção na explicação.
tu é?
Alienfobicos
Na faculdade resolvia alguns problemas como o do Caixeiro Viajante, dentre outros parecidos, utilizando alguns algoritmos, como Busca A* e Algoritmo de Dijkstra. Quando falamos em rotas sem nenhum parâmetro de definição realmente criamos um mundo de possibilidades(conforme citado no vídeo). Porém, quando definimos custos para as rotas, ou parâmetros a serem priorizados, esses algoritmos funcionam bem, diminuindo significativamente o tempo que esse algoritmo resolve o problema.
Os custos que serão os parâmetros de escolha podem ser baseados em alguns aspectos: Distancia territorial, tipo de terreno, dentre outros pontos que mudariam de problema para problema.
Sendo assim, seleção de melhores rotas e decisões de pontos já são bem executadas, um exemplo micro seria a própria rota selecionada pelo nosso GPS.
Acredito que problemas mais complexos, como os citados após foram realmente melhores para representar o quão impactante seriam os avanços com a solução desse problema.
Especialistas me corrijam se falei alguma bobagem. Qualidade do vídeo incrível, como sempre! 3!!!
Eu acho 1 milhão bem pouco como recompensa para resolver questões do MILENIO.
Cara como eu amo seus videos você realmente faz todo assunto ser cativante
Pedro, faz um vídeo explicando como Grigori Perelman resolveu a conjectura de Poincaré
Já resolvi, P desigual a NP. Pelo fato de algumas partes de alguns problemas não terem ligação com outras, então cada parte deve ser resolvida separadamente, é tudo aquilo que fica entre parênteses nas fórmulas ou quando vc vai resolver por exemplo um problema em duas dimensões como a regra de três, ou quando vc deve somar uma dimensão obter o resultado total para depois trabalhar com este resultado. Havia ou há nas calculadoras o M+, M- e MR, se não me engado, onde vc poderia resolver somas e depois somar ou diminuir o resultado utilizando M+ ou M-, mas isso não quer dizer que vc pode deixar de resolver os cálculos em todas as suas dimensões.
esse vídeo é um bom exemplo de resposta para aquela famosa pergunta (pra que eu vou usar matemática na minha vida?)
Mas você realmente vai usar? Ou só as pessoas que fazem programação precisam aprender?
@@wakamekat3805 se eu trabalhar com manicure e pedicure eu com certeza não vou usar, mas se eu quiser uma profissão que tem relação com exatas, aí eu vou usar, mas independente disso, conhecimento é conhecimento
@@kelvinmargotti325 sim sim, aprendi durante 12 anos da minha vida equações que nunca usei e hj não lembro de nada, enquanto em países desenvolvidos eu poderia estar aprendendo sobre econômia e as matérias que eu quisesse
Comecei a ler o Algoritmos hj, a tarde estava estudando sobre ordenação de números e esse lance de como o algoritmo escala de acordo com o n aí tu lança esse vídeo HOJE! QUE TIMING OBRIGADO, Pedro
Tem um episódio do "Elementary" que o caso é sobre o "P=NP"
Vou dar spoiler, não chega a conclusão nenhuma kkkk
Existe também outro problema que é parecido com esse do caixeiro viajante em termos de complexidade, chamado torre de Hanoi(é aquele que você tem 3 Torres com vários anéis e tem que tirar todos os anéis de uma torre e colocar em outra, sendo que um anel maior não pode ficar sobre um anel menor). Pra se ter uma noção, o número de movimentos necessários é obtido pela fórmula 2^n - 1. Se você tiver mil discos, o número de movimentos necessários é 1,07 elevado a 301 !!!. Fiz um teste em minha máquina e com 55 discos o código levou ± 4 horas, com 3,6 elevado a 16 movimentos. E não existe outra forma de resolver(mesmo) afinal essa é a forma mais rápida (pelo menos usando 3 Torres).
Eu sei os problemas de *NÃO TER 1 MILHÃO DE DÓLARES* Consequentemente não consigo resolver o problema ...😅
Faz sentido, com um milhão de dolares no bolso se torna mt mais empolgante trabalhar
@@TopherOzi se descobrirem esse problema a pessoa terá muito mais do que um milhão
Não se preocupe nem o Einstein sabia, ou seja, vc pode ser o próximo Einstein
Pra que ter um milhão? Se até o terno é de 2 bilhões
@ kkkkkkkk boa
Existe sim algum algoritmo pra fazer algum tipo de atalho pois a velocidade da luz " atalha " o tempo e o tempo não é palpável fisicamente porém é " atravessavel" digamos assim assim também um cálculo pode sim atravessar muitas possibilidades
Sugestão de video:
Como as bicicletas ficam em pé?
A pergunta é, porque elas cai
@@Herculesumb Einstein
Porquê elas querem
A resposta esta na relação entre a superficie externa e a area interna de diferentes coordenadas de dimensões, por exemplo um circulo para uma esfera,dps hiper esfera.vc ira perceber q o y de x*y vai aparecer c a soma dele, por exemplo,num circulo tera a area e circunferencia,numa esfera sera a circunferência, area e volume,numa hyperesfere seria circunferência, area,volume e algo a mais
Excelente vídeo, me fez ter nostalgia das aulas de algoritmo na faculdade (trabalho com engenharia de software)
Nossa o vídeo ficou muito bom e extremamente didático! Parabéns!
Só uma correção: NP não vem de "não polinomial", mas sim de "nondeterministic polinomial time" (tempo polinomial não deterministico). Até porque a pergunta P=NP está interessada exatamente em saber se os problemas NP são, ou não, resolviveis em tempo polinomial hahaha.
O termo NP é um pouco mais chatinho de se definir, mas resumidamente: "são os problemas para os quais as instâncias possuem um certificado pequeno de resposta (pode ou não ser a própria resposta) que pode ser usado para validar a solução em si em tempo polinomial"
Ou seja, para um problema ser NP existe um algoritmo que resolve suas instâncias em tempo polinomial se você der um pouco de informação extra para ele, meio que o algoritmo "rouba" já que ele tem mais informações. Por exemplo: para o caixeiro viajante um certificado pequeno pode ser a própria rota (ordem em que você visita as cidades).
Então basicamente resolver P = NP, é achar uma "fórmula" polinomial para substituir a forma "fatorial" de análise combinatória?
Pensei nisso também
Acho q ss
Já conhecia esse problema, mas nunca vi de uma maneira mais didática
Melhor parte é 7:14 voltei umas 5 vezes só pra rever KKKKKKKKKK
Ia comentar isso kkk
kkkkkkkkkkkkkkk foi uma quebra pra mim, tava tão concentrado prestando atenção
Até assustei kkkkkk
Eu ri muito e voltei várias vezes também kkkkkkkkkkkk muito bom!
sou universitario da FATEC e estou fazendo o curso de DSM (Desenvolvimento de Solftware Multiplataforma) e meu professor passou um trabalho sobre complexidade de algoritmo e colocou seu video de referencia
Deixa eu ver se eu entendi, se eu encontrar esse novo algorismo ganho 1M, que podem ser descryptografados com o algorismo que encontrei. Ou seja eu posso quebrar algum outro algorismo usando esse novo e ganhar muito mais do que 1M
Importante notar que log, para a população em geral, é na base 10, mas log, na computação, se refere a base 2
Bom o ciencia todo dia è de fato algo no qual quem tem curiosidade, ficar mais curiosidade ainda para aprender, devido a uma explicação bacana de se ouvir, onrigado mano pedro.
Poderia fazer um video sobre metaheurística aplicadas a problemas NP
EX: Bin Packing Usando ILS
O vídeo tem uma informação errada, NP não significa "não polinomial" e sim um conceito mais complexo. Se NP fosse não polinomial o problema estaria resolvido não é verdade. Essa é uma confusão comum. Fora isso o vídeo é legal.
O erro de identificar NP como não polinomial é muito ruim. Me incomodou bastante.
Oq é ent?
@@joaopedroandsan2172 NP significa "não deterministicamente polinomial".
@@gustavobittencourt meio contra intuitivo, poderia ser NDP... enfim, obrigado pelo esclarecimento
Tratar problemas de tal complexidade de forma a tornar compreensível ao público em geral é digno de congratulações.
Se um dia alcançamos esse algoritmo, daria para avançar bem no xadrez também, e seria impossível uma pessoa ganhar no xadrez de uma máquina que use esse algoritmo, e em compensação, a máquina nos ensinaria muito
já é basicamente impossível o ser humano ganhar de uma máquina no xadrez (considerando os melhores, claro)
Caramba, estava lendo sobre isso no wikipédia ontem, não entendia nada.
Muito bom!
Se P=NP é so cancelar P com P e sobra N.
Tragam meu dinheiro.
KKKKKKKK
P = NP
N = P/P
N = 1
quero também
São vídeos seus que me fazem entender melhor matemática e a ciência de uma forma interessante e me faz gostar e muito disso,muito obrigado,Pedro❤(e pode deixar que se eu achar o resultado com provas,eu divido o dinheiro👀)
P = NP
Cortando P dos dois lados da equação :
N = 1
Big brain time 😎👍
P = NP
NP = P
N = P÷P
N = 1
Big brain time 😎👍
Em 4:10, aprendemos sobre o número de passos necessários para quantidade de números. Mas oq não entra na minha cabeça, é que o fato comparação, não se trataria do todo, porque comparativamente, se eu tivesse 100 números, e fosse colocá-los de forma decrescente, eu não precisaria comparar nenhum número com todos os demais pra saber que ali seria seu lugar, apenas o antecessor, exemplo, se estou no número 87, eu não preciso comparar o 86 com todos os outros 85 números para saber qual o próximo, precisaria apenas comparar com o antecessor "86", logo, não precisei de 85 comparações pra saber o lugar seu devido lugar, só precisaria de uma comparação, o número antecessor, então se ele fosse menor que 87, e o valor é 86, com apenas 1 comparação, e não 85, eu achei seu devido lugar. Faz sentido ????
Eu quero ter milhão de dólares para viver uma vida boa!! Mas usarei uma parte para instituições de câncer e outras instituições importantes.
Eae Felipe, tranquilo
Um milhão não dá para fazer muita coisa
@@mikebezerra3188 na verdade, dá pra fazer um bocado de coisa sim. Afinal, é o dinheiro de toda uma vida pra maioria dos brasileiros, mas não é como se vc fosse um Mark Zukerberg ou até mesmo um Gugu da vida, então invista esse dinheiro com consciência...
@@mikebezerra3188 Dá sim para fazer, só basta ter educação financeira.
@@mikebezerra3188 Da pra mudar de vida tranquilo, só saber como usar, né
Muito bom entender o vídeo por completo, sou cientista da computação e amo algoritmos e métodos de ordenação 😍