Cours Algorithmique Avancée et complexité
Pour bien comprendre l’évolution de la discipline, il est utile de débuter par un bref rappel historique. Pendant plusieurs millénaires, les mathématiciens se sont contentés d’une notion intuitive, informelle, d’algorithme : une « méthode effective de calcul », ou encore un « processus de résolution d’un problème par le calcul ». Ce fut un long chemin pour arriver à la formalisation de cette notion au XXe siècle, puis à l’étude de la complexité des algorithmes qui est l’objet de ce livre. Les premières traces d’algorithmes ont été retrouvées chez les Babyloniens (l’actuel Irak) au deuxième millénaire avant notre ère et étaient principalement des méthodes de calcul pour le commerce et les impôts. Il faut attendre le troisième siècle avant J.-C. en Grèce pour l’apparition du fameux algorithme d’Euclide pour le calcul du pgcd : on peut considérer qu’il s’agit du premier algorithme « moderne » et il est tout à fait remarquable qu’il soit toujours utilisé de nos jours. Mille ans plus tard, au IXe siècle AP. J.-C., Al Khawarizmi, un mathématicien perse (actuel Iran), publie un ouvrage consacré aux algorithmes : l’étymologie du terme « algorithme » vient du nom de ce mathématicien. On commence en effet à étudier les algorithmes en tant que tels, mais il faudra encore 800 ans avant que l’Occident continue cette étude. Aux XVIIe et au XVIIIe siècles, des savants comme Pascal ou Leibniz construisent des machines à calculer mécaniques (la Pascaline en 1642) ou des automates, ouvrant ainsi la voie à l’automatisation du calcul et à la recherche d’algorithmes efficaces. En 1837, Wantzel résout le problème de savoir quelles longueurs il est possible de construire à la règle et au compas : il s’agit de connaître la capacité des algorithmes dont les opérations de bases sont celles de la règle et du compas. Ce sont les prémices de la calculabilité. La calculabilité s’attache à connaître ce qu’on peut résoudre par algorithme quel que soit le temps d’exécution. Or dans les années 1960, si les gros ordinateurs se sont diffusés, il n’en reste pas moins qu’ils sont très lents et ne disposent pas de beaucoup de mémoire. Les chercheurs s’intéressent donc naturellement à l’efficacité des algorithmes : quel algorithme puis-je faire tourner sur cette machine sans que le résultat mette un an à arriver ? Quel algorithme puis-je faire tourner sans dépasser la capacité de la mémoire de la machine ? On trouve des réflexions théoriques très profondes de ce genre dans une lettre de Gödel à von Neumann en 1956, qui demande s’il existe un algorithme quadratique pour le problème SAT : tous les ingrédients de la question « P = NP ? » sont déjà présents dans son esprit. Malheureusement, von Neumann mourant n’a pas pu prendre cette lettre en considération et elle n’a été retrouvée que trente ans plus tard. Si l’on exclut cette lettre, la première référence explicite aux algorithmes fonctionnant en temps polynomial comme définition d’algorithmes « efficaces » se trouve dans les articles de 1965 de Cobham [Cob65] et d’Edmonds [Edm65]. Puis le papier de Hartmanis et Stearns [HS65] lance réellement le domaine de la complexité en montrant que certains problèmes ne peuvent pas être résolus en un temps donné (théorèmes de hiérarchie).
Cours: