Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?)
ฝัง
- เผยแพร่เมื่อ 16 ก.ค. 2020
- On parle d'un problème d'informatique théorique à 1 million de dollars, et même beaucoup plus si vous l'utilisez pour pirater les banques du monde entier ! Oserez-vous chercher un algorithme qui permette de trancher ?
Détails et compléments dans le billet de blog qui accompagne la vidéo :
scienceetonnante.com/2020/07/...
Une vidéo de Passe-Science sur le même sujet, avec notamment une belle réduction entre problèmes NP-complets
• P vs NP : une question...
Écrit et réalisé par David Louapre © Science étonnante
* MES LIVRES :
- "Mais qui a attrapé le bison de Higgs ?"
www.amazon.fr/gp/product/B07R...
- "Insoluble, mais vrai !"
www.amazon.fr/gp/product/2081...
* ME SOUTENIR :
www.tipeee.com/science-etonnante
* SUR LES RESEAUX SOCIAUX :
Facebook : / sciencetonnante
Twitter : / dlouapre
* LE BLOG :
scienceetonnante.com - วิทยาศาสตร์และเทคโนโลยี
![La formule qui a radicalement transformé la finance mondiale [Black-Scholes]](http://i.ytimg.com/vi/XE7FKLfZzBA/mqdefault.jpg)
J’aimerais bien voir ce format pour les autres problèmes du millénaire, même s’ils sont plus complexes ça pourrait être très intéressant ! Et bravo pour cette vulgarisation très simple à comprendre, les mots sont très biens choisis et l’exposé est bien structuré 👌🏼
Peut-être que tu le sais déjà, mais la chaîne de mathématique de "el jj" a fait une vidéo qui explique l’Hypothèse de Riemann : th-cam.com/video/dNpdMYB8pZs/w-d-xo.html
Ainsi qu'une vidéo qui explique la Conjecture de Poincaré : th-cam.com/video/ayjck76iSOA/w-d-xo.html
Je trouves que ces 2 vidéos sont d'une grande qualité et très compréhensible, mais j'avoue que j'adorerai que David nous parle de d'autres problèmes problèmes du millénaire !
Science Étonnante lui-même a fait une vidéo sur l'hypothèse de Riemann :)
th-cam.com/video/KvculWl-jhE/w-d-xo.html
Oui, El JJ est un maitre absolu pour parler de math purs !!!
@@gregorygrandjean2895 les autres problèmes (à part Navier-Stokes) sont très abstraits et seulement accessibles aux experts. Il semble quasi-impossible de vulgariser la conjecture de Hodge ou BSD. Mais si El jj veut le tenter ce serait génial 😁
Malheureusement, et sans vouloir me montrer irrespectueux, je doute fort que notre cher vulgarisateur en soit capable : L'énoncé de certains des problèmes du millénaire ne sont même pas facilement compréhensibles par des mathématiciens non-spécialisés du domaine, il me semble fort douteux qu'il soit possible d'en faire des vidéos potables pour chacun d'entre eux, encore moins accessibles au grand public.
Cela étant dit, si l'on se contente de simplement parler des enjeux derrières certains de ces problèmes sans détailler les énoncés, il me semble possible de parler au grand public de chacun des problèmes à l'exception de la conjecture de Birch : Les fonctions L sont des objets assez éloignés de ce que l'humain est capable de se représenter.
En faire des vidéos réellement instructives reste cependant un tout autre problème.
Quand on connaît déjà le problème, on ne peut qu'admirer la pédagogie avec laquelle celui ci est amené. Je pense que beaucoup de profs de facs ont des résultats moins bons avec leurs élèves après un cours sur le sujet alors que ces derniers y sont bien mieux préparé que la plupart des viewers de cette chaîne, c'est vraiment remarquable.
Bonjour David.
Je connais ta chaîne depuis 18 ou 24 mois je pense mais je ne crois pas avoir déjà posté de commentaire.
Quand j'ai découvert ta chaîne je me suis abreuvé petit à petit de tes vidéos qui sont toujours passionnantes et claires.
Mais celle-ci m'a vraiment bluffé.
Quand tu as commencé à nous exposer le sujet je me suis dit qu'il allait falloir s'acrcocher pou ne pas me faire larguer...en effet je suis plutôt nul en maths.
Je n'ai par exemple jamais compris ce qu'était une fonction (2 de moyenne en maths en terminale, bac A3).
Mais ici tout était clair et limpide, incroyablement bien vulgarisé.
J'ai même enfin compris ce qu'est un algorithme (enfin je pense que c'est finalement un simple programme ou une formule de calcul redondant?).
Alors merci pour tout ton travail et j'espère que tu continueras longtemps à nous distiller du savoir de manière aussi limpide.
PS: il y a peu j'ai vu une video faq de toi où tu expliquais que tu es ingénieur et que tu fais ces vidéos et ton blog lors de ton temps libre.
Je trouve d'autant plus remarquable que tu fasses tout cela pour le plaisir de la diffusion de la connaissance et non pas pour gagner ta vie ou devenir célèbre.
Alors encore une fois un grand merci pour tout!
Merci beaucoup, j'aime ce genre de témoignages qui montrent que parfois j'arrive à toucher les allergiques aux maths ;) Merci d'avoir pris le temps de l'écrire !
Pour l'algorithme, c'est bien ça : une suite d'instruction, qui à partir de données en entrées, produit un résultat (et souvent, permet de résoudre un problème)
"J'ai même enfin compris ce qu'est un algorithme (enfin je pense que c'est finalement un simple programme ou une formule de calcul redondant?)."
un algorithme est une suite d'instruction dont le but est d'obtenir un résultat
par exemple si le résultat que tu souhaite obtenir est un gâteau:
* la recette de cuisine est son algorithme
* les "ajouter 30g de sucre" et autres "mettez au four 45min" sont les instructions qui constitue l'algorithme
* le sucre, œuf et autres ingrédients sont les données d'entrée
si c'est l'anneau de sauron il te faut:
* verser le tout dans la montagne du destin, faire mijoter, blablabla (les instructions qui constituent l'algo)
* de la cruauté, de la malveillance et de la volonté de dominer toute vie (donnée d'entrée)
un algo est tout ensemble d'instruction quel qu'il soit, ça peut tout aussi bien passer un coup de téléphone que opérer un patient, (dans tous les cap tu doit appliquer un ensemble d'instructions pour arriver au résultat désiré)
ps: un mauvais enchainement d'instruction, que ce soit parce que tu as oublié de l'appliquer dans le cas de la recette de cuisine ou que le développeur ait mal écris l'instruction dans le cas d'un programme informatique est ce qu'on appel un bug
ça peut être une instruction manquante, en double, faite après une autre alors qu'il aurait fallu la faire avant (tu met les 30g de sucre AVANT de mettre le gâteau au four, et tu n'oublie pas la farine), etc...
la conséquence varie en fonction du bug et il y en a une infinité possible, mais tous ont un point commun => t’empêcher d'obtenir le résultat voulu
ça peut très bien être ton écran qui déconne pendant 1/2 seconde tout comme une fusée qui explose au décollage (oui oui c'est déjà arrivé^^)
A peu près ça pour l'algorithme. Je trouve que l'image de la recette de cuisine est plus pertinent qu'un programme. Ou une marche a suivre. On te file des choses, tu suis l'algorithme, tu obtiens un résultat.
On te file une liste de nombres compatible, il t'en retourne un résultat.
On te donne un ensemble d'ingrédients, tu en fait un plat. Avec les mêmes ingrédients tu peux avoir plusieurs plats différents, car plusieurs recettes a suivre, plusieurs programmes informatiques.
Une fonction c'est simplement un algorithme qui peut recevoir des données et qui va te donner un résultat une fois exécuté. La fonction plusUn(41), qui ajoute 1 au nombre que tu lui donnes en paramètre (41, dans cet exemple), te donnera un résultat de 42. Une fonction peut recevoir différentes données et exécuter tout un tas d'opérations qui peuvent différer selon les données reçues. En mathématiques, on étudie des fonctions qui transforment des nombres en d'autres nombres, telles que la fonction plusUn(x) (qui se traduirait par f(x) = x +1 en mathématiques, x étant le nombre que tu souhaites transformer, mais qui n'est pas très intéressante...), ou la fonction racineCarrée(x), ou tout type d'opération mathématique plus ou moins complexe. L'idée étant de comprendre comment les nombres réagissent à la transformation opérée, de repérer des nombres qui donnent des résultats intéressants (souvent 0), ou de trouver des limites à la fonction (par exemple, certaines fonctions ne donneront jamais comme résultat un nombre au dessus d'une certaine valeur, et certaines fonctions donnent des résultats s'approchant de l'infini autour de certaines valeurs...). En informatique, la fonction age(Capitaine) te donnera comme résultat l'âge du capitaine... ou de n'importe qui, tant que les données sont dans un format lisibles par la fonction. Mais on pourrait aussi changer l'âge du capitaine avec une fonction changerAge(Capitaine, 42). Ainsi, si ta fonction est bien codée, tu enregistreras quelque part que l'âge du capitaine est 42 ans et ta fonction te reverra un résultat qui te dira "c'est bon, j'ai bien enregistré l'âge du capitaine", et la prochaine fois que tu utiliseras la fonction age(Capitaine), elle te donnera 42 comme résultat. En bref, une fonction en mathématiques, comme en informatique, ça utilise des données/des nombres, ça en fait quelque chose, et ça te donne un résultat à la fin.
Ayant un master en informatique, j'ai suivi un cours de calculabilité et de complexité dans lequel j'ai notamment vu ce que tu expliques dans ta vidéo. Quand j'ai vu le titre, je me suis demandé comment tu allais faire pour expliquer de manière claire et précise des notions aussi théoriques. Et je sidéré par ton explication! Elle est extrêmement simple sans trop l'être, claire et tes exemples sont pertinents. Bravo! :D
ce serait excellent @EcienceEtonnante ! :D
Bravo pour la clarté et la fluidité de l'explication ! Tout est super, exemples, ton, diction, une vocation manifestement.
A chaque vidéo je me dis qu'il ferais un excellent prof.
@@alidigitali9091 Ce serait même dommage qu'il n'enseigne pas. En tout cas on peut profiter de ses vidéos !
Moi, j'avais imaginé qu'il serait le nouveau Michel Chevalet, le big boss de la vulgarisation scientifique à la télé, mais ce n'est peut-être pas son but. Il est hyper doué et cultive son talent mais sans aller jusqu'au bout. Comme disent les ninjagos, "exploiter son plein potentiel"! lol
Y'a pas à dire, cette chaine selon moi domine le ytb science français. C'est clair, imagé et maths-haters-friendly.
Vidéo très chouette.
Pouvoir à ce point rendre intéressant et compréhensible par tout un chacun des sujets normalement accessibles qu’à une minorité c’est du grand art et David le réussi avec brio à chacune de ses vidéos. Bravo et merci.
J'ai fait des études d'informatique théorique et je trouve que c'est particulièrement bien vulgarisé. Très bonne vidéo !
Bonjour, l'informatique théorique m'intéresse, et j'aimerais savoir quel cursus vous avez suivi.
@@generix1240 Coucou, ça m'intéresse aussi ! Si vous avez des liens, ressources à me proposer... Je suis preneur !
@@generix1240 La plupart des études informatiques sont surtout pratiques, mais les cursus à la faculté, comme des licences en informatique ou encore des cursus orientés informatique théoriques à la fac sont optimales pour les connaissances théoriques
while (1) : malloc (1000)
en C, ce code a fait choquer notre enseignant au lycee quand un ami a suivi les recommandations d'un nerd qui se moquait de lui
Une bien belle présentation.
Quand je juge à partir du domaine que je maîtrise bien (informatique, algorithmique), je mesure la capacité de bonne vulgarisation (et j'en deviens envieux).
Merci.
Incroyable , je suis étudiant en informatique et pour tout te dire, ton explication du problème était vraiment limpide, tu fais un excellent travail de vulgarisation et il ne manque pas grand chose ! Merci beaucoup pour toutes ces vidéos et continue comme ça ^^
Super limpide. Bravo. ScienceEtonnance = Boss final de la vulgarisation scientifique francophone sur TH-cam.
Merci :-)
Expliquer la complexité des algos, P, NP, NP-complet en 20 minutes et de façon aussi claire et compréhensible... Excellentissime !... comme toujours. BRAVO et continue !
Vraiment excellente vidéo c'est toujours d'une clarté exceptionnelle. Merci pour le travail !
Il se trouve certains des sujets de vos vidéos deviennent des sujets de recherches et que ça aide beaucoup sur la compréhension sur ceux-ci. En tout cas, pour moi, votre chaine m'est très pratique. Elle fait surgir la passion sur les "Domaines" que vous explorez.
j'ai pris l'habitude de toujours te mettre un pouce bleu avant même de regarder tes vidéo . autant dire que tous ce que tu fais sur cette chaine est une valeur sûre . à chaque fois je me régale et je regarde en boucle .Merci pour ce super travail , c'est un régal
Bravo ! Sans doute la meilleure vidéo de vulgarisation francophone de TH-cam. Réussir à passionner avec la même vidéo des néophytes mais aussi des personnes, plus expérimentés en sciences, qui redecouvrent le problème est un exploit. L'exposé est clair, simple sans être simpliste, et attire la curiosité. Quelle pédagogie et quelle passion !! Bravo et merci.
Dans les commentaires je suis tombé sur au moins 20 génies qui viennent de résoudre ce problème "facile", les gens n'ont peur de rien xD
Merci pour ce travail de qualité accessible gratuitement ❤
J'ai suivi toute ta vidéo et vraiment bravo, tu expliques les choses de façon tellement claire et simple !
J'avais suivi un cours d'ordonnancement de production en dernière année d'école d'ingénieur, et là j'ai mieux compris la classification des algorithmes en 30 minutes que mes profs avaient essayé de nous l'expliquer en un semestre de cours !
Une vidéo de 30 min qui en a l'air 5 tellement c'est clair et intéressant. C'est comme de la meditation
Merci j'avais déjà entendu parler de ce problème mais sans jamais comprendre de quoi il s'agissait. Comme d'habitude c'est super clair et détaillé :)
Excellent ! Première fois que j'arrive à enfin comprendre P=NP! Il faut absolument faire une vidéo pour chacun des 6 autres, s'il te plaît !
J'aime toujours autant la clarté derrière l'explication simple de problèmes bien complexes, merci :D
Très agréable de t'entendre parler d'informatique, et encore plus sur des problèmes sur lesquels j'ai un peu travaillé. Et excellente vidéo, comme toujours !
Réussir à me tenir 27:18 devant une vidéo de ce genre représente un exploit en soi, je peux vous l'assurer. Je suis beaucoup plus à l'aise avec la littérature ou le théâtre. Mais le plus fort tient dans la constance de mon intérêt jusqu'à la fin de la vidéo. Ça, ça mérite son pouce sans hésitation. J'en reste sur mon fondement. Bravo et merci.
Merci !
"Ça se trouve c'est vous qui allez le trouver..."
Je te remercie de ta confiance mais ne te fais pas trop d'illusions quand même 😂😂
mon cerveau fume.
Ya des têtes après la j suis a l apéro si je comprend tout déjà c beau
on ne sait jamais, regarde George Dantzig... par contre maintenant tu sais que c'est difficile à prouver, tu aurais dû essayer AVANT de regarder la vidéo ^^
Je vais chercher un peu mais qu’il compte pas trop sur moi non plus 😂
@Waldel Martell sur Betclic? Tiktok?
Science étonnante c'est comme un restaurant gastronomique, c'est pas tous les jours que tu peux en faire un, tu sais jamais trop quand ca va tomber (a moins que j'ai loupé un truc sur les parutions) mais quand ca tombe... Pu*** la qualité du truc... à mon sens le meilleur vulgarisateur fr sur youtube , et pourtant la concurrence est sévère (et que ce soit dit, je suis et j'adore un paquet de vulgarisateur qui font un taff vraiment incroyable)
Merci !!
(J'essaye d'en faire une par mois)
Un grand bravo et un grand merci pour ce travail titanesque au fil des vidéos qui permet de rendre accessible et passionnant ce qui pouvait nous rebuter jusque là au vu de la complexité du thème. Contenu qui frôle la perfection par un vidéaste passionné et passionnant. Merci de nous ouvrir ces horizons là
Toujours aussi clair et intéressant. J'adore tes vidéos.
J'ai beau avoir vu ce problème à la fac, l'avoir compris. C'est un plaisir de le voir réexpliqué si bien. Ça m'a permis de percevoir plus de détails autour du sujet en lui-même et ses implications ( comme le fait qu'il pourrait tout aussi bien n'y avoir aucune application pratique de trouver un algo polynomial car trop lent ).
Et pour une fois que je connais bien un sujet que tu traite, c'est intéressant de le voir si bien vulgarisé !
Félicitations ! Toujours un très grand intérêt à voir vos vidéos.
Il me semble très intéressant de faire profiter mes élèves du secondaire.
Bravo ! Une variété extraordinaire de sujets aussi passionnants les uns que les autres.
Merci pour cette video, toujours au top de la qualite. Simple, clair et efficace.
J'ai presque tout compris, vous êtes très bon comme d'habitude! Merci!
Y a des vidéos où t'as envie de mettre 10 pouces bleus :-)
celle la en fait partie!
Ou plutôt N pouces bleus.
@@Hyrkhnoss1 si on montait les enchères, 2 puissance N pouces bleus
Il y a pourtant des "mono-neuronés" frustrés qui arrivent à mettre des pouces rouges sur ce genre de vidéo plus qu'excellente...
Seulement 10!!!
Remarquable comme d'habitude. Je fais de la recherche en épistémologie, et vos vidéos synthétisent merveilleusement les domaines abordés. Mille mercis à vous!
Super vidéo sur un des problèmes les plus passionnants ! Tout est clair, la qualité est top !
Mon ancien prof d'algorithmique a l'habitude de dire à ses élèves "J'espère que P/=NP sinon on est tous au chômage !"
haha j'aime beauoup
Vermouth mdrrrr😂
Tellement clair et bien expliqué, bravo !
0:47 Si on cherche le plus petit avec que des nombres à 3 chiffres, chercher d'abord si y'en a dans les 100, y'en a, donc ne chercher QUE dans les 100.
7:28 Bah c'est facile, suffit de faire la proportionnalité prix/poids pour chaque objet et prendre en priorité ceux où le prix au kilo est le plus élevé...
Objet 1: 2400/12 = 200
Objet 2: 500/4 = 125
Objet 3: 3000/20 = 150
Objet 4: 1000/3 = 333,333...
Objet 5: 4000/23 = Environ 175
Objet 6: 1200/8 = 150
Objet 7: 2000/12 = 166,666...
Objet 8: 2000/3 = 666,666...
8 = 2000€, 3 Kgs +
4 = 3000€, 6 Kgs +
1 = 5400€, 18 Kgs +
5 = 9400€, 41 Kgs +
7 = Trop de poids donc suivant !
3 = Trop de poids donc suivant !
6 = 10600€, 49 Kgs
C'est souvent le postulat de départ qui est erroné.
Tellement clair et passionnant à la fois! Merci David!!
C’est absolument brillant! Tes vidéos nous permettent d’appréhender des problèmes pour lesquels il nous faudrait normalement un temps exponentiel par rapport à leur complexité, en un temps linéaire à celle-ci.
Autrement dit, tu nous rends moins cons.
Vidéo très intéressante comme d'habitude ! La seule question que je me pose c'est comment est-ce que le gars a fait pour rentrer le piano dans son sac pour le problème du sac-à-dos...
Merci :) j'adore apprendre en t'écoutant :)
Toujours autant intéressantes ces vidéos, excellentes explications, illustrations pertinentes, même si certains concepts me dépassent un peu il y a toujours quelque chose à prendre (et à apprendre).
🙏 🙏 😊
ohlolo j'ai appris tout ca en classe et plusieurs livres, mais la chapeau!
ca fait tellement plaisir de voir cette presentation si claire et accrocheuse!!
12:14 En informatique on dit souvent "en temps et resources polynomiales". En effet, on a certains problèmes qu'on sait résoudre avec un nombre polynomial d'operations à condition d'avoir une mémoire exponentielle. En pratique informatique, ça revient au final un peu au même parce que si tu dois lire ou écrire une partie non-négligeable de cette mémoire de taille exponentielle à chaque opération, ton opération n'est plus vraiment élémentaire et le temps nécessaire à appliquer l'algorithme est vraisemblablement exponentiel même si le nombre d'étapes ne l'est pas.
C'est pertinent en informatique parce que ramener un algorithme à des opérations vraiment "élémentaires" est inutilement fastidieux, pour mesurer sa complexité tu comptes plutôt en gros le nombre d'opérations "simples" ayant chacune une complexité connue et faible.
En regardant la vidéo, je me suis fait la réflexion : je pense que passer rapidement sur le sujet de la complexité spatiale aurait été intéressant, en plus de spécifier que la complexité dont il parle est la complexité temporelle :) Ainsi qu'une brève introduction aux notions Grand O, Oméga et Têta et éventuellement du fait qu'on néglige les constantes/coefficients lors du calcul de la complexité. Après c'est peut-être trop précis pour une vidéo de vulgarisation :p
@@Riku4554 Justement toute la subtilité de la vulgarisation est de ne pas utiliser les notions pour ne pas s’embarrasser avec leurs explication, sans pour autant empêcher la compréhension du problème globale.
Par ailleurs, même si la complexité spatiale et aussi importante on ne peut rien faire si la complexité temporelle est déjà trop élevée, donc pour moi ça n'est pas forcément utile d'en parler.
Je ne vois pas comment tu peux résoudre un problème en temps polynomial avec une mémoire exponentielle. Lire ou écrire une quantité exponentielle de mémoire se fait forcément en temps exponentiel. Après il y a peut être moyen de tricher en exploitant des opérations élémentaires qui n'en sont pas. Algos quantiques peut-être?
@@gubx42 ça dépend comment on définit "opération élémentaire" dans le calcul de complexité en temps: mathématiquement on aura tendance à dire qu'additionner deux nombres est "une" seule opération, que ces nombres s'écrivent avec 1 chiffre ou 1 milliard. Leur stockage en mémoire par contre va être nettement différent.
Mais du coup ça montre que la complexité d'un algorithme décrit mathématiquement, et de sa version informatique concrète, doivent souvent être soigneusement réévalués, car le premier cache des sous-complexités dans le détail de son implémentation dans le deuxième pour ces cas de "grand nombres".
"on a certains problèmes qu'on sait résoudre avec un nombre polynomial d'operations à condition d'avoir une mémoire exponentielle."
non : vue que accéder à la mémoire est une opération, la complexité en mémoire est toujours inférieur ou égale à la complexité en opération.
(dans "complexité en mémoire", je ne parle pas de la taille des entrés. l'algorithme de recherche du min a une complexité mémoire de O(1))
(et il y a bien des situations où utiliser beaucoup de mémoire peut faire gagné du temps)
Du grand art, comme d'habitude. Merci ! Je suis couturière, toutes ces notions et questions sont très très loin de mon univers et... de mon niveau en maths surtout... mais c'est passionnant !
Merci d'avoir pris le temps de l'écrire ! :-)
C'est passionnant, merci beaucoup pour toutes ces explications et tout le temps que vous devez passer pour préparer tout cela
Master en vulgarisation! On ressort de la vidéo en ayant l'impression d'avoir tout compris d'un problème réservé a quelques spécialistes. Bravo!
Super video (comme d'habitude :) ), qui arrive à expliquer clairement, et je crois sans faire de simplifications abusives (mais je ne peux pas pleinement juger ça, je ne suis pas un spécialiste).
Le concept de complexité est souvent malheureusement mal compris et mal appliqué par les ingénieurs en informatique, même pur des choses beaucoup plus utiles au quotidien pour eux que le problème P=NP.
Dans mon travail je fais régulièrement passer des tests de recrutement à des ingénieurs en développement logiciels, la plupart du temps avec une solide formation en maths (grande école d'ingé et/ou doctorat en informatique/physique théorique/maths), et si la plupart connaissent le concept de complexité, il y en a un nombre étonnant qui, en pratique, n'arrivent pas, par exemple, à différencier un algorithme de tri de complexité n² ou n log n quand on leur montre le code des deux. Bref, pour eux, ça reste un truc de plus qu'on leur a appris en cours mais qui sert à rien dans leur vrai métier.
"Master Big O" , comme dirait Gayle
Mais comment fait-il ? Comment explique-t-il aussi bien ? Super vidéo encore une fois :)
On l'appelle, le DOCTEUR.
@@antoine3086 ou aussi el proffeseur (casa de papel)
Moi je dirais que c'est grâce à...LA FORCE !....ok je sors :(
C'est un genie il ressemble a Mark Zuckerberg
@@rubinho641 Ca c'était pas gentil :D
Fabuleux. J'avais survolé cette partie dans mes cours d'info.
Je connais très bien la complexité, mais cette histoire de P=NP et problèmes NP-complets malgré les heures de cours je n'arrivais pas à trouver ça intéressant et j'ai pas vraiment cherché à comprendre...
En 25 minutes tout est incroyablement clair et j'ai une illumination sur tout ça.
Tu es vraiment une perle t'arrête jamais!
Toujours aussi bien, clair, instructif, même pour un sujet aussi abstrait. Bravo !
Petite addition. La limit n*log(n) pour le tri viens du fait qu'il y a n! order possible, et donc qu'il faut produire ln(n!) ~ n*ln(n) bits d'information pour choisir un ordre.
Cela prove qu'on ne peut pas faire mieux que n*ln(n) pour les tri par comparaison, étant donné qu'on comparaison ne produit qu'on bit d'information, et qu'il en faut donc n*ln(n) pour ordonner une liste.
Mais ceci n'est pas forcement le cas. Il existe des méthodes de tri pour des objects specifiques, par exemple, les nombres de 32 bits, qui produisent plus d'un bit d'information par operation et donc peut d"passer n*ln(n). C'est le case par exemple du radix sort qui peut trier des entiers en temps linéaire.
Pour la factorisation, il y a aussi des algo qui sont sub exponentiel. Par exemple: en.wikipedia.org/wiki/General_number_field_sieve
C'est pourquoi le monde de la cryptography évolue vers les courbes eliptiques plutot que la factorisation.
(pour des tris d'entiers sur 32bits) pour dire que la complexité du radix sort est inférieure à n*ln(n), il faudrait que tu tries plus de 2^32 valeurs, soit 16Go de data
complexité du radix sort : O(w*n) avec w le nombre de bits pour stocker ta clef, ici 32 bits
pour que w*n < n*ln(n)
il faut que ln(n) > w
soit ln(n) > 32
donc n > 2^32
dans le même cas, on a le tri par comptage qui fonctionne aussi très bien pour les entiers, avec une complexité linéaire en asymptotique
@@florentgermain8633 Tu fais plusieurs passes, pour des 32bits, une table d'indexation de 8 bits suffit (256 entrées), puis tu fais 4 passes en commençant par l'octets de poids fort de chaque valeur. Soit 4n, avec 256 valeurs tu obtiens déjà 1024 contre 256*log(256) = 1419.
fr.wikipedia.org/wiki/Tri_par_base
Difficile de le gagner ce million... mais pour toi, il approche tres vite !! ;) Largement mérité !! Continue
Toutes tes vidéos parlant d'informatique sont vraiment incroyables ! J'ai pu comprendre le problème NP=P sans passer 3h à scroll Wikipedia, merci !
Merci, facile à comprendre avec tes explications. C’est cool. Bravo pour cette vidéo.
Salut David ! Il y a un sujet qui est peu parlé dans le monde , c’est celui de la mort , en point de vu physique , j’aurais aimer savoir s’il y a eu quelque réponse. Le problème , c’est que je ne sais pas si ça collera au sujet de ta chaîne , mais bon qui tente rien n’aura rien . Sinon tu fais des vidéos avec des contenu s incroyables , j’adore la physique , les théories maintenant que je regarde tes vidéos depuis 2-3 ans environ . Donc bonne Continuation !
Je pense que le sujet de la mort collerait plus à quelqu'un touchant d'avantage à la biologie qu'à la physique, je pense à DirtyBiology par exemple
TekPike Oui , c’est exactement ce que je pensais , du coup je posais la question
Eostream C’est ce que je pensais aussi , j’étais pas certain mais je voulais juste savoir s’il n’y avais pas de truc etc...
Petite correction : la valeur Nlog(N) est vraie uniquement pour les tris par comparaisons. (Il existe des tris qui ne sont pas des tris par comparaison)
Et encore cela n'exclues pas de niké un code avec du dropfish ( sachant que pour qu'un tipeu se hack lui même il faut avoir du temps ET de l'argent à foutre en l'air ;-) ).
Comme toujours tes vidéos nous rappellent pourquoi ta chaîne s’appelle ainsi.
Merci :)
Merci pour vos vidéos et votre travail, je vous ai découvert il y a peu de temps et visionne l'ensemble de vos vidéos parfois plusieurs fois. N'ayant pas du tout la fibre scientifique, j'avoue que vos vidéos me passionné et me font rêver, je touche du doigt la magie et l'émerveillement que procure la science, merci encore
"C'est pas parce qu'ils sont nombreux à avoir tord qu'ils ont raison !" :D
Tort ? D'ailleurs, seul le tort tue.
Dans ce cas c'est qu'ils ont raison d'avoir tort (©Le chat)
@Имран хадис je l'ai prouvé également. Hélas, je n'ai pas la place nécessaire dans ce commentaire pour l'écrire entièrement.
Bravo, super video ! Ayant suivi un cours sur le sujet, je suis impressionné par ta capacité à résumer et expliquer le sujet de façon concise et complète, sans pour autant s'attarder sur les détails assez techniques et plutôt exotiques de cette théorie (je pense aux machines de Turing non déterministes, les problèmes indécidables tel que celui de l'acceptation, les démonstrations de réductions polynomiales à donner des cauchemars...)
Passionnant et toujours aussi bien vulgarisé... bravo et merci pour ton travail !
J'adore vraiment toutes vos vidéos.
Bravo et merci encore pour toutes ces vulgarisation.
Le problème du sac à dos est facile à résoudre : il suffit de prendre le sac de Marry Poppins...
...Mais je ne sais pas ou est-ce qu'elle l'as mis.
Ou celui d'hermione
La plus grande question est : que ce passe t"il si on replie le sac sur lui même
@@noerosier4714 Merlin en avait un aussi
Personne ne parle de Sport Billy ?
Manière vraiment simple et intéressante d'aborder la classe NP, bravo à toi pour la vidéo
Excellente vidéo sur un sujet auquel je viens de m'intéresser hier ! Merci beaucoup pour ces éclaircissements, tes vidéos sont toujours un plaisir !
La vidéo est juste parfaite. Le sujet traité peut sembler très complexe sans s'y pencher mais enfait c'est très simple
Merci David pour cette excellente vidéo !
Y'a ce genre de vidéos sur des représentations d’algorithmes de classement, je trouve ça très reposant ! ^^
th-cam.com/video/kPRA0W1kECg/w-d-xo.html
TH-cam me propose souvent celle-ci en suggestion, je ne peux pas m'empêcher de la re-regarder à chaque fois ! ^^
le bogo sort de cette vidéo me fait toujours exploser de rire
comment devenir fou!
Ah ben tiens nickel, j'arrivais pas à dormir!
celle ci est pas mal non plus th-cam.com/video/vmT3XUBoxiQ/w-d-xo.html
@@orbital_c315 Je ne connaissais pas le terme technique ! 😅 Enfin, je n'imaginais même pas qu'il y en ait un ! ^^ Mais il y en a toujours un, évidemment ^^ Merci !
Les sons choisis en font presque tout le charme oui x)
ça me rappelle mes cours d'informatique :')
Super Merci c'est quand même incroyable la facilité (avec beaucoup de temps et de travail je suppose) que tu as à nous faire comprendre les choses .... bravo je suis fan
C'est grâce a ce que tu fais que je me suis remis à la recherche et à la lecture scientifique pour terminer mon memoire de fin d'études.. vraiment big up a toi
On pourrait aussi envisager que P=NP soit indécidable. Un exemple de problème indécidable est de savoir si un algorithme quelconque s'exécute en un nombre fini d'étapes (autrement dit, qu'il se termine toujours). Si P=NP est indécidable, cela signifierait que ni P=NP, ni P≠NP ne puissent être démontrés. Très "méta". 😏
Jveux pas dire de connerie mais il me semble que dans ZF de toute façon le problème de "j'ai un théorème est ce qu'il existe une preuve" est indécidable. Maintenant est ce que P=NP est indépendant de ZF je sais pas
@@leGEEK84 ZF?
@@leGEEK84 Je ne suis pas sûr que tu aies la bonne interprétation des théorèmes d'incomplétudes. Le premier dit "il existe des énoncés indécidables dans ZF". Le deuxième dit "ZF ne démontre pas sa propre cohérence" (ou plutôt si mes souvenirs sont bons, il dit que si ZF montre l'énoncé qui encode la cohérence de ZF dans le language de la théorie des ensembles, alors il démontre aussi sa négation).
@@MartijnCoppoolse c'est l'axiomatique de Zermelo Fraenkel sans axiome du choix, c'est une axiomatique assez standard en.m.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory
17:40 Pour les tris basés sur des comparaisons seulement non?
J'allais le faire remarquer. Il existe un algorithme en n loglog n qui trie une liste de nombres de façon déterministe. Pour les tris stochastique, la question d'un algorithme en O(n) est encore ouverte.
@@Varmin123 lien ?
@@thunderphoenix2140 si tu veux un exemple, cherche le bucket sort, sinon je n ai pas compris ta réponse ahah ^^
(Mais tout est déterministe ici, on se base juste pas sur les comparaisons)
Bonne soirée!
Oui je me suis limité à ça pour ne pas complexifier :-)
Toujours au top ! Merci pour cette vidéo 👍
Je dis : Bravo ! C'est une excellente vulgarisation, même si on devine quelquefois des simplifications qui doivent inquiéter les spécialistes. Le but essentiel est atteint : avoir réussi à faire comprendre de quoi il s'agit en quelques dizaines de minutes. Merci David !
7:10 Le problème du sac a dos est mal expliqué, car s'il faut juste ramener une somme supérieure à 10000€, il suffit de parcourir la liste, calculer les €/kg, trier cette nouvelle liste par ordre décroissant. Parcourir cette nouvelle liste des €/kg triés et retenir les objets au fur et à mesure sans dépasser la limite de poids (d'abord le plus fort €/kg, puis le suivant s'il rentre, sinon le suivant s'il rentre etc.). Le vrai problème du sac a dos réside dans le fait qu'il faille MAXIMISER la somme accumulée (et pas seulement dépasser une limite arbitraire). Sinon très bonne explication!
P=NP porte sur les problèmes de décision donc ça me parait normal qu'il parle de cette variante du problème du sac à dos
Ben non justement, la méthode heuristique qui consiste à trier par densité ne garantit pas de résoudre le problème. Et comme je l'explique dans le billet de blog, on considère bien le problème de décision (respect d'une contrainte) et pas celui d'optimisation.
@@ScienceEtonnante bon je vais y réfléchir un peu plus
@@Muzkaw On ne peut pas vérifier une solution au problème de maximisation en temps polynomial, du coup cette version est plus dure que NP (on dit qu'il est NP-difficile).
*Moi, arrivé à **16:42* "La vache, j'espère que vous avez une chute à tout ça parce que l'intro est comac !"
Ah c'est sûr c'est pas Jo le rigolo !
Ce que j aime avec tes vidéos c est que la question est vite répondue. Sinon super vidéo comme d habitude très claire sur un sujet pas facile :)
Le meilleur vulgarisateur de TH-cam, encore une fois une vidéo excellente et parfaitement expliquée (je suis développeur de logiciels). Merci David pour l'incroyable boulot, merci de nous ouvrir à la science. Ton talent est indéniable !
avec n=1 ou p=0, on a bien p=np
à moi le million !!!
*se réveille*
mince...
mec t'aura pas le million comme cela , le binaire est une base pour le JS mais byte c'est avant tout un taux de change TRES PERSONNEL ... #troll *! #geEk. ..
@@llll3148 tu sais ct une blague
21:37 le premier veut voir le numero 19et ne veut pas le voir haha
De plus en plus exceptionnel, merci pour ce travail de qualité.
c'est toujours tellement intéressant vos videos!! merci beaucoup
Zut, je n'ai toujours pas compris ce qu'était un sudoku ...
Peut-être que c'est indécidable lol, P=NP serait donc le plus grand troll que le monde ait connu.
Le prix récompense aussi la preuve de l'impossibilité de démontrer si P=NP ou non.
C'est arrivé avec l'hypothèse du continu, l'un des 23 problèmes de Hilbert
@@benjamilou Et David en a parlé dans une vidéo, celle sur l'infini il me semble
P=NP, la solution c'est N=1, merci au revoir 🤣
@@Raiku347 t'as oublié P=0 :p
Bravo, magnifique sujet et brillantes explications !
Ca fait plaisir de voir que cette vidéo est en tendances
Likez mon commentaire si vous voulez qu'ils fasse une vidéo sur l'équation de Navier-Stokes 😂
Non
⬆️ Likez ce commentaire pour le rendre jaloux 😅
on est plus en 2011 narvalo
Inuké j’aime ce mot mdr. Par contre @le renoi du quartier a raison c’est quand même intéressant
26:30 "Si la plupart des chercheurs semblent d'accord sur le résultat, ça n'est pas pour autant qu'on sait le démontrer, et rien ne dit qu'on arrivera à le faire un jour." **wink wink regardez mon épisode sur l'incomplétude de Godel wink wink**
J'attendais le voyageur du commerce depuis le début :).
Superbe vidéo. Sachant que ce cours est de niveau master ! Tu l'illustres tellement bien .. après moi je connais déjà donc je ne sais si ma voix compte mais je le dis quand même :)
Vos explications sont lumineuses et fabuleuses : pas besoin d’algorithmes pour mesurer votre talent de vulgarisateur intelligent et bienveillant !
Est ce que vous aimeriez vulgariser votre thèse.
Il l'a déjà fait, c'est la vidéo sur la gravité quantique à boucles.
Si et seulement si on fait de l'art go
22:22 pour le mal de crâne.
C'est écrit de manière formelle, mais la lecture n'est pas si difficile une fois que l'on connaît la signification des symboles
@@kolowi Je pensais plus à ce qui est dit à l'oral : "problème abstrait de satisfaction de formule en logique booléenne". Je veux dire tu me sors ça ou tu parles chinois c'est pareil XD
@@berengerlefort8612la logique booléenne consiste juste à exprimer les choses comme une combinaison d'affirmations avec des *OU* et des *ET*
Les booléens en info: 1, 0, ou -1
Bonjour David, merci pour cet épisode très clair et ordonné, bravo pour avoir réussi à expliquer simplement un problème aussi complexe.
Personnellement je tiens un blog de vulgarisation scientifique et tes vidéos m'ont aidé à structurer mes explications.
Merci pour le coup de main, et pour les épisodes ;)
Bonne continuation !
Merci David. Tu es simplement parfait👌👍
Bonne vidéo, cependant tu confonds « il faut » et « il suffit ». Non il ne « faut » pas trouver un problème qui serait un contre-exemple pour demontrer que P est different de NP, puisqu’il existe d’autres facons de faire (par exemple demontrer qu’un contre exemple P existe, sans pour autant l’expliciter) ; en revanche, cela suffit. C’est pas grand chose, mais c’est important dans ce genre de sujet.
Bien vu !
Oh tiens une nouvelle notification du boss final de la vulgarisation scientifique
Merci David pour cet exposé brillant ! Tout y est, c'est parfaitement structuré, bravo et encore merci !
merci infiniment pour cette super vidéo !!! tu es génial !
...et je vois que tu a bientôt atteint les 1 millions ! bravo !