L'algorithmique et les sciences

Concept central de l'informatique, outil de démonstration à la fois efficace et rapide, l'algorithme introduit un nouveau principe de fonctionnement technologique, c'est-à-dire à la fois une nouvelle manière de penser et une nouvelle façon d'explorer la nature. Qu'est-ce qu'un algorithme ? C'est une séquence d'instructions à suivre pour parvenir à un résultat en un temps fini, soit un programme pilotant l'exécution d'un calcul sur des données appartenant à une classe de problèmes. Or comme le montre l'auteur dans la première partie de sa Leçon inaugurale (n° 229) au Collège de France au sein de la Chaire annuelle d'Informatique et sciences numériques, une classe de problèmes est définie par la complexité de l'algorithme permettant de les résoudre. L'algorithmique distingue ainsi trois classes de problèmes auxquelles sont corrélées trois classes de complexité algorithmique : polynomiale (classe P), exponentielle (classe EXP) et non déterministe polynomiale (classe NP). Après avoir exposé la typologie de la complexité algorithmique, l'auteur nous montre un des résultats révolutionnaires apporté par l'informatique théorique : la trivialisation de la vérification continue d'une chaîne démonstrative grâce à l'aléa algorithmique, qui, outillé au moyen de l'algorithme PCP, a permis de révolutionner « notre conception mathématique et épistémologique de la preuve. » (p. 75) Dès lors, si les équations mathématiques – celles de Newton, Maxwell, Boltzmann, Einstein et Schrödinger – ont fait le succès de la physique (dans la mesure où elles permettent d'expliquer la quasi-totalité des phénomènes physiques de notre univers), c'est en revanche l'algorithme qui se présente actuellement comme un puissant outil d'appréhension des phénomènes collectifs, qu'ils soient naturels (une volée d'oiseaux, une construction de termitière, un banc de poissons, etc.), sociaux (un groupe d'individus, un réseau social, etc.) ou biologiques (des réseaux neuronaux, des circuits cellulaires, des réseaux protéiques, etc.). Comme l'écrit Bernard Chazelle en conclusion de sa Leçon inaugurale : « si les sciences nouvelles se parlent, leur langage est sans aucun doute l'algorithmique. Les algorithmes naturels nous donnent un langage. À nous de le lire, de le déchiffrer, et de s'émerveiller de la littérature de la nature » (p. 102). – 1. Introduction : La complexité algorithmique ; 2. Et Turing arriva à Princeton : Universalité – Dualité – Autoréférence ; 3. Peut-on automatiser la créativité ? ; 4. Pile ou face : Que sais-je ?  – La magie du PCP – Quelle est l'idée du PCP ? – La logique du PCP – L'algèbre du PCP ; 5. Les algorithmes naturels : Les systèmes d'influence – Les nuées d'oiseaux – Les systèmes d'influence diffusifs.

F. F.