algorithme

Qu’est-ce qu’un algorithme ? Des premiers calculs au GPS

Vous êtes en retard pour prendre un train. Sur la carte de votre téléphone, une route vous mène directement à la gare en neuf minutes. L’application vous propose pourtant de passer par le marché. Trois minutes pour y arriver, quatre de plus pour rejoindre la gare. Le détour vous fait gagner deux minutes. Vous pourriez le vérifier de tête. À l’échelle d’une ville, avec des milliers de rues et de croisements, comment l’application sait-elle quels trajets méritent d’être examinés ?

Un algorithme donne une méthode précise pour résoudre un problème à partir de données. Ici, il reçoit une carte, un départ et une destination. Il doit trouver l’itinéraire le plus rapide selon les durées attribuées aux routes. Des méthodes de ce genre existaient avant les ordinateurs. Ce que l’informatique a changé, c’est l’échelle à laquelle on peut les appliquer et les manières de chercher une réponse. Revenons d’abord à une époque où l’on devait transmettre ces méthodes à des personnes qui calculaient à la main.

D’où vient le mot « algorithme » ?

Vers 300 avant notre ère, les Éléments d’Euclide décrivent une méthode pour trouver la plus grande mesure commune à deux nombres. Prenez deux longueurs, 48 et 18 cm. Si vous voulez y faire entrer un même carreau un nombre entier de fois, vous pouvez retrancher deux fois 18 à 48 et vous intéresser à ce qui reste, 12. En poursuivant, vous trouvez 6. Le point décisif est que la méthode peut être expliquée à quelqu’un qui l’appliquera ensuite à d’autres longueurs. Euclide en démontre le bien-fondé. Des tablettes babyloniennes attestent que des procédés de calcul par étapes étaient déjà pratiqués bien avant lui.1

Le mot « algorithme » nous ramène beaucoup plus tard à Bagdad. Vers 825, al‑Khwarizmi consacre un traité à une manière de compter venue de l’Inde. Dans cette écriture, le 2 de 205 vaut deux centaines et le zéro indique qu’il n’y a aucune dizaine. Les versions latines du traité expliquent comment tirer parti de ces positions pour additionner deux nombres. On aligne les chiffres de même rang, on les additionne et, si nécessaire, on reporte une retenue. À l’époque, on pouvait effectuer ce calcul sur une tablette effaçable, en remplaçant les chiffres à mesure que le résultat prenait forme. La façon d’écrire les nombres guide ainsi les gestes du calcul. Plus loin, la façon de représenter les rues guidera à son tour la recherche d’un itinéraire.2

Le texte arabe du traité n’a pas été retrouvé. Il est connu grâce à des versions latines remaniées. L’une commence par Dixit Algorizmi, « Al‑Khwarizmi a dit ». Du nom latinisé dérivent des formes médiévales comme algorisme, qui désignent d’abord le calcul avec ces chiffres. Leur sens s’élargit jusqu’à celui de méthode de calcul, puis de traitement. Le même savant a laissé une autre trace dans notre vocabulaire. Le mot « algèbre » vient d’al‑jabr, un terme du titre d’un autre de ses livres.2

On mesure l’intérêt pratique de ce calcul en lisant le récit de Fibonacci. Enfant, il rejoint son père, qui travaille à la douane de Béjaïa, dans l’actuelle Algérie, pour les marchands pisans. Il raconte y avoir appris une manière de compter qui l’impressionne. Dans son Liber abbaci, rédigé en 1202 et remanié en 1228, ces méthodes servent notamment à traiter des questions de prix, de monnaies et de partage. Pour le lecteur du livre, l’avantage est concret. Il peut refaire les opérations avec ses propres chiffres. Reste à savoir jusqu’où l’on peut confier ce travail à une machine.3

Quand la règle doit pouvoir s’exécuter

Ouvrez la Note G publiée par Ada Lovelace en 1843. Le tableau destiné à la machine analytique de Babbage précise les opérations à effectuer sur les nombres de Bernoulli, les emplacements où lire les valeurs et ceux où conserver les résultats. La machine reste inachevée, mais le tableau donne une idée de ce qu’exige l’exécution automatique. Chaque étape doit disposer exactement des valeurs que les étapes précédentes étaient censées produire.4

En 1936, Alan Turing aborde cette question sous un angle théorique. Il imagine une machine élémentaire qui lit et écrit des symboles et suit des règles précises. Ce modèle lui permet d’étudier ce qu’une procédure de calcul peut accomplir et d’établir des limites à ce qu’on peut résoudre par cette voie. Avec les ordinateurs programmables, une autre question devient pressante. Lorsque plusieurs méthodes donnent la même réponse, laquelle demandera le moins de travail à la machine ? À la fin des années 1950, les concepteurs d’ALGOL 60 cherchent notamment à permettre aux chercheurs de décrire leurs méthodes avec assez de précision pour les partager et les exécuter sur différentes machines.4

