Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?)

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 :

Une vidéo de Passe-Science sur le même sujet, avec notamment une belle réduction entre problèmes NP-complets

Écrit et réalisé par David Louapre © Science étonnante

* MES LIVRES :
- "Mais qui a attrapé le bison de Higgs ?"

- "Insoluble, mais vrai !"

* ME SOUTENIR :

* SUR LES RESEAUX SOCIAUX :

* LE BLOG :

[antol]

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é 👌🏼

[yozukil]

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!

[Garrincha]

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.

[JeromeMaquoi]

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

[Abakhan]

Bravo pour la clarté et la fluidité de l'explication ! Tout est super, exemples, ton, diction, une vocation manifestement.

[planchapain]

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)

[jmc]

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.

[almastr]

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.

[DavidDji_]

Super limpide. Bravo. ScienceEtonnance = Boss final de la vulgarisation scientifique francophone sur Youtube.

[theoroubaix]

J'ai fait des études d'informatique théorique et je trouve que c'est particulièrement bien vulgarisé. Très bonne vidéo !

[ardechirpakfar]

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 !

[thomasp]

Bravo ! Sans doute la meilleure vidéo de vulgarisation francophone de YouTube. 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.

[NoxofShadow]

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é !

[samyouanes]

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

[v-table]

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 ^^

[BrunoDARCET]

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.

[kamizole]

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.

[MrSasuke]

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 !

[faouzimohamed]

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.

[etiennelemieux]

C'est la première fois que je vois une explication plutôt claire de ce que signifie P=NP :)
Dans cette idée de démonstration d'impossibilité, j'ai toujours été intrigué par l'affirmation qu'on ne peut découper un angle en 3 parties égales avec une règle et un compas par exemple. Ça me paraîtrait un exemple intéressant pour aborder cette notion de démonstration d'impossibilité à quelque chose de plus simple.