O Problema de 1 MILHÃO de DÓLARES
HTML-код
- Опубликовано: 7 сен 2024
- * Inglês no Cambly com até 50%OFF só por uma semana! - PEDRO50OFF l bit.ly/3lB4Gwh
* Aula grátis pra você experimentar o Cambly quando quiser com o código: bit.ly/3lB4Gwh
P = NP é um dos problemas do milênio mais difíceis de serem resolvidos, mas que tem consequências muito importantes para a humanidade (além de um prêmio de 1 milhão de dólares para quem conseguir resolvê-lo). Nesse vídeo eu vou explicar o que significa dizer que P = NP e porque isso importa.
Seja membro do nosso canal para ajudar a manter os vídeos no ar! ruclips.net/user/cie...
Minhas redes sociais:
/ pedroloos
/ pedroloos
Nosso podcast: anchor.fm/sinapse
E-mail: contato@cienciatododia.com.br
Um muito obrigado aos apoiadores do Catarse que tornaram esse vídeo possível: René da Silva Bastos, Patricia Guedes, Pedro Amorim, Edilson Gomes, Simone Neves, Yann Motta, Mauricio Diegues e Adriano Cardoso Lima.
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
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
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.
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.
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
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!
Eu sou um homem simples, eu vejo Ciência Todo Dia, eu clico
Eu também
Somos 2
Exatamente
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, 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
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!
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.
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.
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.
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.
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.
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
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
@@ViolletLeDonPin Mas so para deixar claro que pessoalmente até achei um assunto interessante mas não é exatamente feito para este canal
Excelente video!! Uma correcao que é importantissima, NP é "Não deterministico polinomial", e não "não-polinomial". Isso faz muita diferença! Rsrs
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
@@Mairon.Mulinari 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.
@@Mairon.Mulinari 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
@@Mairon.Mulinari 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.
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
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!
Faz um video sobre a Gravitação Quantica em Loop
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, 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
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
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) "
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.
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
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.
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.
As vezes sinto saudade das aulas de algoritmos na faculdade.. As coisas eram fáceis e não imaginava o quanto kkk
Você podia fazer um vídeo falando sobre a universal wave function, adoraria saber mais sobre o assunto
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
Os videos do pedro te mostram algo que sempre existiu mas vc nunca parou pra pensar sobre, é uma sensação incrivel
Pedro, por favor faça um vídeo sobre cada proposta do premio do milenio de matemática, por favor
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.
Sempre trazendo vídeos muito interessantes, e apresentando de forma bem dinâmica, parabéns.
Verdade linda
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í
Trás mais vídeos com problemas não resolvidos, adorei o conteúdo!
obs: Faz um sobre Química.
Pedro, um grande prazer assistir seus vídeos. Será que você poderia fazer um vídeo sobre o efeito piezoelétrico?
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
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!
Pedro, faz um vídeo explicando como Grigori Perelman resolveu a conjectura de Poincaré
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
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!
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.
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
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.
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)
Importante notar que log, para a população em geral, é na base 10, mas log, na computação, se refere a base 2
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
Que louco. Deu introdução de algoritmo e estrutura de dados e complexidade de algoritmo de maneira simples.
Sugestão de video:
Como as bicicletas ficam em pé?
A pergunta é, porque elas cai
@@Herculesumb Einstein
Porquê elas querem
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.
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!
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.
Tem um episódio do "Elementary" que o caso é sobre o "P=NP"
Vou dar spoiler, não chega a conclusão nenhuma kkkk
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).
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
(Oque eu vou falar agora provavelmente tem vários erros, me corrijam no que estiver errado)
Usando o exemplo das cidades, vamos supor que eu estou no rio de janeiro em vez de calcular todas as viajens de uma vez, eu poderia calcular a distância entre as cidades e o rio de janeiro e ir para a mais proxima assim so teriam 25 cidades e o destrito, assim sucessivamente
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).
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).
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
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.
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
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
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
Eu ate elogiaria o vídeo, mas eu não vi ainda
Pelo menos ele é sensato
Já conhecia esse problema, mas nunca vi de uma maneira mais didática
Eu acho 1 milhão bem pouco como recompensa para resolver questões do MILENIO.
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!!!
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!
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.
P = NP
N = 1
cade meu milhão?
Eu tenho uma dúvida, e se recriassemos o big bang em uma escala beeeeem menor, tipo oq o ripy fez, criou um universo, poderíamos saber exatamente oq aconteceu antes ou se pode haver outras formas de vida?
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 😎👍
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()
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
Eu apostaria na equivalencia NP=P. Assim como existe uma superfície em Gauss que explica espaços imersos, de ponta-cabeça, deve existir um espaço em dualidade que espelha o problema do caixeiro viajante no plano, a partir de sua projeção no espaço.
Certamente ninguém hesitaria em saber qual o percurso entre cidades situadas em uma montanha...A gravitação seria o seu Norte!
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é
Pedrinho me ajudando a sintetizar uma resposta simples para uma prova que abrange as classes de solucionabilidade de problemas, desde já, muito obrigado!
p = np
np = p
p = p
_
n
Quando pegar o premio me fala que passo o pix.
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.
Piada besta do ano que eu ri para cacete foi o "se pronuncia 3!!!" HAHAHA
Claramente a aplicação desse número é em jogos de truco
Eu acho que P=NP basta criar um app com figuras polinomiais e fazer com que usuários resolvam esses gráficos gerando a interação do P com o NP criando incontáveis novos algoritmos de rápida resolução.
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
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:14 oh, céus, como eu ri disso KKKKKKKKKKKKKK
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 😭❤
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
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 :)
1º reza a lenda que o Pedro da coração para o primeiro
Hehe
Hahahah parece que sim
Parabéns
Perdeu o coração kkkk
Engraçado q ontem msm eu estava vendo os problemas q valem 1 milhão de dólares e hj vc posta 1 deles kkkkkkkk
Faz mais sobre os outros tbm e tbm contando do cara q conseguiu resolver um deles lá em 2006 (acho)
Poderia fazer um vídeo explicativo falando sobre a teoria de que o universo não é infinito? Eu estava na internet e vi algumas pessoas que abriram esse diálogo, até apresentaram provas que, para mim, forma um pouco coerentes. Não quis me envolver muito, mas eu gostaria de saber da sua opinião.