Pour sentir la différence entre problème, algorithme et programme, prenez le tableau des départs à la gare. Le problème est de trouver le train qui part le plus tôt parmi ceux qui vont à votre destination. Une méthode consiste à lire les départs les uns après les autres, à vérifier la destination et à retenir la meilleure heure rencontrée. Le programme écrit cette méthode en Python, en Java ou dans un autre langage. On y retrouve trois structures simples. La séquence fixe l’ordre des opérations. La condition décide si l’on doit remplacer l’heure retenue. La boucle fait répéter le contrôle pour le départ suivant.

Cette méthode fonctionne avec un tableau en désordre. Si l’affichage est déjà classé par heure, vous pouvez vous arrêter au premier train vers votre destination. Un simple changement dans l’organisation des données vient de modifier le travail nécessaire pour obtenir la réponse.

Ce que l’on range change ce que l’on peut chercher

Imaginez maintenant un répertoire de 1 024 contacts. Avec des noms mélangés, une recherche qui les examine un à un peut devoir parcourir tout le répertoire. Dans un tableau trié, le programme peut aller directement au milieu. Si le nom recherché se situe après celui du milieu dans l’ordre alphabétique, il écarte toute la première moitié. Il recommence sur la partie restante. C’est la recherche dichotomique. Dans cet exemple, une dizaine de comparaisons suffit pour trouver un nom ou constater son absence. En informatique, la complexité décrit comment le travail ou la mémoire nécessaires évoluent quand les données grossissent. Ici, elle fait apparaître l’avantage de réduire le nombre de noms à examiner de moitié à chaque étape. Il a toutefois fallu constituer et maintenir le répertoire dans l’ordre.5

Pour fabriquer ce répertoire, on peut utiliser le tri par fusion. On partage les contacts en deux groupes, on trie chacun et on les réunit dans l’ordre. Imaginez deux piles de fiches déjà classées. Pour construire une pile commune, il suffit de comparer les deux fiches du dessus et de prendre celle qui vient en premier. C’est un exemple de la stratégie diviser pour régner. La recherche dichotomique élimine une moitié, tandis que le tri par fusion traite les deux moitiés puis réunit leurs résultats. Le tri peut s’écrire de façon récursive. La même procédure s’applique alors à des groupes de plus en plus petits jusqu’à ce qu’il reste une seule fiche à traiter.5

À la fin des années 1950, une contrainte matérielle rend cette question du tri très concrète pour Tony Hoare. Il étudie la traduction automatique à Moscou. Le dictionnaire à consulter est stocké sur une bande magnétique dont la lecture prend plusieurs minutes. Hoare raconte l’avantage qu’il y avait à classer les mots recherchés dans le même ordre que le dictionnaire. Un seul défilement de la bande suffirait alors pour les retrouver. Ce problème lui donne l’idée de Quicksort, le tri rapide, qu’il décrit en détail en 1962. La méthode organise les éléments autour d’une valeur choisie comme repère, le pivot, puis traite séparément les groupes ainsi formés. Le tri par fusion et Quicksort produisent le même ordre. Ils partagent le travail de deux façons différentes.6

Le tableau est une structure de données. Il organise les éléments dans des cases numérotées. Dans une file, on sert d’abord le premier arrivé, comme pour les documents envoyés à une imprimante qui les traite dans leur ordre d’arrivée. Une pile donne d’abord accès au dernier élément ajouté. Dans un éditeur de texte, c’est celui que l’on veut retrouver pour annuler la dernière action. Le tableau, la file et la pile facilitent chacun certaines opérations. Pour représenter la ville de notre premier exemple, il nous faut une structure qui exprime aussi les relations entre les lieux.5

Le problème que Dijkstra emporte au café

En 1956, l’informaticien néerlandais Edsger Dijkstra cherche un problème à soumettre à l’ARMAC, le nouvel ordinateur du Centre de mathématiques d’Amsterdam, pour en montrer les capacités. Il se souvient avoir imaginé sa méthode sur une terrasse de café, sans papier ni crayon. Pour la démonstration, il dessine une carte simplifiée du réseau ferroviaire néerlandais. Une personne dans le public peut proposer deux villes. La machine imprime alors l’itinéraire le plus court, ville après ville. Dijkstra publie la méthode en 1959.7

Il faut d’abord convertir la carte en graphe. Les lieux et les carrefours sont les points du graphe, appelés sommets. Les routes sont les liens entre ces points. À chaque route, on peut associer un coût, ici un nombre de minutes. Pour retrouver les options à un carrefour, on peut conserver la liste des routes qui en partent. Le programme a ainsi accès aux voisins du point courant sans relire toute la carte. Il garde parallèlement la meilleure durée connue depuis le départ jusqu’à chacun des points découverts.

