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 !
@@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.
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.
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.
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
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
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.
@@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
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)
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 ^^
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é !
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 !
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)
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.
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
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 ^^
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!
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
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 !
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...
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.
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.
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!
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
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 !
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
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
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 !
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.
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à
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.
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 !
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 ;-) ).
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.
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 !
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 ! :)
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 TH-cam 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
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 😅
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!
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 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).
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.
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.
@@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
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
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 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!
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 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
Très bonne vulgarisation d'un problème assez théorique .... il suffisait juste de définir la notion O: un problème de complexité O(N), de complexité O(N * N), etc. Ceci dit, vérifier si un nombre est premier, est en fait un problème de complexité O(N) ... donc ni O(N puissance 6), encore moins O(N puissance 12). En effet, considérons un nombre N quelconque. L'algorithme LE PLUS LENT permettant de savoir si N est premier ou pas, est le suivant: Début {Pour I = (N-1) jusqu'à 2 Faire Si le reste de la division de N par I = 0 Alors {Ecrire " N n'est pas un nombre premier" Exit; } Fsi Fait Ecrire " N est un nombre premier" } Fin Ainsi, avec cet algorithme, dans le PIRE des cas, on fait (N - 2) vérifications. Cet algorithme est donc de complexité .... O(N).
Hmm mais est-ce que le modulo ne compterait pas comme plusieurs opérations élémentaires ? Pour le déterminer il faudrait selon moi I étapes dans le pire des cas, il faut donc rajouter 1 + 2 + 3 + ... + (N-1) étapes soit (N² - N) / 2, donc au total (N - 2) + (N² - N) / 2 = (N² + N - 4) / 2 donc O(N²), non ?
@@stratonikisporcia8630 Il y'a (N-1)-2+1 = (N-2) vérifications. Pour chaque vérification, on teste si N est divisible par i. Ce test (calcul du modulo, etc.) nécessite un temps d'exécution d CONSTANT: le temps d'exécution TOTAL est donc T(N) = d (N-2)
Merci à toi pour cette vidéo. J'ai compris plus finement cette histoire de polinomes. Si tu diffusait une vidéo sur chaques problèmes de ce Mr Clay, nous serions nombreux à les suivres. Merci de ta pédagogie.
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 ! ^^
@@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)
Ca me rappelle mes cours sur le sujet. C était mon prof qui avait amélioré avec des confrères à lui le system AKS. Un type brillant qui avait vulgarise la chose aussi bien que toi. Super vidéo !
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**
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 :)
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!
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 !
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 !
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. ..
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 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!
@@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
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 !
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.
C'est marrant parce que dans les jeux vidéos, le problème du sac à dos on le fait très souvent : imaginons que je suis dans Skyrim, j'ai un objet qui pèse 0,5kg, et qui coûte 200PO, on calcul rapidement que pour 1kg de cet objet, on gagne 400PO, et si on voulait optimiser la chose, on garderait une colonne avec le poids brut à coté (on le fait dans son esprit en général, hein xD ) : ainsi, tout les objets avec le meilleur ratio va en prio dans le sac, puis avec ce qu'il reste de poids dispo, on met l'objet qui a le second meilleur ratio et qui peut rentrer, et ainsi de suite jusqu'à ce que tout rentre :p ! Hop ! Easy :D !
Merci pour cette vidéo de qualité comme d'habitude ! Venant de prépa scientifique ça me rappelle l'algorithmique effleurée en spé (Tri à bulle etc), où ce problème mythique nous avait été exposé :)
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 !
Excellent. Peu avant la fin, j'étais justement en train de me dire qu'en pratique un problème P avec un gros exposant n'était pas très différent d'un problème NP ! J'en ai été conforté par ta conclusion.
Un problème P avec un gros exposant est quand même très différent d'un problème NP dans le sens ou une fois qu'on dispose d'une capacité de calcul adéquate on peux résoudre le problème P quelle que soit la taille des données. Avec un problème NP ce n'est pas le cas car le nombre d'opérations a effectuer augmente de façon exponentielle avec la taille des données.
@@wil1080 Bien entendu, sinon, pourquoi avoir inventé la théorie ? Je dis en pratique. Quand les ordinateurs quantiques seront monnaie courante, on verra. Mais, si la vitesse de calcul n'est pas infinie (auquel cas, même les problèmes NP deviennent solubles), il y aura toujours un exposant assez grand pour casser les pieds !
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.
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.
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.
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
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.
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.
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
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)
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 ^^
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'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é !
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 !
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)
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.
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
"Ç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?
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!
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
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 !
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...
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.
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!!!
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
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
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!
Super limpide. Bravo. ScienceEtonnance = Boss final de la vulgarisation scientifique francophone sur TH-cam.
Merci :-)
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!
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
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
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 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
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é.
@@lemalademental316cet algorithme ne fonctionne pas dans le cas suivant:
Objet 1: 8000€, 49kg
Objet 2: 200€, 1kg
Objet 3, 7000€, 10kg
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 !
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 !
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à
Vraiment excellente vidéo c'est toujours d'une clarté exceptionnelle. Merci pour le travail !
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.
Merci pour ce travail de qualité accessible gratuitement ❤
J'ai presque tout compris, vous êtes très bon comme d'habitude! 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 !
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 ;-) ).
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.
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
@@ScienceEtonnante Merci, je vais voir ça.
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
Tkt je suis la pcq j'avais besoin de me rappeler que je suis une merde en math😂
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 !
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😂
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 ! :)
Merci beaucoup :-)
Toujours aussi clair et intéressant. J'adore tes vidéos.
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 TH-cam 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
"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.
Je fais des études en mathématiques et informatique. C'est de loin la meilleure explication du problème que j'ai entendu!!
Merci :) j'adore apprendre en t'écoutant :)
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 😅
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).
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.
Difficile de le gagner ce million... mais pour toi, il approche tres vite !! ;) Largement mérité !! Continue
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.
P=NP, c'est pourtant pas dur à résoudre. Deux solutions : N=1 ou P=0
C'est du 2nd degré rassure moi 😅
@@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
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
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...
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!
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
Très bonne vulgarisation d'un problème assez théorique .... il suffisait juste de définir la notion O: un problème de complexité O(N), de complexité O(N * N), etc. Ceci dit, vérifier si un nombre est premier, est en fait un problème de complexité O(N) ... donc ni O(N puissance 6), encore moins O(N puissance 12). En effet, considérons un nombre N quelconque. L'algorithme LE PLUS LENT permettant de savoir si N est premier ou pas, est le suivant:
Début
{Pour I = (N-1) jusqu'à 2
Faire Si le reste de la division de N par I = 0
Alors {Ecrire " N n'est pas un nombre premier"
Exit;
}
Fsi
Fait
Ecrire " N est un nombre premier"
}
Fin
Ainsi, avec cet algorithme, dans le PIRE des cas, on fait (N - 2) vérifications. Cet algorithme est donc de complexité .... O(N).
Hmm mais est-ce que le modulo ne compterait pas comme plusieurs opérations élémentaires ? Pour le déterminer il faudrait selon moi I étapes dans le pire des cas, il faut donc rajouter 1 + 2 + 3 + ... + (N-1) étapes soit (N² - N) / 2, donc au total (N - 2) + (N² - N) / 2 = (N² + N - 4) / 2 donc O(N²), non ?
@@stratonikisporcia8630 Il y'a (N-1)-2+1 = (N-2) vérifications. Pour chaque vérification, on teste si N est divisible par i. Ce test (calcul du modulo, etc.) nécessite un temps d'exécution d CONSTANT: le temps d'exécution TOTAL est donc T(N) = d (N-2)
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 ?
Merci à toi pour cette vidéo.
J'ai compris plus finement cette histoire de polinomes.
Si tu diffusait une vidéo sur chaques problèmes de ce Mr Clay, nous serions nombreux à les suivres.
Merci de ta pédagogie.
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)
J'avais jamais rien compris à ce problème. Là c'est beaucoup plus clair dans ma tête.
Merci !
ça me rappelle mes cours d'informatique :')
Ca me rappelle mes cours sur le sujet. C était mon prof qui avait amélioré avec des confrères à lui le system AKS. Un type brillant qui avait vulgarise la chose aussi bien que toi. Super vidéo !
*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 :)
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**
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 :)
Zut, je n'ai toujours pas compris ce qu'était un sudoku ...
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!
21:37 le premier veut voir le numero 19et ne veut pas le voir haha
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 !
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
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 !
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
La clarté de l'explication est assez incroyable.
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 ?
@@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!
Oui je me suis limité à ça pour ne pas complexifier :-)
La conclusion avec l'histoire des sondages est extra, merci :)
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
Je ne sais pas si tes explications sont parfaite mais j'ai enfin compris l'énoncé de ce probleme!
Merci!
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
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 !
Il suffit de simplifier P = NP par P et hop, N = 1 million pour moi
Toujours aussi bien, clair, instructif, même pour un sujet aussi abstrait. Bravo !
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
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.
C'est marrant parce que dans les jeux vidéos, le problème du sac à dos on le fait très souvent : imaginons que je suis dans Skyrim, j'ai un objet qui pèse 0,5kg, et qui coûte 200PO, on calcul rapidement que pour 1kg de cet objet, on gagne 400PO, et si on voulait optimiser la chose, on garderait une colonne avec le poids brut à coté (on le fait dans son esprit en général, hein xD ) : ainsi, tout les objets avec le meilleur ratio va en prio dans le sac, puis avec ce qu'il reste de poids dispo, on met l'objet qui a le second meilleur ratio et qui peut rentrer, et ainsi de suite jusqu'à ce que tout rentre :p ! Hop ! Easy :D !
Merci pour cette vidéo de qualité comme d'habitude ! Venant de prépa scientifique ça me rappelle l'algorithmique effleurée en spé (Tri à bulle etc), où ce problème mythique nous avait été exposé :)
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 !
dude the coolest and easiest course on complexity i have ever seeing. Bravo
Excellent. Peu avant la fin, j'étais justement en train de me dire qu'en pratique un problème P avec un gros exposant n'était pas très différent d'un problème NP ! J'en ai été conforté par ta conclusion.
Un problème P avec un gros exposant est quand même très différent d'un problème NP dans le sens ou une fois qu'on dispose d'une capacité de calcul adéquate on peux résoudre le problème P quelle que soit la taille des données. Avec un problème NP ce n'est pas le cas car le nombre d'opérations a effectuer augmente de façon exponentielle avec la taille des données.
@@wil1080 Bien entendu, sinon, pourquoi avoir inventé la théorie ? Je dis en pratique. Quand les ordinateurs quantiques seront monnaie courante, on verra. Mais, si la vitesse de calcul n'est pas infinie (auquel cas, même les problèmes NP deviennent solubles), il y aura toujours un exposant assez grand pour casser les pieds !
vous êtes plus clair que mon prof de complexité !! bien expliqué, merci
Superbe ! C'est très clair ton format, facile à comprendre.