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

[@antol1558]

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

[@gregorygrandjean2895]

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 : kzbin.info/www/bejne/mn_TlYCPd52jkNU Ainsi qu'une vidéo qui explique la Conjecture de Poincaré : kzbin.info/www/bejne/l6rNlJ5ta86GhaM 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 !

[@timothemalahieude5076]

Science Étonnante lui-même a fait une vidéo sur l'hypothèse de Riemann :) kzbin.info/www/bejne/gafGpp-NoZKdnqc

[@shift4156]

Oui, El JJ est un maitre absolu pour parler de math purs !!!

[@patrick_g350]

@@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 😁

[@Alphabetatralala]

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.

[@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!

[@ScienceEtonnante]

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 !

[@mben4257]

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)

[@ulquiorraschiffer1327]

"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é^^)

[@MrZeDeathcaller]

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.

[@Obikin89]

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.

[@7Garrincha7]

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

[@MickaelJi]

ce serait excellent @EcienceEtonnante ! :D

[@Abakhan]

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

[@alidigitali9091]

A chaque vidéo je me dis qu'il ferais un excellent prof.

[@Abakhan]

@@alidigitali9091 Ce serait même dommage qu'il n'enseigne pas. En tout cas on peut profiter de ses vidéos !

[@olivierorsola]

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

[@jmc6319]

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.

[@almast3r933]

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.

[@theoroubaix9646]

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

[@generix1240]

Bonjour, l'informatique théorique m'intéresse, et j'aimerais savoir quel cursus vous avez suivi.

[@samyouanes7194]

@@generix1240 Coucou, ça m'intéresse aussi ! Si vous avez des liens, ressources à me proposer... Je suis preneur !

[@zorglubgaming8670]

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

[@WithScienceAsMySheperd]

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

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

[@ardechirpakfar6823]

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 !

[@planchapain1]

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)

[@ScienceEtonnante]

Merci !! (J'essaye d'en faire une par mois)

[@samyouanes467]

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

[@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.

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

[@faouzimohamed7458]

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.

[@thomasp2731]

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

[@trollenz]

"Ç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 😂😂

[@Blanquette]

mon cerveau fume.

[@soldatlouche8130]

Ya des têtes après la j suis a l apéro si je comprend tout déjà c beau

[@pierrel.3937]

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

[@Azenamouke]

Je vais chercher un peu mais qu’il compte pas trop sur moi non plus 😂

[@chaussette1er]

@Waldel Martell sur Betclic? Tiktok?

[@MrSasuke67]

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 !

[@philippenachtergal6077]

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.

[@Riku4554]

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

[@Kataklysme666]

@@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.

[@gubx42]

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?

[@reinf4430]

@@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".

[@paulamblard3836]

"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)

[@FavoritesAG]

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

[@fv6876]

Y a des vidéos où t'as envie de mettre 10 pouces bleus :-)

[@thepigboss3966]

celle la en fait partie!

[@Hyrkhnoss1]

Ou plutôt N pouces bleus.

[@ttarazradasdadadadad]

@@Hyrkhnoss1 si on montait les enchères, 2 puissance N pouces bleus

[@castorix31]

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

[@TheSaadfc]

Seulement 10!!!

[@mrcrazybullet]

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

[@DavidDji_1989]

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

[@ScienceEtonnante]

Merci :-)

[@pierrelacombe4757]

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 !

[@IncroyablesExperiences]

Tellement clair et bien expliqué, bravo !

[@lemalademental316]

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

[@justicetout]

C'est souvent le postulat de départ qui est erroné.

[@PaperFox-ne7ms]

​@@lemalademental316cet algorithme ne fonctionne pas dans le cas suivant: Objet 1: 8000€, 49kg Objet 2: 200€, 1kg Objet 3, 7000€, 10kg

[@4themusiclovers]

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!

[@deadalnix]

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.

[@florentgermain8633]

