L'algorithmique ouvre la possibilité d'un regard nouveau sur les sciences et les technologies qui s'étend bien au-delà de ses applications pratiques. Ce cours propose d'en expliquer les fondements.
La loi de Moore prévoit le doublement de la puissance des ordinateurs tous les deux ans. Cette progression a été le principal vecteur d’innovation technologique dans le monde depuis plus de quarante ans. Comme toute croissance exponentielle, bien sûr, la Loi de Moore est condamnée à brève échéance. De fait, tout porte à croire qu’elle est déjà lettre morte. C’est en tout cas l’hypothèse de travail qui sous-tend le développement de la prochaine génération de systèmes d’exploitation chez Microsoft. L’avenir de l’informatique, on serait tenté d’en conclure, n’appartient plus à la puissance brute de calcul mais à l’algorithmique, la discipline qui nous a apporté le décodage du génome humain, les moteurs de recherche, les enchères électroniques, le cryptage des achats en ligne, et la reconnaissance de la parole. Au-delà de ses applications logicielles, toutefois, l’algorithme est surtout un outil conceptuel « subversif » qui ouvre la possibilité d’un regard nouveau sur les sciences et les technologies.
Ce cours propose d’expliquer les éléments constitutifs de cette révolution en marche.
Les algorithmes font penser différemment. Saviez-vous, par exemple, qu’il existe un algorithme en mesure de vous convaincre instantanément de la validité d’une preuve comme celle de la redoutable Conjecture de Poincaré en y piochant au plus dix mots au hasard ? L’intuition qui vous conduit à penser que toute démonstration mathématique est à la merci de la moindre faute est foncièrement trompeuse. Saviez-vous qu’il vous est possible de convaincre un interlocuteur d’une vérité sans en révéler la moindre information sur sa justification ? Ces algorithmes à « divulgation nulle » ont radicalement transformé des notions épistémologiques fondamentales comme la vérification de preuve. En cryptographie, leur utilisation permet des transactions entre des entités qui ne se font pas confiance. Par exemple, comment authentifier un document ou prouver la possession d’un mot de passe sans le révéler ?