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!
@@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! ).
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).
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.
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!
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.
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.
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
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
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!
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!
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.
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
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.
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) "
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!
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.
Eureca eu tenho não só uma solução mais três. 1°exemplo: você aplica o spin logo tudo que não for "1" é diferente de "1" então se você tem apenas dois números 1 e 2 sabendo que 1 é 1 então n precisa de ler o 2 para saber que 2 é 2 e assim sucessivamente. 2'exemplo: no segundo exemplo vc cria uma tabela tipo o campo de higgis nesta tabela vamos supor que tenha 4 casas vazias a cada casa da tabela você dará um nome casa 1=a, 2=b, 3=c, 4=d sabendo disso você aplica a seguinte condição cada casa só Pode receber um valor nunca um valor diferente assim como no campo de higgis logo então você tera todos os resultados. 3 exemplo é geométrico. Imagina que eu lhe dê uma daquelas réguas que se usa para treinar ortografia, aquelas infantil que tem o número de 1 a 10, logo então você vai em um ambiente escuro e joga uma luz por trás da régua, todos os números irá aparecer certo. Então. Agora vamos supor que vc tampe o número 2,5 e 10 e jogue a luz novamente você verá refletido todos os números menos os que você tampou.sem ter que analizar mais nada
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?
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.
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.
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í
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.
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
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.
Uma correção: se você possui 100 números a ser comparado você não vai fazer 100 comparações você fará 99 comparações pois você não irá comparar um número com ele mesmo Exemplo: número 2 não será comparado com ele mesmo pois nn faz sentido Ele será comparado com os outros 99
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.
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).
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
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.
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".
Pedrinho me ajudando a sintetizar uma resposta simples para uma prova que abrange as classes de solucionabilidade de problemas, desde já, muito obrigado!
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!
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
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.
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
@@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
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 :)
Caro Pedro, o vídeo é muito didático e bem feito, parabéns! Mas no tempo 10:45 você afirma que NP significa "Não Polinomial" e isto está incorreto. O que podemos afirmar sobre NP é que temos um "gabarito" que valida soluções não determinísticas do problema em tempo polinomial, mas claro que isto tornaria seu vídeo muito complicado. Então o correto e mais fácil de entender é afirmar que NP são problemas que ainda não encontramos algoritmos polinomiais para resolvê-lo.
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.
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
Não manjo de matemática, porém, vamos lá. Não sei se o problema matemático é como vc descreveu ou se por didatismo ficou assim, mas quando pensamos na complexidade de achar os caminhos reais é algo analógico enquanto os dois primeiros exemplos eram intrinsecamente ligados a conjuntos de números bem diretos. Se pensarmos que esses caminhos estão mapeados digitalmente, o que poderíamos ter primeiro é um algoritmo pensando em criar conjuntos de valores em cada cidade, onde se existe, por exemplo, um valor 345AF eu sei que são 345 km para sair da cidade A para F. Tendo esses valores fixos rastreados de maneira bem linear, me parece fácil de fazer um segundo comando mais direto para localizar ou calcular rotas. O jeito que você explicou no vídeo me deu a impressão de que esse último problema é mais linguístico do que matemático.
Uma correção: NP significa "não deterministico polinomial", ao invés de "Não Polinomial" como citado no vídeo. Isso indica que se você tem uma máquina equivalente a de Turing e que esta possui poder não deterministico, podemos encontrar a solução em tempo polinomial, para qualquer problema computavel. É uma máquina teórica.
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
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!!!
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).
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
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.
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
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
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
Eu sou um homem simples, eu vejo Ciência Todo Dia, eu clico
Eu também
Somos 2
Exatamente
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).
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.
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!
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.
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.
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
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
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!
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
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.
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
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.
Faz um video sobre a Gravitação Quantica em Loop
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.
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) "
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
Pedro, por favor faça um vídeo sobre cada proposta do premio do milenio de matemática, por favor
Que louco. Deu introdução de algoritmo e estrutura de dados e complexidade de algoritmo de maneira simples.
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.
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.
Sempre trazendo vídeos muito interessantes, e apresentando de forma bem dinâmica, parabéns.
Verdade linda
Eureca eu tenho não só uma solução mais três.
1°exemplo: você aplica o spin logo tudo que não for "1" é diferente de "1" então se você tem apenas dois números 1 e 2 sabendo que 1 é 1 então n precisa de ler o 2 para saber que 2 é 2 e assim sucessivamente.
2'exemplo: no segundo exemplo vc cria uma tabela tipo o campo de higgis nesta tabela vamos supor que tenha 4 casas vazias a cada casa da tabela você dará um nome casa 1=a, 2=b, 3=c, 4=d sabendo disso você aplica a seguinte condição cada casa só Pode receber um valor nunca um valor diferente assim como no campo de higgis logo então você tera todos os resultados.
3 exemplo é geométrico.
Imagina que eu lhe dê uma daquelas réguas que se usa para treinar ortografia, aquelas infantil que tem o número de 1 a 10, logo então você vai em um ambiente escuro e joga uma luz por trás da régua, todos os números irá aparecer certo. Então. Agora vamos supor que vc tampe o número 2,5 e 10 e jogue a luz novamente você verá refletido todos os números menos os que você tampou.sem ter que analizar mais nada
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!
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
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.
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.
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í
Você podia fazer um vídeo falando sobre a universal wave function, adoraria saber mais sobre o assunto
As vezes sinto saudade das aulas de algoritmos na faculdade.. As coisas eram fáceis e não imaginava o quanto kkk
Trás mais vídeos com problemas não resolvidos, adorei o conteúdo!
obs: Faz um sobre Química.
Sempre quis entender isso... vc explicou de um jeito mt claro... parabens!
Pedro, um grande prazer assistir seus vídeos. Será que você poderia fazer um vídeo sobre o efeito piezoelétrico?
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.
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
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()
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!
Agora como é que o Instituto vai saber se uma resposta está correta se nem eles mesmo sabe a resposta ??? Ai fica a incógnita
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.
Uma correção: se você possui 100 números a ser comparado você não vai fazer 100 comparações você fará 99 comparações pois você não irá comparar um número com ele mesmo
Exemplo: número 2 não será comparado com ele mesmo pois nn faz sentido
Ele será comparado com os outros 99
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.
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
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).
Pedro, faz um vídeo explicando como Grigori Perelman resolveu a conjectura de Poincaré
Importante notar que log, para a população em geral, é na base 10, mas log, na computação, se refere a base 2
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)
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.
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).
Predo, faz um vídeo sobre a complexidade dos números primos que é uma questão que também vale 1 milhão de dólares 😭❤
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
Pedrinho me ajudando a sintetizar uma resposta simples para uma prova que abrange as classes de solucionabilidade de problemas, desde já, muito obrigado!
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!
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
Um milhão de dólares é muito pouco dinheiro. Essa solução vale mais que um trilhão de dólares. Por menos que isso é não vendo kkk
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.
Tem um episódio do "Elementary" que o caso é sobre o "P=NP"
Vou dar spoiler, não chega a conclusão nenhuma kkkk
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
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
Já conhecia esse problema, mas nunca vi de uma maneira mais didática
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
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 :)
Sugestão de video:
Como as bicicletas ficam em pé?
A pergunta é, porque elas cai
@@Herculesumb Einstein
Porquê elas querem
Caro Pedro, o vídeo é muito didático e bem feito, parabéns! Mas no tempo 10:45 você afirma que NP significa "Não Polinomial" e isto está incorreto. O que podemos afirmar sobre NP é que temos um "gabarito" que valida soluções não determinísticas do problema em tempo polinomial, mas claro que isto tornaria seu vídeo muito complicado. Então o correto e mais fácil de entender é afirmar que NP são problemas que ainda não encontramos algoritmos polinomiais para resolvê-lo.
Eu acho 1 milhão bem pouco como recompensa para resolver questões do MILENIO.
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.
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
Não manjo de matemática, porém, vamos lá. Não sei se o problema matemático é como vc descreveu ou se por didatismo ficou assim, mas quando pensamos na complexidade de achar os caminhos reais é algo analógico enquanto os dois primeiros exemplos eram intrinsecamente ligados a conjuntos de números bem diretos.
Se pensarmos que esses caminhos estão mapeados digitalmente, o que poderíamos ter primeiro é um algoritmo pensando em criar conjuntos de valores em cada cidade, onde se existe, por exemplo, um valor 345AF eu sei que são 345 km para sair da cidade A para F. Tendo esses valores fixos rastreados de maneira bem linear, me parece fácil de fazer um segundo comando mais direto para localizar ou calcular rotas.
O jeito que você explicou no vídeo me deu a impressão de que esse último problema é mais linguístico do que matemático.
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
Uma correção: NP significa "não deterministico polinomial", ao invés de "Não Polinomial" como citado no vídeo. Isso indica que se você tem uma máquina equivalente a de Turing e que esta possui poder não deterministico, podemos encontrar a solução em tempo polinomial, para qualquer problema computavel. É uma máquina teórica.
Excelente vídeo, me fez ter nostalgia das aulas de algoritmo na faculdade (trabalho com engenharia de software)
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
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!
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 ate elogiaria o vídeo, mas eu não vi ainda
Pelo menos ele é sensato
Tratar problemas de tal complexidade de forma a tornar compreensível ao público em geral é digno de congratulações.
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
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).
p = np
np = p
p = p
_
n
Quando pegar o premio me fala que passo o pix.
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
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.
1:45 na verdade você iria fazer 999 ou 1999 comparações, já que você não vai o próprio número com ele mesmo
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 😎👍
Tu é foda demais cara, amo o teu trabalho! TMJ
P = NP
N = 1
cade meu milhão?
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