(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

[@TheNvipy]

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

[@TheBendith]

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!

[@jpa6022]

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.

[@aymarddjasrabe9799]

"Master Big O" , comme dirait Gayle

[@taghazog]

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!

[@kamizole6685]

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.

[@ScienceEtonnante]

Merci !

[@etiennelemieux472]

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.

[@ericgrenier6591]

Vraiment excellente vidéo c'est toujours d'une clarté exceptionnelle. Merci pour le travail !

[@leaadam]

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

[@daemonsoadfan]

Mais comment fait-il ? Comment explique-t-il aussi bien ? Super vidéo encore une fois :)

[@antoine3086]

On l'appelle, le DOCTEUR.

[@rulesamx3567]

@@antoine3086 ou aussi el proffeseur (casa de papel)

[@datajedi5217]

Moi je dirais que c'est grâce à...LA FORCE !....ok je sors :(

[@rubinho641]

C'est un genie il ressemble a Mark Zuckerberg

[@kirkanos771]

@@rubinho641 Ca c'était pas gentil :D

[@fishpronos]

Tu es sans aucun doute le meilleur du monde pour nous faire découvrir un thème dont on a zéro connaissance sur le sujet et d'une facilité déconcertante ... Je pense justement que faire des vidéos de ton genre on peut croire que c'est du P mais je pense vraiment que c'est un NP complet... Petit parallèle métaphorique avec ta vidéo. Ce que je veux dire en résumé c'est que faire des vidéos de ton genre c'est justement un énorme travail de faire du simple avec du compliqué et ça c'est tout toi. Donc P=NP vrai et je le démontre avec les vidéos de sciences étonnantes. Merci pour tout ton travail ! Et merci aussi pour le million de dollars lol

[@laurenceb.6233]

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 !

[@ScienceEtonnante]

Merci d'avoir pris le temps de l'écrire ! :-)

[@distil47]

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 !

[@antoine8563]

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

[@ryukami583]

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à

[@petitkus4408]

Merci pour ce travail de qualité accessible gratuitement ❤

[@lmwak1005]

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 !

[@svadilfarikenoby7126]

J'ai presque tout compris, vous êtes très bon comme d'habitude! Merci!

[@thomasl1801]

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 !

[@QuentMeun]

Toujours aussi clair et intéressant. J'adore tes vidéos.

[@rotters2556]

Je fais des études en mathématiques et informatique. C'est de loin la meilleure explication du problème que j'ai entendu!!

[@TyrranoAlpha]

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

[@crocodil.13]

Tkt je suis la pcq j'avais besoin de me rappeler que je suis une merde en math😂

[@aetzazashraf3076]

La clarté de l'explication est assez incroyable.

[@allfamax3]

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)

[@llll3148]

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 ;-) ).

[@bryangui4208]

Je n'exagère pas quand je dit que tes vidéos de vulgarisation scientifique sont les meilleures sur internet. Je pouvais comprendre tous bien que je ne sois pas un francophone natif (c'est peut-être evident en lisant mon commentaire). Bravo!

[@shift4156]

Difficile de le gagner ce million... mais pour toi, il approche tres vite !! ;) Largement mérité !! Continue

[@Billou]

Quelle claque d'écouter ce genre de vidéos. On pourrait même dire que faire une vidéo aussi intéressante que cela est un problème NP; mais démontrer qu'elle est aussi qualitative et intéressante est un problème P Bravo pour le travail fourni !

[@vermouth1542]

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

[@benoit721]

haha j'aime beauoup

[@quentinmarret466]

Vermouth mdrrrr😂

[@mathildereynaud3468]

Encore une vidéo incroyable. Même si comme moi on a déjà fait beaucoup de maths et qu’on connaît ce problème, on apprend toujours de nouvelles choses grâce à vos vidéos. C’est si clair et bien expliqué je ne sais pas comment vous faites, chapeau bas ! :)

[@ScienceEtonnante]

Merci beaucoup :-)

[@jerempinch2530]

