P = NP ?

A propos du chercheur fantôme

Capture d’écran 2019-10-29 à 07.20.46

extrait de la BD « Le chercheur fantôme » de Robin Cousin, éditions Flblb

Les liens de ce paragraphe renvoient à Wikipédia

L’algorithmique n’est pas une science récente si l’on remonte à celui qui lui a légué son nom, Al-Kwarâzmî (nom latinisé en Algorizmi) homme de science persan mort à Bagdad en 850. Cependant son essor a été facilité récemment par la construction de machines permettant de calculer plus vite qu’un cerveau humain.

Ce que l’on considère comme le premier ordinateur (machine analytique) a été conçu mais jamais construit par Charles Babbage au XIXème siècle. Ada Lovelace, mathématicienne et fille de Lord Byron, l’a aidé à en penser les principes. Elle est consacrée aujourd’hui comme la première informaticienne.

 

9782213712796-001-T

 

Une biographie romancée de Catherine Dufour « Ada ou la beauté des nombres » est paru en septembre chez Fayard.

 

 

cover.jpg.rendition.460.707-215x300@2x

 

Une BD en anglais The thrilling aventures of Lovelace and Babbage de Sydney Padua raconte avec humour et loufoquerie l’histoire du premier ordinateur.

 

 

 

  • Qu’est-ce que P = NP veut dire ?

Le mieux est d’interroger un informaticien sur le sujet…

Son histoire remonte à Euler et à son problème sur les ponts de Königsberg. Un exposé de Jacques Sauloy, trouvé sur le site de l’université de Toulouse, apporte un éclairage accessible sur la question.

Capture d’écran 2019-10-29 à 07.42.45.png

image extraite du diaporama de Jacques Sauloy

Le problème P = NP fait partie des problèmes du siècle et peut même rapporter un million de dollars à celui qui le résoudra. Et rendrait même l’auteur de la solution démesurément riche puisqu’à en croire le journal du geek : il pourrait s’accaparer tous les bitcoins et le concept de blockchain serait alors mal à point…

Scott Aaderson, professeur à l’Université du Texas, Austin, dans son blog en anglais affirme :

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.

 

  • La théorie des graphes

C’est une branche des mathématiques, plus précisément des mathématiques discrètes, très féconde. Notons qu’un de ses pionniers en France est Claude Berge, membre fondateur de l’OuLiPo.

Si vous voulez tout savoir très vite sur la théorie des graphes – ou disons en avoir une introduction, de la notion de distance jusqu’à la coloration – il faut aller par exemple sur un des sites dédiés : graphes.fr

Exemple célèbre de l’utilisation des graphes en littérature, Georges Perec a utilisé la marche du cavalier sur un échiquier pour construire son récit La vie mode d’emploi. Quelques explications :

Ici sur france.tv éducation , et là pour le cahier des charges du roman

  • Qu’en faire ?

Les graphes sont a peu près partout où l’on veut en voir, mais en classe on peut en faire une BD par exemple, ou une machine à poèmes (ce qui ne garantit pas la poésie) :

On se donne un polygone, dont on pourra discuter la parité des sommets, et on cherche à partir d’un sommet pour y revenir en passant une fois et une seule par chaque côté et chaque diagonale. On attache une image ou un vers, ou un petit texte, à chaque sommet et il n’y a plus qu’à déplier l’histoire pour la lire en entier.

Etienne Lécroart le fait avec brio dans Contes et décomptes

contes1

Et qui a été repris lors d’une animation à la Maison de Fermat à Beaumont-de-Lomagne où une jeune fille de 8 ans a raconté quelques déboires avec sa maman : (suivez les flèches dans l’ordre !)

Capture d’écran 2019-10-29 à 10.33.29

Quand à la poésie chacun jugera :

eoderdrome

 

On peut en faire bien d’autres choses, en somme…