L'algorithmique et ses applications
Chercher, trier, s'appeler soi-même, compresser un texte, classer le Web et chiffrer un secret : cinq planches pour regarder travailler les algorithmes, compter leurs opérations et vérifier qu'ils tiennent leurs promesses.
Qu'est-ce qu'un algorithme ?
Un algorithme est une suite finie d'instructions précises qui, appliquée à des données (l'entrée), produit un résultat (la sortie) en un nombre fini d'étapes. Le mot vient du nom du savant persan al-Khwârizmî (IXe siècle), dont les traités ont fait connaître en Europe le calcul avec les chiffres indo-arabes. Une recette de cuisine, la division posée apprise à l'école ou l'itinéraire calculé par un GPS sont des algorithmes ; un programme n'est qu'un algorithme écrit dans une langue que la machine comprend.
Devant un algorithme, on se pose toujours trois questions :
On écrit par exemple O(n²) (« grand O de n carré ») pour dire que le nombre d'opérations croît au plus comme n², à un facteur constant près. La figure ci-dessous montre pourquoi cette question domine toutes les autres : on y lit le temps de calcul d'une machine qui exécute un milliard d'opérations par seconde, selon la complexité de l'algorithme.
Chercher : lire tout, ou couper en deux ?
Question : pour retrouver un nom dans un annuaire de n noms rangés par ordre alphabétique, faut-il les lire un par un ? La recherche séquentielle compare la cible à chaque case, dans l'ordre. La recherche dichotomique (du grec « couper en deux ») regarde la case du milieu, élimine la moitié qui ne peut pas contenir la cible, et recommence sur l'autre moitié.
Ici ⌊x⌋ désigne la partie entière de x, et log₂ n le nombre de fois qu'on peut diviser n par 2 avant de tomber sous 1. Chaque case ci-dessous contient une valeur ; les valeurs sont rangées par ordre croissant.
Trier : cinq méthodes, deux familles
Question : comment ranger n valeurs par ordre croissant, et combien de comparaisons cela coûte-t-il ? Voici cinq méthodes classiques, chacune décrite en une phrase.
- Sélection : on cherche la plus petite valeur, on la met en tête, et on recommence avec le reste.
- Insertion : comme on range des cartes dans sa main, chaque nouvelle valeur glisse vers la gauche jusqu'à sa place.
- Bulles : on compare les voisins deux à deux et on les échange s'ils sont mal rangés ; les grandes valeurs remontent comme des bulles.
- Fusion : on coupe la liste en deux, on trie chaque moitié par la même méthode, puis on fusionne deux listes déjà triées.
- Rapide (quicksort) : on choisit un pivot (ici la dernière valeur), on place les plus petites à sa gauche et les plus grandes à sa droite, puis on recommence de chaque côté.
Une inversion est un couple de valeurs mal rangées l'une par rapport à l'autre ; une liste triée n'en a aucune, une liste inversée en a n(n − 1)/2. Elles servent de contrôle : le tri à bulles fait exactement un échange par inversion.
La course : comparaisons mesurées selon la taille
La récursivité : se rappeler soi-même
Une fonction récursive est une fonction qui s'appelle elle-même sur un problème plus petit, jusqu'à un problème assez simple pour être résolu directement : le cas de base. C'est la forme naturelle de « diviser pour régner », déjà à l'œuvre dans la dichotomie et le tri fusion.
Les tours de Hanoï
Pour déplacer k disques de A vers C sans jamais poser un disque sur un plus petit : déplacer les k − 1 disques du dessus de A vers B, puis le grand disque de A vers C, puis les k − 1 disques de B vers C. Le nombre de coups vérifie h(k) = 2h(k − 1) + 1, d'où h(k) = 2k − 1.
Fibonacci et l'arbre des appels
F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2). Programmée telle quelle, la fonction recalcule sans cesse les mêmes valeurs. La mémoïsation — garder chaque résultat dans un carnet et le relire au lieu de le recalculer — supprime ces doublons.
Application : compresser un texte avec Huffman
En informatique, chaque caractère occupe ordinairement 8 bits (un octet ; un bit vaut 0 ou 1). Mais pourquoi coder « e », très fréquent, avec autant de bits que « z », très rare ? L'algorithme de Huffman (1952) construit un code de longueur variable : on prend les deux symboles les moins fréquents, on les réunit sous un nœud dont le poids est la somme de leurs effectifs, et l'on recommence jusqu'à n'avoir plus qu'un seul arbre. Le chemin de la racine à une feuille donne le code du caractère : 0 à gauche, 1 à droite.
Le code obtenu est un code préfixe : aucun code n'est le début d'un autre, si bien qu'on décode sans séparateur. Sa qualité se mesure à l'entropie de Shannon H = −Σ p log₂ p (où p est la fréquence de chaque caractère) : aucun code ne peut descendre en moyenne sous H bits par caractère, et Huffman garantit H ≤ L < H + 1, où L est la longueur moyenne de son code.
Début du texte codé (chaque caractère suivi de son code) :
Signature : deux algorithmes qui ont changé Internet
Deux applications à grande échelle, où les idées des planches précédentes — itérer, compter les opérations, exploiter un écart de complexité — deviennent décisives.
Comment classer des milliards de pages ? L'idée de Sergey Brin et Larry Page (1998) : une page est importante si des pages importantes pointent vers elle. On l'imagine avec un surfeur aléatoire qui, à chaque clic, suit au hasard l'un des liens de la page avec la probabilité d (le facteur d'amortissement, 0,85 en pratique), ou saute vers une page quelconque avec la probabilité 1 − d ; d'une page sans lien, il saute toujours au hasard. Le PageRank d'une page est la proportion du temps que le surfeur y passe à long terme.
On calcule ce classement par trois chemins indépendants : on simule le surfeur ; on itère la formule à partir de valeurs égales (méthode de la puissance) ; on résout exactement le système linéaire de N équations par l'élimination de Gauss.
Comment envoyer un secret à quelqu'un qu'on n'a jamais rencontré ? Le chiffrement RSA (Rivest, Shamir et Adleman, 1977) repose sur une dissymétrie : multiplier deux nombres premiers est facile, retrouver ces deux nombres à partir de leur produit est extrêmement difficile. On note a mod n le reste de la division de a par n.
- On choisit deux nombres premiers p et q, on calcule n = pq et φ(n) = (p − 1)(q − 1).
- On choisit e sans diviseur commun avec φ(n) : la clé publique est (n, e), connue de tous.
- L'algorithme d'Euclide étendu fournit d tel que e·d mod φ(n) = 1 : c'est la clé privée.
- On chiffre c = me mod n et l'on déchiffre m = cd mod n, par exponentiation rapide : on lit l'exposant en binaire, on élève au carré à chaque chiffre et on multiplie quand le chiffre vaut 1.
Euclide étendu : trouver la clé privée
À chaque ligne, le reste r s'obtient en retranchant q fois la ligne précédente ; le coefficient t suit le même calcul, si bien que r et t·e ont toujours le même reste modulo φ(n) — contrôlé dans la dernière colonne.
Le message chiffré puis déchiffré
Repères historiques
- vers −300Euclide décrit, au livre VII des Éléments, l'algorithme du plus grand commun diviseur — celui qu'utilise encore RSA.
- vers 825Al-Khwârizmî rédige ses traités de calcul indien et d'algèbre ; la forme latine de son nom donnera « algorithme ».
- 1843Ada Lovelace publie un programme de calcul des nombres de Bernoulli pour la machine analytique de Charles Babbage.
- 1936Alan Turing définit mathématiquement le calcul mécanique et montre que certains problèmes n'ont aucun algorithme.
- 1945John von Neumann décrit le tri fusion.
- 1952David Huffman invente ses codes de longueur minimale.
- 1959Edsger Dijkstra publie son algorithme du plus court chemin.
- 1961Tony Hoare publie le tri rapide.
- 1968Donald Knuth fait paraître le premier volume de The Art of Computer Programming.
- 1971Stephen Cook pose les bases de la NP-complétude ; la question « P = NP ? » reste ouverte.
- 1977Rivest, Shamir et Adleman publient le chiffrement RSA.
- 1998Sergey Brin et Larry Page présentent PageRank, cœur du moteur Google.
Compter avant de programmer
La complexité se mesure en nombre d'opérations selon la taille n. Entre log n, n log n, n² et 2n, l'écart dépasse vite ce que peut rattraper n'importe quelle machine.
Diviser pour régner
Couper le problème en deux — dichotomie, tri fusion, exponentiation rapide — fait apparaître un log₂ n ; retenir ce qu'on a déjà calculé évite les explosions de la récursivité.
Des algorithmes partout
Compression des fichiers, classement des pages du Web, sécurité des paiements : chaque fois, une idée simple, une complexité maîtrisée et des contrôles qui prouvent que le résultat est juste.
Pour aller plus loin
- Le plus court chemin (Dijkstra, Bellman-Ford, Floyd-Warshall) : page le plus court chemin.
- Les problèmes où l'on ne connaît pas d'algorithme rapide : le voyageur de commerce et le sac à dos.
- Thèmes non traités ici : les tables de hachage (retrouver une donnée en temps presque constant), les graphes, la machine de Turing et la calculabilité, la question P = NP.
- Les chiffres de cette page sont tous calculés dans le navigateur, puis confrontés à une formule exacte ou à une méthode indépendante.