L’algorithmique, science des algorithmes, est centrale en informatique. Je parlerai d’abord des algorithmes classiques, ceux qui prennent des données, calculent, puis rendent des résultats. Ils sont très nombreux, et l’algorithmique a pour objectif d’en découvrir de nouveaux ou d’améliorer les anciens, en veillant toujours à garantir leur terminaison sur les données concernées, leur correction, qui exprime que l’algorithme fait bien ce pour quoi il a été conçu, et leur complexité, qui est leur coût en temps de calcul, mémoire, ou énergie. Analyser ces propriétés fait toujours appel aux mathématiques, et y conduit souvent à de nouveaux développements.
Dès 1936, Turing avait formalisé la notion d’algorithme à l’aide de sa fameuse machine. Il avait aussi montré que tout n’était pas faisable par des algorithmes : son théorème d’indécidabilité du problème de l’arrêt établissait l’impossibilité de construire un algorithme T se terminant toujours et décidant si un algorithme précis A travaillant sur des données D va se terminer ou non. Ce résultat fondamental établit la limite la plus dure de l’informatique : si on peut construire une machine universelle simulant n’importe quelle autre machine, on ne peut pas en construire pour décider l’arrêt de cette machine.
Pendant longtemps, ne travaillant que sur du papier, les chercheurs se sont intéressés principalement aux questions de décidabilité/indécidabilité, sans vraiment se préoccuper de la faisabilité pratique des algorithmes qu’ils étudiaient : quels problèmes mathématiquement intéressants peut-on résoudre avec des algorithmes qui s’arrêtent toujours, et pour quels problèmes est-il impossible de construire de tels algorithmes …