algorithme

Imaginez que vous vouliez ranger les nombres 8, 3, 6 et 2 du plus petit au plus grand. Vous pouvez comparer deux nombres, les placer, puis recommencer selon des consignes toujours identiques. La liste 2, 3, 6, 8 est le résultat.

Un algorithme transforme ainsi des données de départ en un résultat par une suite d'instructions précises. L'ordre compte, et la procédure doit finir. Une personne peut exécuter ces instructions avec papier et crayon ; un ordinateur peut les répéter beaucoup plus vite.

Un algorithme est une procédure finie et ordonnée qui reçoit des données, exécute des instructions non ambiguës, puis produit un résultat. Pour une même entrée et dans un cadre déterministe, chaque étape fixe la suivante. Une condition d'arrêt garantit que l'exécution ne se poursuit pas indéfiniment.

Les données peuvent être des nombres, une liste à trier ou les sommets et arêtes d'un graphe. Les instructions peuvent effectuer un calcul, comparer des valeurs ou choisir une branche selon une condition. L'algorithme d'Euclide calcule par exemple le PGCD de deux entiers par des divisions successives. D'autres algorithmes ordonnent une liste ou recherchent un plus court chemin dans un graphe.

Un algorithme décrit la méthode indépendamment du langage informatique choisi. Son programme est une mise en œuvre concrète. Le nom vient de la latinisation d'Al-Khwarizmi ; l'informatique a ensuite multiplié la vitesse et les domaines d'exécution de telles procédures.

Pour calculer le PGCD de deux entiers positifs, prenez le plus grand et divisez-le par le plus petit. Remplacez ensuite ces deux nombres par le diviseur et le reste, puis recommencez. Dès que le reste vaut 0, arrêtez : le dernier reste non nul est le PGCD. Chaque division diminue strictement le reste non nul ; la procédure finit donc après un nombre fini d'étapes.

Un algorithme s'applique quand les données d'entrée sont définies, que chaque instruction est exécutable sans interprétation personnelle et qu'un point d'arrêt est prévu. Il faut aussi préciser le résultat attendu : une liste triée, un nombre ou un chemin, par exemple.

Pour l'algorithme d'Euclide présenté ici, les entrées sont deux entiers strictement positifs et chaque étape utilise une division euclidienne. Si une consigne demande seulement de « choisir un reste assez petit », l'étape est ambiguë et le calcul n'est pas exécutable tel quel. Il faut remplacer cette consigne par la division euclidienne, qui détermine un reste unique compris entre 0 et le diviseur exclu.

On cherche le PGCD de 252 et 105. Les données sont les deux entiers positifs 252 et 105 ; l'opération autorisée est la division euclidienne.

1. Divisez 252 par 105. Le quotient vaut 2 et le reste vaut 42 : 252 = 2 × 105 + 42.

2. Reprenez le diviseur 105 et le reste 42. La division donne 105 = 2 × 42 + 21.

3. Reprenez 42 et 21. La division donne 42 = 2 × 21 + 0. Le reste est nul : l'algorithme s'arrête.

Le dernier reste non nul est 21, donc le PGCD de 252 et 105 vaut 21. Le contrôle est direct : 252 = 12 × 21 et 105 = 5 × 21. La chaîne des trois divisions rend visibles les données transmises d'une étape à la suivante.

Pour calculer exactement le PGCD de deux entiers, les divisions successives de l'algorithme d'Euclide évitent de tester tous leurs diviseurs communs. On choisit cette méthode dès que les nombres deviennent trop grands pour une liste mentale fiable.

Pour ordonner beaucoup de valeurs, un algorithme de tri fixe les comparaisons et les déplacements à effectuer. Le choix entre plusieurs tris dépend notamment du nombre de données et de leur ordre initial.

Dans un réseau modélisé par un graphe, un algorithme de plus court chemin compare les itinéraires selon un coût défini, comme une distance. Une simple lecture visuelle peut suffire sur un petit dessin ; l'algorithme devient préférable lorsque les chemins possibles se multiplient.

Algorithme et programme. L'algorithme décrit une méthode ; le programme traduit cette méthode dans un langage exécutable par une machine. Le même tri peut donc conduire à plusieurs programmes sans changer de principe.

Algorithme et formule. Une formule relie des grandeurs, tandis qu'un algorithme ordonne des opérations. L'égalité 252 = 12 × 21 vérifie un calcul ; elle ne donne pas, à elle seule, les étapes pour trouver 21.

Algorithme exact et heuristique. Une heuristique propose une stratégie pratique sans garantir toujours le résultat optimal. Une procédure de plus court chemin prouvée correcte donne au contraire un chemin minimal sous ses hypothèses.

Une suite d'instructions peut ne jamais finir. Si aucune valeur ne se rapproche d'un arrêt, l'exécution boucle. La répétition d'un état est un indice possible lorsque l'espace des états est fini, mais une exécution peut aussi parcourir indéfiniment des états tous distincts ; il faut alors établir une quantité qui progresse vers une borne ou fixer un arrêt justifié.

Finir ne suffit pas. Un algorithme peut s'arrêter et produire une réponse fausse. Pour 252 et 105, annoncer 42 est réfuté par 105, qui n'est pas divisible par 42 ; il faut prouver la règle puis contrôler le résultat sur les données.

Une instruction ambiguë casse la reproductibilité. Deux exécutants peuvent alors choisir des étapes différentes. Il faut remplacer des mots comme « assez petit » par un critère testable ; dans la division euclidienne, le reste doit être au moins nul et strictement inférieur au diviseur.

Deux algorithmes corrects peuvent avoir des coûts très différents. Sur quatre valeurs, l'écart passe inaperçu ; sur une grande liste, le nombre d'opérations et la mémoire deviennent décisifs. Il faut comparer leur complexité dans le domaine d'entrées visé.

Algorithme d'Euclide et cætera prolonge l'exemple du PGCD et replace cette procédure dans une famille d'idées mathématiques.

Le glossaire PGCD précise le résultat recherché par les divisions successives et ses propriétés arithmétiques.

La fiche algorithme de tri montre comment une procédure ordonnée compare et range les éléments d'une liste.

L’algorithme de la tortue donne un autre terrain d'exécution où une suite d'instructions produit une construction observable.