Les algorithmes : des recettes pour les machines

Qu'est-ce qu'un algorithme ?

En une phrase : un algorithme est une suite finie d'instructions précises qui, appliquée à des données (les entrées), produit un résultat (la sortie) en un nombre fini d'étapes, sans qu'il soit jamais nécessaire de réfléchir ou d'improviser.

Une recette de cuisine, la technique de la division posée apprise à l'école ou le mode d'emploi d'un meuble en kit sont déjà des algorithmes. Le mot vient du mathématicien persan al-Khwârizmî (vers 780-850), dont le nom latinisé en Algoritmi désignait au Moyen Âge les méthodes de calcul en chiffres indo-arabes. Le mathématicien Donald Knuth résume les qualités exigées d'un algorithme en cinq mots :

Algorithme et programme : l'idée et sa traduction

Un programme est la traduction d'un algorithme dans un langage que la machine comprend. Le même algorithme, celui d'Euclide pour le plus grand commun diviseur (étudié en planche 1), s'écrit ainsi en pseudo-code, en Python et en JavaScript : les mots changent, la méthode est identique.

// pseudo-code
fonction PGCD(a, b)
  tant que b ≠ 0 :
    r ← reste de a ÷ b
    a ← b
    b ← r
  renvoyer a

# Python
def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

// JavaScript
function pgcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

Où se cachent les algorithmes ?

Chaque geste quotidien devant un écran déclenche des algorithmes, souvent plusieurs centaines. Quelques exemples :

Quatre mille ans d'algorithmes

• vers −1800Des tablettes babyloniennes décrivent des procédures de calcul pas à pas, dont une approximation de √2 juste à six décimales.
• vers −300Euclide, Éléments, livre VII : l'algorithme du PGCD, toujours utilisé dans les cartes bancaires (planche 1).
• vers −240Ératosthène invente son crible pour lister les nombres premiers.
• vers 825Al-Khwârizmî écrit à Bagdad un traité du calcul avec les chiffres indiens ; sa traduction latine, qui commence par « Dixit Algorizmi », donne son nom à l'algorithme.
• 1202Fibonacci, Liber abaci, diffuse en Europe le calcul décimal posé.
• 1843Ada Lovelace publie, pour la machine analytique de Babbage, le premier programme : le calcul des nombres de Bernoulli.
• 1844Gabriel Lamé borne le nombre de divisions d'Euclide, premier calcul de complexité de l'histoire.
• 1928Hilbert et Ackermann posent le « problème de la décision » : existe-t-il une méthode mécanique pour trancher toute question mathématique ?
• 1936Alan Turing (et Alonzo Church) définissent l'algorithme et démontrent que l'arrêt est indécidable (planche 5).
• 1945John von Neumann décrit l'ordinateur à programme enregistré et invente le tri fusion.
• 1959Edsger Dijkstra publie son algorithme du plus court chemin, cœur des GPS.
• 1961Tony Hoare publie le tri rapide.
• 1965Hartmanis et Stearns fondent la théorie de la complexité ; Jack Edmonds propose de juger « efficace » un algorithme polynomial (planche 4).
• 1971Stephen Cook formule la question P = NP, l'un des sept problèmes du millénaire, toujours ouverte.
• 1977Rivest, Shamir et Adleman publient RSA, fondement du commerce en ligne.
• 1994Peter Shor montre qu'un ordinateur quantique factoriserait les grands nombres en temps polynomial.
• 1998Brin et Page lancent PageRank.
• 2024Un projet collaboratif démontre, preuve vérifiée par ordinateur, que le castor affairé à 5 états s'arrête au plus tard après 47 176 870 pas.

En résumé