"C'est pas parce qu'ils sont nombreux à avoir tord qu'ils ont raison !" :D

[@alainrogez8485]

Tort ? D'ailleurs, seul le tort tue.

[@AnttonC]

Dans ce cas c'est qu'ils ont raison d'avoir tort (©Le chat)

[@alainrogez8485]

@Имран хадис je l'ai prouvé également. Hélas, je n'ai pas la place nécessaire dans ce commentaire pour l'écrire entièrement.

[@saidnsiri3487]

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.

[@jojojo9610]

Merci :) j'adore apprendre en t'écoutant :)

[@vagamorneval8451]

Mince j'me suis assoupi sur la fin, voila ce que c'est de regarder un ytb qui parle clairement et simplement d'un probleme complexe , juste avant l'heure du dodo quand on a deja un stock de sommeil en retard. Bon la bonne nouvelle c'est que seul mes yeux se sont momentanément fermé donc je devrais en garder quelque chose. C'etait tres instructif et interressant en tous cas, merci.

[@Muzkaw]

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!

[@hartbook]

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

[@ScienceEtonnante]

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.

[@Muzkaw]

@@ScienceEtonnante bon je vais y réfléchir un peu plus

[@JulienVion]

@@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).

[@ThomasKundera]

Absolument excellent. D'autant plus que j'y ai appris des choses et remis à l'endroit des choses fausses que je croyais sur le sujet (et que je m'étais d'ailleurs dis que je devrais regarder ça de plus pès récemment, voilà qui est fait). Merci.

[@lecrocodile1105]

P=NP, c'est pourtant pas dur à résoudre. Deux solutions : N=1 ou P=0

[@Odranoel.0]

C'est du 2nd degré rassure moi 😅

[@lecrocodile1105]

@@Odranoel.0 Oui. Mais il y a quelques années, j'avais répondu ça assez sérieusement à l'un de mes profs qui essayait d'élargir notre culture G mathématique

[@paulruiz8150]

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 !

[@CcrcOoo]

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 !

[@nini700]

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

[@CcrcOoo]

TekPike Oui , c’est exactement ce que je pensais , du coup je posais la question

[@CcrcOoo]

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

[@maxdebeer4626]

Bonjour, je trouve cet exposé aussi clair que vivant et passionnant, même si je suis un peu largué vers la fin... car, mathématicien amateur, mais pas du tout informaticien, donc peu familiarisé avec les algorithmes. Mais j'y reviendrai, le temps qu'il faut, avec plaisir, jusqu’à ce que plus rien ne m'échappe. Je viens de terminer de poster sur KZbin une proposition de résolution de la conjecture de Goldbach en 5 épisodes sous le titre générique VARIATIONS GOLDBACH. Avis aux amateurs! On a théoriquement besoin de décomposer le nombre pair en facteurs premiers jusqu'à sa racine carrée, mais pratiquement non, car, une fois le principe de la démonstration validé, il est facile de démontrer que ça reste valable jusqu'à l'infini. En fait, cette démonstration s'inscrit dans le principe du "ça ne peut pas ne pas être" : je ne démontre pas vraiment que, pour tout nombre pair, il y a un certain nombre de solutions avérant la conjecture, mais plutôt, qu'il ne peut pas ne pas y en avoir. Peut-on programmer des algorithmes fonctionnant sur ce principe? (comme pour résoudre "économiquement" le problème des chaussettes ou des pots de peinture que je propose épisode 3) Berendans

[@playsong3000]

ça me rappelle mes cours d'informatique :')

[@bestephanehildebrand]

Le meilleur vulgarisateur de KZbin, 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 !

[@Naheulf]

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.

[@thepigboss3966]

Ou celui d'hermione

[@noerosier4714]

La plus grande question est : que ce passe t"il si on replie le sac sur lui même

[@34smiley81]

@@noerosier4714 Merlin en avait un aussi

[@kirkanos771]

Personne ne parle de Sport Billy ?

[@billyboy_45]