Trois trajets possibles vers la gare sur notre carte simplifiée
Trajet Durée du trajet
Route directe 9 minutes
Par la mairie 2 + 8 = 10 minutes
Par le marché 3 + 4 = 7 minutes

Au départ, le programme connaît trois durées provisoires. La mairie est à 2 minutes, le marché à 3 et la gare à 9. Il examine d’abord la mairie, qui a la plus petite durée provisoire. Continuer de là vers la gare prendrait 10 minutes au total. Il garde donc 9. Il examine ensuite le marché et ramène la durée connue jusqu’à la gare à 7 minutes. C’est seulement lorsque la gare devient le prochain point à examiner que sa durée est définitive. Le programme peut restituer le trajet en remontant les étapes qu’il a mémorisées.

C’est une stratégie gloutonne. À chaque étape, Dijkstra choisit le point non traité dont le coût total depuis le départ est le plus faible parmi les coûts connus. Pourquoi ce choix tient-il ? Pour parvenir à ce point par un détour encore inexploré, il faudrait d’abord quitter la zone déjà traitée. Le premier point de ce détour coûterait au moins autant à atteindre que le point retenu. La suite du détour pourrait seulement ajouter du temps, puisque les durées sont positives ou nulles. Dans une grande ville, une file de priorité facilite la sélection du prochain point. La priorité est donnée par le coût provisoire, à réévaluer chaque fois qu’un meilleur chemin est découvert.7

Quand faut-il explorer, revenir en arrière ou mémoriser ?

Le pari glouton peut échouer dans d’autres situations. Imaginez trois sortes de jetons valant 1, 3 et 4. Vous devez rendre 6 avec le moins de jetons possible. Prendre à chaque étape le plus gros jeton qui ne dépasse pas la somme restante donne 4 + 1 + 1. Deux jetons de 3 suffisent. Le gain immédiat procuré par le jeton de 4 laisse un reste difficile à compléter. Pour utiliser une méthode gloutonne avec confiance, il faut donc savoir ce qui, dans le problème, rend le choix local compatible avec le résultat recherché.

Pour ces jetons, on peut calculer les meilleures solutions en partant de zéro, puis pour 1, 2, 3 et ainsi de suite. Quand on arrive à 6, le programme essaie de finir avec un jeton de 1, de 3 ou de 4. Il consulte alors les réponses déjà calculées pour 5, 3 et 2, auxquelles il ajoute un jeton. Le meilleur résultat vient de 3, que l’on sait déjà obtenir avec un seul jeton. Cette manière de résoudre des sous-problèmes et de réutiliser leurs réponses s’appelle la programmation dynamique. Elle évite de refaire un même calcul chaque fois qu’il apparaît dans une combinaison différente.8

Dans un sudoku, on peut commencer par un autre type de recherche. On place un chiffre permis dans une case, puis on poursuit jusqu’à obtenir une solution ou rencontrer une contradiction. Si une case ne peut plus être remplie, on revient sur le dernier choix et on essaie une autre valeur. C’est le retour sur trace, ou backtracking. Une recherche exhaustive pourrait énumérer toutes les grilles candidates. Ici, reconnaître tôt une contradiction permet d’abandonner d’un coup toutes les solutions qui prolongeraient le mauvais choix.5

Sur une carte où chaque tronçon compte pour une seule étape, il existe une méthode adaptée à la question « combien de rues faut-il traverser ? ». On examine d’abord tous les points à une rue du départ, puis ceux à deux rues, et ainsi de suite. Une file conserve les points découverts dans l’ordre où ils devront être examinés. C’est le parcours en largeur. Un parcours en profondeur, lui, suit une branche aussi loin que possible avant de revenir essayer les autres. On peut l’utiliser pour savoir si une sortie est accessible dans un labyrinthe. Selon le problème, on cherche ici soit à atteindre un point en un minimum d’étapes, soit à explorer des possibilités et à savoir ce qui est accessible.5

Revenir à la gare, avec une meilleure question

Plus la carte s’agrandit, plus il devient intéressant d’orienter la recherche. En 1968, Peter Hart, Nils Nilsson et Bertram Raphael publient une méthode connue sous le nom d’A*. Elle estime l’intérêt de poursuivre depuis un carrefour en additionnant le coût du chemin trouvé jusque-là et une estimation de ce qu’il reste jusqu’à la destination. Si l’on minimise une distance, la distance à vol d’oiseau peut donner une borne inférieure au chemin à parcourir. Ce renseignement aide la recherche à privilégier certaines directions. On peut aussi accélérer les requêtes en préparant le réseau à l’avance. OSRM, qui utilise les données d’OpenStreetMap, propose par exemple une méthode qui découpe le réseau en zones à plusieurs niveaux.9

