Ce qu'est un algorithme

La méthode pour trouver le plus grand diviseur commun du livre VII des Éléments d'Euclide, écrite il y a environ 2300 ans, fonctionne encore aujourd'hui dans les ordinateurs.

Une méthode qui marche à tous les coups

Imagine que tu cherches le plus grand nombre qui divise à la fois 1071 et 462. Tu pourrais essayer tous les nombres de 462 jusqu'à 1 et t'arrêter au premier qui divise les deux. Ça marche, mais cela peut demander des centaines d'essais. Il existe un chemin plus court. Divise 1071 par 462 et garde le reste, 147. Divise maintenant 462 par 147 et garde le reste, 21. Divise 147 par 21 : le reste vaut 0, donc la réponse est 21. Trois divisions au lieu de plusieurs centaines.

Ce chemin plus court est un algorithme : une liste finie d'étapes précises qui prend une entrée et produit la bonne sortie. Celui-ci est l'algorithme d'Euclide pour le plus grand diviseur commun (PGCD), et il figure dans le livre VII des Éléments, écrits vers 300 av. J.-C. Euclide le décrivait par des soustractions répétées de longueurs plutôt que par des divisions, mais l'idée est la même, et c'est la version avec les restes qu'utilisent les programmes aujourd'hui.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // reste
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // affiche 21

Ce qui fait d'une liste d'étapes un algorithme

Les manuels comme celui de Cormen, Leiserson, Rivest et Stein décrivent un algorithme comme une procédure bien définie qui transforme une entrée en sortie. Cette description contient trois idées, et chacune compte quand on écrit du code.

• Précis. Chaque étape a un seul sens. « Divise a par b et garde le reste » est précis ; « rends les nombres plus petits d'une façon ou d'une autre » ne l'est pas.
• Fini. Il doit s'arrêter. Dans l'algorithme d'Euclide, le reste est toujours plus petit que le nombre par lequel on a divisé : il diminue donc à chaque tour et finit forcément par atteindre 0.
• Correct. Pour chaque entrée autorisée, la sortie est la bonne réponse, et pas seulement pour les exemples que tu as essayés.

On donne souvent une recette de cuisine comme exemple de la vie courante, et c'est un bon exemple : les ingrédients sont l'entrée, le plat est la sortie, et les étapes sont dans l'ordre. La différence, c'est tout ce que le lecteur complète. Un cuisinier décide ce que veut dire « une pincée ». Un ordinateur ne décide rien : c'est pourquoi les algorithmes pour ordinateurs sont écrits avec chaque étape détaillée.

Même problème, algorithmes différents

Un problème a en général de nombreux algorithmes corrects, et ils peuvent demander des quantités de travail très différentes. Pour le PGCD de 1071 et 462, essayer tous les nombres à partir de 462 en descendant demande 442 essais avant d'atteindre 21, alors que la méthode d'Euclide demande 3 divisions. Les deux sont correctes. Une seule est rapide. Une grande partie de ce cours porte sur cette deuxième question : une fois qu'une méthode est correcte, combien d'étapes demande-t-elle, et comment ce nombre augmente-t-il quand l'entrée grandit ?

Pour y répondre, les informaticiens comptent des étapes élémentaires (une comparaison, un échange, une division) plutôt que des secondes. Les secondes dépendent de la machine. Un nombre d'étapes ne dépend que de l'algorithme et de l'entrée : il permet donc de comparer deux méthodes équitablement. Le labo ci-dessous compte les comparaisons pour toi pendant qu'il trie une rangée de barres. Essaie le même ordre de départ avec deux méthodes différentes et observe les compteurs.

Entrées, sorties et étapes intermédiaires

Avant d'écrire un algorithme, note exactement ce qui entre et ce qui doit sortir. Pour le PGCD : l'entrée est deux nombres entiers positifs, et la sortie est un nombre entier qui divise les deux, sans qu'aucun nombre plus grand en fasse autant. Cette description indique comment tester le résultat, et elle donne souvent une idée des étapes. Elle révèle aussi les cas limites : et si l'un des nombres vaut 0 ? (La boucle ci-dessus renvoie l'autre nombre, ce qui est la bonne réponse.) Et si les deux nombres sont égaux ? Réfléchir aux cas limites avant d'exécuter le code permet d'éviter beaucoup d'erreurs.