*Moi, arrivé à **16:42* "La vache, j'espère que vous avez une chute à tout ça parce que l'intro est comac !"

[@jeremybelot8147]

Ah c'est sûr c'est pas Jo le rigolo !

[@Yroflamme]

Merci beaucoup David ! J'ai enfin compris ce problème dont on me parle régulièrement dans mes études d'informatique... Je n'avais trouvé personne capable de l'expliquer simplement jusqu'ici 😅

[@ARatQuiRit]

Y'a ce genre de vidéos sur des représentations d’algorithmes de classement, je trouve ça très reposant ! ^^ kzbin.info/www/bejne/oYG1cmONZtB4eck KZbin me propose souvent celle-ci en suggestion, je ne peux pas m'empêcher de la re-regarder à chaque fois ! ^^

[@orbital_c315]

le bogo sort de cette vidéo me fait toujours exploser de rire

[@Kataklysme666]

comment devenir fou!

[@samouraimelanine4646]

Ah ben tiens nickel, j'arrivais pas à dormir!

[@samouraimelanine4646]

celle ci est pas mal non plus kzbin.info/www/bejne/rJ63ZIuLd9Srn7M

[@ARatQuiRit]

@@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)

[@tisiphone535]

J'aime toujours autant la clarté derrière l'explication simple de problèmes bien complexes, merci :D

[@charlyisidore]

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". 😏

[@leGEEK84]

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

[@MartijnCoppoolse]

@@leGEEK84 ZF?

[@Pece0]

@@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).

[@leGEEK84]

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

[@guillaumec5932]

Pour ceux qui trouvent ça étonnamment simple à comprendre c'est le moment de s'intéresser à l'informatique ! C'est une filière d'étude qui n'est pas très populaire en nombre d'adhérents mais pourtant très intéressante

[@edelahaye]

Zut, je n'ai toujours pas compris ce qu'était un sudoku ...

[@noubliezpasvotreserviette4263]

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 :)

[@aoe9857]

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

[@Maximetony]

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 !

[@fractalphilosophorum9405]

Peut-être que c'est indécidable lol, P=NP serait donc le plus grand troll que le monde ait connu.

[@Ceelvain]

Le prix récompense aussi la preuve de l'impossibilité de démontrer si P=NP ou non.

[@benjamilou]

C'est arrivé avec l'hypothèse du continu, l'un des 23 problèmes de Hilbert

[@mben4257]

@@benjamilou Et David en a parlé dans une vidéo, celle sur l'infini il me semble

[@Raiku347]

P=NP, la solution c'est N=1, merci au revoir 🤣

[@fractalphilosophorum9405]

@@Raiku347 t'as oublié P=0 :p

[@quantumlife8426]

Superbe vidéo, au final P n'est pas égal à NP si 99% des experts mathématiciens le disent, j'imagine que même si il reste 1% de chance ce dernier n'est composé que de ceux qui croient encore au père noël, mais sait-on jamais le problème reste entier et merci à toi de nous l'avoir si bien exposé, ta vidéo était très intéressante !

[@duoriep]

21:37 le premier veut voir le numero 19et ne veut pas le voir haha

[@DonEdwardHyde]

La conclusion avec l'histoire des sondages est extra, merci :)

[@ThomasLeRuineur]

17:40 Pour les tris basés sur des comparaisons seulement non?

[@Varmin123]

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.

[@thunderphoenixx]

@@Varmin123 lien ?

[@Barioth]

@@thunderphoenixx 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!

[@ScienceEtonnante]

Oui je me suis limité à ça pour ne pas complexifier :-)

[@pituitlechat3807]

Je ne sais pas si tes explications sont parfaite mais j'ai enfin compris l'énoncé de ce probleme! Merci!

[@kepler6393]

Est ce que vous aimeriez vulgariser votre thèse.

[@Ceelvain]

Il l'a déjà fait, c'est la vidéo sur la gravité quantique à boucles.

[@exlinguist]

