Olá Esse vídeo foi feito em parceria com o Kelly é uma plataforma voltada para você aprender inglês a maneira mais natural e personalizada possível que fica até o final do vídeo para ver uma promoção especial que o que ele fez especialmente para você responda as perguntas no final desse vídeo para concorrer a um milhão de dólares só que não sou eu quem vai pagar o prêmio em questão e oferecido pelo Instituto de matemática Clay e a pergunta é uma das 7 perguntas do milênio essas perguntas representam sete dos problemas mais difíceis ainda sem resposta da
matemática física computação dos nossos tempos modernos e muitos deles sem consequências práticas bastante significantes para incentivar a investigação desses problemas o Instituto oferece um prêmio de 1 milhão de dólares para quem conseguir resolver a pergunta de hoje é um problema da Computação sobre a complexidade de problemas difíceis a pergunta é conhecida como P = NP e antes de eu poder explicar ela eu preciso explicar algumas coisas vamos supor que eu peço um favor para você eu vou te dar uma lista de 1.000 números e eu quero que você encontre o menor deles para mim se
ele se fosse pequena digamos 10 números seria trivial mas como início é muito grande você decide pensar em uma estratégia você vai olhar o primeiro número da lista e anotar ele numa folha separada Então você vai olhar o segundo número e se ele for menor que o número anotado você apaga esse primeiro número e a nossa é você então você segue para o terceiro número e repete o processo comparando ele com o número anotado repetindo o processo mil vezes você vai com certeza ter encontrado o menor número na lista esse plano que você criou aquela
chamamos de um algoritmo uma série de Passos bem definidos que realizam a tarefa muito clara de nesse caso encontrar o menor número nessa lista só que eu quero focar numa característica específica desse algoritmo que nós acabamos de fé uma lista de 1.000 números Você precisa fazer mil comparações pra executar o algoritmo internos ele se tivesse dois mil números você precisaria de 2000 comparações E se ela tivesse sem o número você precisaria de 100.000 comparações Vocês entenderam a ideia ou seja a quantidade e de comparações aumenta diretamente com a quantidade de números na lista o número
de elementos na lista forene o número de comparações necessárias é essa dependência do número de passos que o algoritmo precisa fazer com a quantidade de números na lista é chamado de complexidade do algoritmo para esse algoritmo de achar o valor mínimo especificamente a complexidade é linear Ou seja a quantidade de números dobra é necessário dobro de passar sabonete mas esse Nem sempre é o caso vamos ao segundos é o em vez de encontrar o menor número da lista eu quero que você reordene e ela do menor número para o maior essa já é uma tarefa
bem mais complicada Então vamos usar uma lista de apenas 10 números fora de ó um jeito de fazer isso é o seguinte você pega a lista de 10 números desorganizados e repete o algoritmo de achar o menor valor do exemplo anterior dessa forma você vai achar o menor dos 10 números e aí você anota ele como menor número da nova lista organizada agora você foca o resto da lista desorganizada ignorando o anotar sobrar 19 números Então você repete o algoritmo de achar o mínimo de novo preciso nove números restantes anotando o resultado como segundo menor
número da lista organizada Então você repete os outros oito números que sobraram e daí para os últimos sete e acendia no fim do processo você vai ter uma nova lista com os 10 números ordenados só que equivale uma pergunta interessante quantos passos você teve de executar para conseguir fazer isso Vamos por partes você primeiro com parou de 10 números do primeiro passo e no segundo nove números e aí oito números e depois sete e assim por diante até chegar em um ou seja o número total de Passos foi 10 + 9 + 8 + 7
+ 6 + 5 + 4 + 3 + 1 e somando tudo foram 55 comparações ou 55 passos para reordenar a lista mas e se fossem sem números a quantidade de passa seria sem mais 99 mais ou menos que oito mais 97 mas 96/95 mas 9423 mais ou menos até um felizmente Nós não precisamos fazer essa sombra Porque existe uma forma o Siena é a quantidade de números o número de Passos = n ao quadrado + Zene / 2 se N = 10 + 155 como esperar se alista tem 100 números é igual a sem
e o resultado é 5050 da dessa forma do número de Passos O que determina a complexidade de um algoritmo é o termo que cresce mais rápido como o número de passos que nesse caso é elevado ao quadrado então se a quantidade de números na lista aumenta em dez vezes a quantidade de Passos aumenta em aproximadamente 100 vezes que a 10 ao quadrado esse algoritmo de ordenar a lista é mais complexo do que o algoritmo que encontre o menor valor portanto que vai ser mais lento de executar casa quantidade de dados seja grande o suficiente Ou
seja a complexidade de uma bonito está ligada a sua velocidade em cumprir uma tarefa uma coisa curiosa que o mesmo problema pode ser resolvido de diversas fotos existe literalmente uma dúzia de diferentes algoritmos que reordenou uma lista vocês podem literalmente escolher o favorito e alguns deles são menos complexas o ritmo que eu apresentei tem uma complexidade menor do que elevado ao quadrado isso basicamente quer dizer que existe uma forma mais rápida para reordenar uma lista com complexidade n logaritmo de esse número cresce mais devagar do que elevado ao quadrado e como logaritmo apareceu aqui dá
uma longa está em resumo o mesmo problema pode ser resolvido por diferentes algoritmos e nem todos esses algoritmos tem a mesma velocidade de execução ou complexidade todos os problemas que podem ser resolvidos que algum algoritmo que tem como complexidade a quantidade de dados ele elevado a um outro número por exemplo a forma uma categoria de problemas com solução que nós chamamos de polinomial Não se preocupa entanto como o nome e sim em que isso quer dizer é um elevado alguma coisa ou seja problemas que podem ser resolvidos por algoritmos e complexidade n é o quadrado
em Ao Cubo e assim por diante isso é que nós chamamos de solução polinomial nós chamamos o conjunto de todos esses problemas pela letra e e esse é o p do P = NP ou seja um texto bom então vamos agora para o termo n pé Imaginem agora que você é um caixeiro-viajante isso é um vendedor que passa de cidade em cidade você está saindo da sua cidade e quer visitar outras duas cidades chamada de cidade 1 e 2 eu só que como é que você descobre Qual que é o melhor caminho para fazer um
jeito fácil seria simplesmente fazer uma lista com todos os caminhos possíveis e ver em qual deles Você percorre a menor distância isso é você pode sair da cidade 1 e a2 ou sair da dois e para um e nesse caso é bastante fácil porque você tem apenas duas cidades com dois caminhos possíveis então é bastante fácil de encontrar o melhor caminho só que com três cidades você pode dar um para dois tá três da 2 para 1 para 3 ou misturar isso de qualquer forma que você preferir no fim você vai ter seis possíveis caminhos
então você olha qual deles é o menor usando o nosso algoritmo de mínimo do começo do vídeo o jeito de calcular isso aqui na primeira viagem você tem três cidades vai escolher e na segunda você tem duas e na última e modificando todas as escolhas você tem 3 x 2 x 1 = 6 cidades essa operação de multiplicar todos os números maiores do que 10 antes de três é chamado de 1 fatorial e a escrita com 13 seguido de uma exclamação e é pronunciado três brincadeira pronunciar três fatorial a exclamação essa 15 se for em
cinco cidades o número de escolha é 5 fatorial ou 5 x 4 x 3 x 2 vezes um que é 120 com sete cidades do mundo de possibilidades de aumenta para mais de 5 esse o seu objetivo fosse visitar todas as 26 capitais do Brasil mais o Distrito Federal o número de possíveis ordens a qual você pode fazer isso é 10 elevado a 28 isso é um com 20 e 80 atrás mas estamos falando de menos de 30 cidades usando esse algoritmo para listar civis caminhos o número de caminhos aumentam muito rapidamente mais do que
é uma exponencial mesmo computador teria dificuldade em encontrar o melhor caminho numa situação dessas é mas já Vimos que o mesmo problema pode ter outro solução mais rápida Então a nossa solução simples não é nada fácil Será que existe alguma solução rápida para o problema do caixeiro-viajante EA resposta é que atualmente não existe uma solução rápida para este problema todas as soluções para ele tem basicamente uma complexidade exponencial isso é crescem muito rapidamente com o número de cidades outra forma de falar isso a dizer que não existe um algoritmo com complexidade da forma n ^
ca que resolve o problema isso é importante porque algoritmos polinomiais o Pela expressão V = NP são muito mais rápidos o que algoritmos não polinomiais o NP da expressão P igualmente problemas como esse do caixeiro-viajante que não tem solução de complexidade polinomial conhecida como um outro conjunto de problemas de notado como NP de não polinomial todo o problema polinomial também a NP porque nós podemos simplesmente escrever um algoritmo bem péssimo para resolver eles e transformar um algoritmo rápido e um algoritmo de complexidades pô é mas a pergunta de um milhão de dólares é justamente a
oposta ou seja Será que existe um algoritmo rápido ou seja polinomial para resolver o problema do caixeiro-viajante e outros problemas em vários Será que todos os problemas NP sem soluções rápidas não são secretamente P Será que o conjunto P e o conjunto NP são mesmo ou seja P = NP acharam algoritmo super lento da forma n em 1 milhão seria um avanço drástico e que talvez pague Quem conseguir ele como um milhão de dólares e essa é justamente a pergunta em aberto Será que para todo problema complexo de complexidade não polinomial MP existe um algoritmo
rápido para resolver ele que seja de complexidade polinomial p a resposta para essa pergunta Tem implicações bastante Profundas se sim isso significa que nós como humanos estamos falhando entender algo muito importante sobre como criar algoritmos ciperfor = NP Isso significa que todos os algoritmos de criptografia o Sérgio os nossos dados na internet podem ser facilmente quebrados por esse algoritmo rápido que ainda não foi encontrado só que por outro lado problemas como do caixeiro-viajante tem aplicações no mundo real são variações desse problema que determina o tráfego de bens e pessoas ao redor do mundo e acharam
algoritmo computacional viável para utilizar isso poderia revolucionar completamente a logística por trás o transporte de cargas e pessoas Outra área que se beneficiaram imensamente esse per fosse igual NP é a medicina EA biologia proteínas são compostos biológicos essenciais tanto para nós como animais como para produção de remédios e compostos químicos proteínas são grandes cadeias atômicas que se organizam de forma tridimensional e essa organização tem consequências em como elas funcionam reduzir a forma de uma proteína a partir da sua composição molecular é um problema de complexidade emitir não polinomial descoberta de um algoritmo rápido para isso
seria um avanço drástico na pesquisa por diversos remédios e não entendimento de diversas áreas da biologia apesar disso a maior parte dos a aposta Que pena não é igual a isso é existem problemas no mundo que são muito complexos para serem resolvidos de forma rápida Se esse for o resultado certo Existem poucos benefícios práticos os ovos Mas isso não tornaria o resultado menos impressionante é importante por nosso entendimento da Computação a pergunta P = NP basicamente essa um complexo ao mundo em que nós habitantes Será que existem programas de computador rápidos para quase qualquer problema
ou será que certas soluções estão ocultas por um mar de complexidades se você tiver uma resposta com uma prova do resultado por favor deixe nos comentários e a gente divide o prémio do Instituto karai eu Julho mas sabe o que que é muito melhor do que ganhar um milhão de dólares aprender uma nova habilidade que vai abrir infinitas portas e oportunidades para você Esse vídeo foi feito em conjunto com o Camille que é uma plataforma voltada para você aprender inglês da maneira mais natural e personalizada possível com quem você aprende inglês falando diretamente com tutores
nativos e de diversas formações e isso faz aprendizado ser muito diferente além de você está as pessoas que têm o inglês como língua materna você pode escolher eles com base nos seus interesses Já pensou trem de inglês falando sobre matemática física ou até mesmo sobre os mistérios do universo ou problema do P = NP do quem de você pode ter aulas particulares e aprende de acordo com os seus objetivos a e o melhor de tudo é 24 horas você faz o seu horário de acordo com a sua agenda e isso é extremamente importante para pessoas
modernas que estão sempre em movimento as aulas podem ser feitas pelo computador ou pelo aplicativo e como Esse vídeo foi feito em parceria com quem eu tenho uma surpresa para vocês usando o código que está aparecendo na tela Pedro 50 off tudo junto ou seis ganham uma aula gratuita para experimentar o que ele sem compromissos além de cinquenta por cento de desconto no plano ao porque eu tenho certeza que vocês vão decidir assinar depois de experimentar o que ele é perfeito para você aprender a falar em inglês porque no fim é isso que importa lenguajes
a mente biztalk é natural last Weekend Muito obrigado e até a próxima E aí E aí E aí E aí E aí
