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

Watch on YouTube

Show annotations

Download is disabled.

352,764

29,537

198

Genre: Science & Technology

Family friendly? Yes

Wilson score: 0.9924

Rating: 4.9734 / 5

Engagement: 0.0843%

ScienceEtonnante

Subscribe | 941K

Shared July 17, 2020

On parle d'un problème d'informatique théorique à 1 million de dollars, et même beaucoup plus si vous l'utilisez pour pirater les banques du monde entier ! Oserez-vous chercher un algorithme qui permette de trancher ?

Détails et compléments dans le billet de blog qui accompagne la vidéo :
https://sciencetonnante.wordpress.com...

Une vidéo de Passe-Science sur le même sujet, avec notamment une belle réduction entre problèmes NP-complets
https://www.youtube.com/watch?v=8TrIW...

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

Facebook : http://www.facebook.com/sciencetonnante
Twitter : http://www.twitter.com/dlouapre
Abonnez-vous : https://www.youtube.com/scienceetonnante
Me soutenir sur Tipeee : http://www.tipeee.com/science-etonnante
Mon livre : http://www.science-etonnante.com/redi...

Sushi LaFamille

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

3 weeks ago | [YT] | 950

F V

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

3 weeks ago | [YT] | 463

crollens

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

3 weeks ago | [YT] | 205

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!

3 weeks ago | [YT] | 297

Abakhan

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

3 weeks ago | [YT] | 188

Daemonsoadfan

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

3 weeks ago | [YT] | 108

Incroyables Expériences

Tellement clair et bien expliqué, bravo !

3 weeks ago | [YT] | 18

jm c

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.

3 weeks ago | [YT] | 51

Théo Roubaix

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

3 weeks ago | [YT] | 8

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)

3 weeks ago | [YT] | 4

KEN le survivant

pour une fois je comprends ce problème
Merci.

3 weeks ago | [YT] | 29

Urikan

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

3 weeks ago | [YT] | 4

Jerem Pinch

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

3 weeks ago | [YT] | 11

Bruno DARCET

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.

3 weeks ago | [YT] | 4

Physicien du Président de l'Empire d'Imhotep

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

3 weeks ago | [YT] | 42

FirsfName Lastname

Wow, juste WoW. L’année passée on étudiait ça en cours, et je cherchais un article/vidéo/n’importe quoi qui résume ces différents mots NP Complet, P,... et leurs relations
Il n’y avait rien ! (Oui une seule vidéo connue mais un peu trop brouillon à mon goût)

Cette vidéo a tout simplifié! Merci infiniment! Merci exponentiellement

3 weeks ago | [YT] | 8

jp a

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.

3 weeks ago | [YT] | 5

Aime Ducret

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

1 day ago | [YT] | 1

deadal nix

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: https://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.

3 weeks ago (edited) | [YT] | 7

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

3 weeks ago | [YT] | 3