Si et seulement si on fait de l'art go

[@Tassdo]

Très bonne vidéo. Ayant fait des études d'info théorique j'étais à l'affût pour des trucs faux (pas juste un peu simplifiés, ce qui est obligatoire en vulgarisation) mais j'ai pas trouvé grand chose. La seule chose que j'ai à redire c'est que P et NP sont des classes de problèmes de *décision*, donc le tri par exemple n'est pas dans P ni NP (ce n'est pas un problème de décision). Mais j'avoue que les problèmes de décision ça rend la distinction "facile à résoudre" et "facile à vérifier" un peu moins simple à expliquer (il faut discuter d'une notion de "témoin", "indice" ou "certificat") Edit : Ah bah c'est mentionné sur le blog, donc même ça c'est bon :)

[@Secifelam]

avec n=1 ou p=0, on a bien p=np à moi le million !!! *se réveille* mince...

[@llll3148]

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

[@raoufbensalem3417]

@@llll3148 tu sais ct une blague

[@wollin20]

Je suis vraiment content d'être inscrit à votre chaîne: On se sent à la fois idiot d'avoir complètement ignoré le problème auparavant et réellement instruit après!

[@ScienceEtonnante]

Merci :-)

[@berengerlefort8612]

22:22 pour le mal de crâne.

[@kolowi]

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

[@berengerlefort8612]

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

[@Faxbable]

@@berengerlefort8612la logique booléenne consiste juste à exprimer les choses comme une combinaison d'affirmations avec des *OU* et des *ET*

[@ManipulationTotaleFr]

Les booléens en info: 1, 0, ou -1

[@Wellounet]

Comme toujours tes vidéos nous rappellent pourquoi ta chaîne s’appelle ainsi. Merci :)

[@lerenoiduquartier633]

Likez mon commentaire si vous voulez qu'ils fasse une vidéo sur l'équation de Navier-Stokes 😂

[@snyseb]

Non

[@snyseb]

⬆️ Likez ce commentaire pour le rendre jaloux 😅

[@baobabkine9898]

on est plus en 2011 narvalo

[@baobabkine9898]

Inuké j’aime ce mot mdr. Par contre @le renoi du quartier a raison c’est quand même intéressant

[@SirSk7walk3r]

J'avais jamais rien compris à ce problème. Là c'est beaucoup plus clair dans ma tête. Merci !

[@jeangoncalves3691]

Il suffit de simplifier P = NP par P et hop, N = 1 million pour moi

[@dantoro648]

Enfin j'ai compris le problème P=NP. C'est très bien expliqué, merci. Je m'attaque au problème immédiatement et je te promet un bon pourboire quand on me remettra le prix.

[@boudjemalarid3021]

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 :)

[@aminebadr4617]

J'aimerais avoir une idée sur la même définition en utilisant les algorithmes quantiques, est-ce qu'on aura la même classification ? les mêmes théories de complexité ? etc. Une vidéo sur ce sujet sera très souhaité. Bon courage pour la suite.

[@ScienceEtonnante]

J'enparle un peu dans le billet de blog, en effet il y a une classe spécifique BQP pour les problèmes résoluble en temps P avec un ordi quantique

[@aminebadr4617]

@@ScienceEtonnante Merci, je vais voir ça.

[@drwitch77]

C'est des vidéos du genre qui me donnent envie de me mettre aux maths pour la beauté de ces problèmes. Merci pour la vulgarisation

[@gilleswalther5964]

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).

[@Caendras]

Ca fait plaisir de voir que cette vidéo est en tendances

[@jean-luclys380]

Toujours aussi bien, clair, instructif, même pour un sujet aussi abstrait. Bravo !

[@laurent-minimalisme]

the truth has been spoken! le problème qui m'a fait adorer mes cours d'informatique à la Fac! merci monsieur Kounalis (pour ceux qui était à la fac Valrose) d'avoir passé autant de temps et de passion à enseigner de cour la!