Sur votre téléphone, le GPS aide à vous situer. Pour calculer le trajet, il faut aussi une carte exploitable et des critères. La route la plus courte en kilomètres peut différer de la plus rapide, et un sens interdit peut rendre impossible un trajet qui semblait évident sur le dessin. Une nouvelle estimation du trafic peut à son tour changer le résultat. C’est ce qui rend les algorithmes intéressants à lire et à comparer. Il faut regarder les données qu’ils reçoivent, la règle qui guide leurs choix et la réponse qu’ils sont chargés de trouver.

Revenez aux deux trajets de l’ouverture. Pour minimiser le nombre de tronçons, prenez la route directe. Pour économiser des minutes, passez par le marché. La carte est la même. La question posée a changé, et avec elle, le chemin que vous emprunterez.

Sources et références

  1. Euclide, Éléments, livre VII, proposition 2. Voir aussi Bill Casselman, Completing the Square, American Mathematical Society, notamment la tablette YBC 6967.
  2. Menso Folkerts, Early Texts on Hindu-Arabic Calculation, 2001. Bibliothèque nationale de France, notice Dixit Algorizmi. Trésor de la langue française, étymologie d’« algorithme ». Université de St Andrews, notice sur al‑Khwarizmi.
  3. Léonard de Pise, prologue du Liber abbaci et traduction de Laurence E. Sigler. Voir la notice de l’université de St Andrews.
  4. Ada Lovelace, Note G, 1843. Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. Peter Naur (éd.), Revised Report on the Algorithmic Language ALGOL 60, 1963.
  5. NIST, Dictionary of Algorithms and Data Structures. Robert Sedgewick et Kevin Wayne, tableau des algorithmes et des structures de données, université de Princeton.
  6. Tony Hoare, entretien avec le Computer History Museum et Quicksort, 1962.
  7. Edsger W. Dijkstra, From my Life, récit rétrospectif, et A Note on Two Problems in Connexion with Graphs, article de 1959 accompagné d’un retour sur la démonstration à l’ARMAC.
  8. MIT OpenCourseWare, Design and Analysis of Algorithms, séance sur la programmation dynamique, exemple du rendu de monnaie.
  9. Peter E. Hart, Nils J. Nilsson et Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, 1968. OSRM, documentation du découpage du réseau pour le calcul d’itinéraires.

Publications similaires

  • Speedcoding

    En 1953, alors que l’informatique n’en est encore qu’à ses débuts, IBM introduit un système de programmation qui va profondément transformer la manière d’utiliser les ordinateurs scientifiques : Speedcoding. Speedcoding est un système de programmation scientifique développé par IBM en 1953 pour l’IBM 701, sous la supervision de John W. Backus. Il simplifie l’écriture des…

  • LISP

    À la fin des années 1950, les ordinateurs savent déjà effectuer rapidement des calculs numériques. Avec FORTRAN, les scientifiques disposent même d’un langage de haut niveau efficace pour exprimer leurs formules. Mais les chercheurs qui commencent à travailler sur l’intelligence artificielle rencontrent un autre problème : ils veulent manipuler des symboles, des règles logiques, des…

  • ADA

    Ada est un langage de programmation créé à la demande du département de la Défense des États-Unis (DoD) à la fin des années 1970. Son objectif est inhabituel : il ne s’agit pas seulement de faciliter l’écriture des programmes, mais aussi de rendre plus fiables des logiciels complexes destinés à fonctionner pendant de nombreuses années….

  • BCPL

    BCPL signifie Basic Combined Programming Language : une version simplifiée de CPL, conçue pour écrire des compilateurs et des logiciels système plus faciles à transporter d’une machine à l’autre. Au milieu des années 1960, les langages de programmation deviennent plus expressifs, mais leurs compilateurs restent souvent longs et difficiles à adapter. Un langage peut être…

  • BASIC

    Le BASIC est un langage de programmation créé en 1964 au Dartmouth College par John G. Kemeny et Thomas E. Kurtz pour rendre l’informatique accessible aux débutants. Son nom signifie Beginner’s All-purpose Symbolic Instruction Code. Associé dès l’origine au temps partagé, BASIC permet à un étudiant de saisir quelques lignes, lancer son programme, voir immédiatement…

  • Java

    En mai 1995, Sun Microsystems présente un nouveau langage de programmation : Java. Il doit permettre à un même logiciel de fonctionner sur des ordinateurs très différents. Pourtant, quelques années plus tôt, ses créateurs ne songeaient pas particulièrement aux ordinateurs personnels, encore moins aux pages Web. Ils travaillaient sur des téléviseurs et d’autres équipements électroniques….