Algorithmes et complexité

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• définir ce qu'est un algorithme et le distinguer d'une recette, d'une heuristique et d'un programme;
• lire et écrire un algorithme dans le pseudocode du cours, et expliquer pourquoi ce cours n'utilise pas un langage de programmation pour cela;
• démontrer la correction d'un algorithme itératif à l'aide d'un invariant de boucle, et sa terminaison à l'aide d'une quantité qui décroît strictement dans un ensemble bien fondé;
• compter le coût d'un algorithme en opérations élémentaires, distinguer le meilleur cas, le pire cas et le cas moyen, et dire pourquoi on ne compte pas des secondes;
• énoncer précisément les définitions de $O$, $\Omega$ et $\Theta$ avec leurs quantificateurs, et les utiliser sans leur faire dire ce qu'elles ne disent pas;
• analyser le tri par sélection, le tri par insertion et la recherche séquentielle, et estimer la plus grande taille d'entrée traitable dans un temps donné;
• décrire l'architecture de von Neumann et dérouler à la main le cycle chercher–décoder–exécuter d'un petit programme, puis calculer le temps d'accès moyen d'une hiérarchie de caches et traduire une adresse virtuelle en adresse physique.

Qu'est-ce qu'un algorithme?

Une définition de travail

Le mot vient du nom du mathématicien persan al-Khwārizmī (IX^e siècle), dont le traité de calcul, traduit en latin, a donné à l'Occident la numération de position et les procédés de calcul écrit que vous utilisez encore pour poser une addition. Le mot désigne aujourd'hui l'objet central de l'informatique.

Il faut insister sur la troisième et la quatrième: elles ne vont pas de soi et elles se démontrent. Une suite d'instructions non ambiguës qui boucle indéfiniment sur certaines entrées n'est pas un algorithme pour ces entrées; une suite d'instructions qui s'arrête toujours mais renvoie parfois une mauvaise réponse n'est pas non plus un algorithme du problème posé. Le chapitre 5 montrera qu'il est en général impossible de décider mécaniquement si un texte donné s'arrête sur toutes ses entrées: la terminaison est une propriété qu'on prouve à la main, pas une propriété qu'une machine vérifie pour nous.

Un algorithme est indépendant de la machine qui l'exécute et du langage dans lequel on l'écrit. L'algorithme d'Euclide est le même que vous l'exécutiez avec un crayon, en Python sur un ordinateur portable ou avec des cailloux; ce qui change est le temps par étape, pas le nombre d'étapes.

Ce qu'un algorithme n'est pas

Une recette de cuisine. La comparaison est traditionnelle et instructive surtout par ses échecs. «Salez à votre goût», «faites revenir jusqu'à ce que ce soit doré», «ajoutez une pincée de sel» sont ambigus: deux cuisiniers obtiennent deux résultats. «Laissez reposer la pâte une heure» est non ambigu, mais la recette n'a ni entrée variable ni spécification de sortie vérifiable. Une recette est une procédure; il lui manque la précision et la spécification qui font l'algorithme.

Une heuristique. Une heuristique est une méthode qui donne souvent une bonne réponse, vite, sans garantie. «Pour aller d'une ville à l'autre, prenez toujours la route qui vous rapproche le plus de la destination» termine et est non ambiguë, mais elle peut vous mener dans une impasse: elle n'est pas correcte. Les heuristiques sont indispensables dans la pratique — la plupart des problèmes d'optimisation industriels sont traités ainsi — mais elles se jugent à leur qualité mesurée, pas à une démonstration de correction. Nous y reviendrons au chapitre 5 avec les problèmes NP-complets, pour lesquels on ne connaît pas d'algorithme exact rapide.

Un programme. Un programme est la réalisation d'un algorithme dans un langage de programmation, pour une machine donnée. Le même algorithme admet des milliers de programmes. Réciproquement, un programme contient beaucoup de choses qui ne relèvent pas de l'algorithme: la lecture d'un fichier, la gestion de la mémoire, le format d'affichage, les messages d'erreur.

Le plus vieil algorithme: Euclide

L'algorithme d'Euclide, décrit dans les Éléments (livre VII, vers 300 av. J.-C.), calcule le plus grand commun diviseur (greatest common divisor, gcd) de deux entiers. Il est probablement plus ancien qu'Euclide lui-même, et il est resté d'usage courant: c'est lui qui, au chapitre 9, permettra de calculer l'exposant privé du chiffrement RSA.

L'idée tient en une identité. Si $a=qb+r$ avec $0\le r<b$, alors tout diviseur commun de $a$ et $b$ divise $r=a-qb$, et tout diviseur commun de et divise : les deux paires ont , donc le même pgcd:

On remplace donc le couple $(a,b)$ par $(b,a\mathrm{mod}b)$ jusqu'à ce que le second terme soit nul, et l'on lit le pgcd dans le premier.

Écrire un algorithme: le pseudocode

Les conventions de ce cours

Un algorithme doit être écrit quelque part. Nous utilisons un pseudocode en français, assez précis pour être non ambigu, assez souple pour ne pas se noyer dans la syntaxe d'un langage. Voici les conventions, fixées une fois pour toutes:

Les indices vont de 1 à n, comme en mathématiques. Attention: Python, comme la plupart des langages, numérote de $0$ à $n-1$; les traductions ci-dessous en tiennent compte. L'algorithme d'Euclide s'écrit alors:

Euclide(a, b)              // a ≥ 0, b ≥ 0, non tous deux nuls
  tant que b ≠ 0 faire
    r ← a mod b            // reste de la division euclidienne
    a ← b
    b ← r
  fin tant que
  retourner a              // a = pgcd(a₀, b₀)

et la version Python, qui fait exactement la même chose:

def euclide(a, b):
    """pgcd de a et b par divisions successives."""
    while b != 0:
        a, b = b, a % b    # affectation simultanée
    return a

Exécutée sur euclide(1071, 462), cette fonction renvoie 21, et math.gcd(1071, 462) renvoie également 21: les deux valeurs ont été obtenues en exécutant le code, non en le lisant.

Pourquoi du pseudocode plutôt qu'un langage

Trois raisons, dans cet ordre d'importance.

Séparer l'idée de sa réalisation. Le pseudocode ne dit rien du typage, de la gestion de la mémoire ou des bibliothèques disponibles. Ce qui reste est exactement ce dont on prouve la correction et dont on compte le coût. Quand nous écrirons «$T(n)=n(n-1)/2$ comparaisons», cette affirmation vaudra pour tout programme fidèle à l'algorithme, en Python, en C ou en tableur.

Éviter les faux amis. En Python, a, b = b, a % b est une affectation simultanée; en C, il faudrait une variable temporaire. En Python, liste1 + liste2 recopie les deux listes, ce qui coûte $\Theta (n)$ là où le lecteur croit lire une opération élémentaire. Le pseudocode n'a pas d'opération dont le coût soit caché: chaque ligne coûte ce qu'elle a l'air de coûter.

Rester lisible par un humain. Un algorithme est d'abord une idée qu'on communique. Les Éléments d'Euclide n'ont ni accolades ni point-virgules et se lisent encore vingt-trois siècles plus tard.

La correction: invariants et terminaison

Comment savoir qu'un algorithme fait bien ce qu'on lui demande? Tester ne suffit pas: un test montre la présence d'un défaut, jamais son absence. La correction se démontre, et la démonstration d'un algorithme itératif a toujours deux moitiés: un invariant pour la correction, un variant pour la terminaison.

L'invariant de boucle

C'est une récurrence déguisée: l'initialisation est le cas de base, la conservation est l'hérédité, et le troisième point est la lecture du résultat. L'art consiste à trouver le bon invariant — assez fort pour conclure, assez faible pour être conservé.

Prenons l'algorithme le plus simple qui soit, la somme des éléments d'un tableau:

Somme(A)
  s ← 0
  pour i de 1 à A.longueur faire
    s ← s + A[i]
  fin pour
  retourner s

Démonstration. Prenons pour invariant la propriété

Initialisation. Avant le premier tour, $i=1$ et $s=0$; la somme vide ${\sum }_{k=1}^{0}A[k]$ vaut $0$ par convention. Donc $P(1)$ est vraie.

Conservation. Supposons $P(i)$ vraie pour un $i$ avec $1\le i\le n$. Le corps de la boucle remplace $s$ par $s+A[i]$, c'est-à-dire par ${\sum }_{k=1}^{i-1}A[k]+A[i]={\sum }_{k=1}^{i}A[k]$, puis le compteur passe à . Au début du tour suivant, : c'est .

Terminaison. La boucle s'arrête lorsque le compteur atteint $n+1$. L'invariant $P(n+1)$ donne alors $s={\sum }_{k=1}^{n}A[k]$, qui est bien la valeur retournée. $\square$

La démonstration paraît lourde pour un résultat évident. C'est précisément l'intérêt de l'exercice: la même mécanique s'applique sans changement à des algorithmes dont le résultat n'a rien d'évident, et c'est elle qui fait apparaître les erreurs de bord — un pour i de 2 à n au lieu de 1 à n, un s ← A[i] au lieu de s ← s + A[i]. Un invariant qui ne se conserve pas signale exactement la ligne fautive.

La terminaison: un variant dans un ensemble bien fondé

Une boucle pour i de 1 à n termine par construction. Une boucle tant que ne termine pas par construction: il faut le prouver.

L'argument est immédiat: si la boucle effectuait une infinité de tours, les valeurs successives de $V$ formeraient une suite infinie strictement décroissante dans $E$, ce que la bonne fondation interdit.

Les deux mots comptent. Strictement: une quantité qui décroît au sens large peut stagner indéfiniment. Bien fondé: une quantité réelle positive qui décroît strictement peut très bien ne jamais s'arrêter — la suite $V_k=1/k$ décroît strictement dans ${\mathbb{R}}_{>0}$, qui n'est pas bien fondé, et la boucle correspondante tourne pour toujours. C'est pourquoi on choisit presque toujours un variant entier positif: le nombre d'éléments non encore traités, la valeur d'une variable, la différence entre une borne et un compteur.

Démonstration. Terminaison. Prenons pour variant $V=b$, la valeur courante de la seconde variable. Elle est entière et positive ou nulle tout au long de l'exécution, car un reste de division euclidienne l'est. À chaque tour, la nouvelle valeur de $b$ est $r=a\mathrm{mod}b$, qui vérifie $0\le r<b$ par définition du reste: $V$ décroît à chaque tour, dans l'ensemble bien fondé . La boucle s'arrête donc après un nombre fini de tours, et comme part de et diminue d'au moins par tour, ce nombre est au plus .

Correction. Prenons pour invariant

Initialisation: au premier passage, $(a,b)=(a_0,b_0)$ et $I$ est trivialement vraie. Conservation: supposons $I$ vraie et $b\ne 0$. Le tour remplace par , et l'identité (2.1) donne ; de plus la nouvelle première composante vaut , donc le couple reste non nul. : la boucle s'arrête avec , donc avec , et l'invariant donne . Or puisque tout entier divise . La valeur retournée est donc bien .

La borne «au plus $b_0$ divisions» est correcte mais très mauvaise: sur $(1071,462)$ elle annonce au plus 462 divisions, il y en a eu 3. L'exercice 2.1 de ce chapitre établit le vrai majorant — la première variable est divisée par deux au moins tous les deux tours, d'où au plus $2{\log }_2{a}_0$ divisions, soit un coût logarithmique en la valeur et donc linéaire en le nombre de chiffres — et son point 3 exhibe le pire cas, atteint sur deux termes consécutifs de la suite de Fibonacci. Noter la borne grossière d'abord, puis la raffiner, est une démarche normale: la terminaison et le coût sont deux questions distinctes.

Le coût d'un algorithme

Que compter, et pourquoi pas des secondes

La question naturelle — «combien de temps cela prend-il?» — est la mauvaise question, pour quatre raisons.

Une mesure en secondes dépend de la machine. Le même programme s'exécute dix fois plus vite sur un serveur récent que sur un téléphone d'il y a cinq ans. Le résultat mesuré parle du matériel autant que de l'algorithme.

Elle dépend de tout le reste. Langage, compilateur et ses options, système d'exploitation, autres processus, état des mémoires caches: deux exécutions consécutives du même programme sur la même machine ne donnent pas le même temps.

Elle n'est pas prédictive. On veut savoir ce qui se passera sur un million d'éléments après avoir mesuré sur mille. Une seconde mesurée ne s'extrapole pas; un nombre d'opérations, si.

Elle vieillit. Un chiffre de temps publié aujourd'hui sera faux dans trois ans. Un nombre d'opérations est une propriété mathématique de l'algorithme: il ne vieillit jamais.

On compte donc des opérations élémentaires: affectations, comparaisons, opérations arithmétiques, accès à une case de tableau — chacune supposée de coût constant, indépendant des valeurs manipulées. Ce modèle s'appelle la machine RAM (random access machine). Il est faux dans le détail (une multiplication coûte plus cher qu'une addition, un accès mémoire hors cache coûte cent fois un accès en cache) mais il est faux d'un facteur constant, et c'est exactement ce que l'analyse asymptotique accepte d'ignorer.

En pratique on ne compte même pas toutes les opérations: on choisit une opération dominante, celle dont le nombre est proportionnel au travail total. Pour un tri, c'est la comparaison entre deux éléments (parfois l'échange, quand déplacer coûte cher). Pour une recherche, c'est le test d'égalité. Pour Euclide, c'est la division. Compter l'opération dominante donne le bon ordre de grandeur et rend l'analyse faisable à la main.

La taille de l'entrée

Le choix n'est pas anodin. Tester si un entier $N$ est premier en essayant tous les diviseurs jusqu'à $\sqrt{N}$ demande environ $\sqrt{N}$ divisions: c'est peu si l'on compte en fonction de , mais l'entrée est l'écriture de , longue de bits, et est . Un entier de 2048 bits, comme ceux du chapitre 9, mettrait cette méthode hors de portée pour toujours. Nous dirons toujours en quoi se compte.

Meilleur cas, pire cas, cas moyen

Deux entrées de même taille ne coûtent pas forcément la même chose. Soit $D_n$ l'ensemble des entrées de taille $n$ et $T(x)$ le nombre d'opérations dominantes effectuées sur l'entrée $x$.

Le pire cas est la mesure de référence, pour trois raisons: il donne une garantie valable sur toute entrée; il est souvent atteint par les entrées réelles (un fichier déjà trié, une liste presque triée); et il ne demande aucune hypothèse sur la provenance des données.

Le cas moyen est plus informatif quand il est calculable, mais il n'a de sens qu'avec sa loi. «Le tri par insertion fait en moyenne $n^2/4$ comparaisons» est une phrase incomplète: incomplète de «lorsque l'entrée est une permutation tirée uniformément parmi les $n!$ permutations de $n$ éléments distincts». Si vos données arrivent presque triées — ce qui est fréquent —, cette moyenne ne décrit pas votre situation, et le tri par insertion se comporte bien mieux qu'elle ne le laisse croire.

Le meilleur cas ne sert presque jamais à juger un algorithme, mais il sert à en comprendre le comportement: un algorithme dont le meilleur cas est linéaire et le pire quadratique est un algorithme adaptatif, qui exploite la structure déjà présente dans l'entrée.

Les notations asymptotiques

Compter exactement les opérations est possible pour de petits algorithmes, pénible pour les autres, et surtout inutile: le résultat dépend de conventions arbitraires (compte-t-on l'incrémentation du compteur de boucle?) qui ne changent le total que d'un facteur constant. Ce qui importe est la loi de croissance du coût quand $n$ grandit. Les trois notations qui suivent capturent exactement cela.

Grand O: une borne supérieure

Les deux quantificateurs sont l'essentiel de la définition. «Il existe $c$» autorise à ignorer tout facteur constant. «Il existe $n_0$» autorise à ignorer tout comportement en petites tailles. Ce que $O$ affirme, c'est une propriété de la queue du comportement, à une constante multiplicative près.

L'égalité de la notation $f(n)=O(g(n))$ est un abus d'écriture universellement toléré: $O(g(n))$ désigne en réalité un ensemble de fonctions, et il faudrait écrire $f\in O(g)$. On ne peut donc pas retourner l'égalité: $O(n)=n$ n'a aucun sens, et de $f=O(n^2)$ et on ne conclut évidemment pas .

Grand Oméga: une borne inférieure

$\Omega$ sert à énoncer des limites de principe: tout algorithme qui trie par comparaisons fait $\Omega (n\log n)$ comparaisons dans le pire cas (chapitre 3); tout algorithme qui lit son entrée fait $\Omega (n)$ opérations. Une borne inférieure ne parle pas d'un algorithme, mais du problème: elle dit qu'aucun algorithme, présent ou futur, ne peut faire mieux.

Grand Théta: l'ordre exact

Démonstration. (1) Si $f=\Theta (g)$, les constantes $c_2$ et $c_1$ de (2.4) fournissent immédiatement (2.2) et (2.3). Réciproquement, si $f\le cg$ pour $n\ge n_1$ et pour , alors les deux inégalités valent simultanément pour , avec et .

(2) Pour $n\ge 1$, chaque $n^k$ avec $k\le d$ vérifie $n^k\le n^d$, donc

ce qui donne la majoration avec $c_2={\sum }_k|a_k|$. Pour la minoration, posons $S={\sum }_{k<d}|a_k|$. Pour ,

dès que $a_{d}n-S\ge \frac{a_d}{2}n$, c'est-à-dire dès que $n\ge 2S/a_d$. On prend donc et .

(3) Par définition de la limite avec $\epsilon =L/2$, il existe $n_0$ tel que $L/2\le f(n)/g(n)\le 3L/2$ pour $n\ge n_0$, d'où (2.4) avec et .

Le point 2 est la règle pratique: on ne garde que le terme de plus haut degré et on jette son coefficient. Le point 3 en donne la version «par les limites», souvent la plus rapide à appliquer.

Les classes de croissance

En pratique, le coût des algorithmes se range dans une poignée de classes. Les voici, avec le nombre d'opérations qu'elles demandent pour trois tailles, et la plus grande taille traitable en une seconde.

Toutes les valeurs de ce tableau ont été calculées en Python, avec des entiers exacts pour les puissances et les factorielles, et la dernière colonne par recherche dichotomique sur la fonction de coût elle-même. Quelques repères pour la lire:

• La colonne de droite est la seule qui compte pour un ingénieur. Elle répond à «jusqu'où puis-je aller?». Un algorithme cubique traite mille éléments par seconde; un algorithme quadratique en traite trente et un mille; un algorithme quasi-linéaire en traite quarante millions.
• Le passage de $n^2$ à $n{\log }_{2}n$ change la nature du problème, pas seulement sa vitesse: on passe de dizaines de milliers d'éléments à des dizaines de millions, soit un facteur 1 253.
• Deux classes sont hors jeu. À $10^9$ opérations par seconde, un algorithme en $\Theta (2^n)$ traite en une seconde et en 36,5 ans; un algorithme en traite . Gagner un facteur mille sur la machine fait passer à et à : . C'est pourquoi le chapitre 5 parlera de problèmes «intraitables» et non de problèmes «lents».

La figure 2.1 rend visible ce que le tableau énumère. Sur une double échelle logarithmique, $n$, $n{\log }_{2}n$, $n^2$ et $n^3$ sont des droites (ou presque, pour la deuxième) de pentes croissantes: elles diffèrent d'un facteur, pas d'une nature. La courbe $2^n$, elle, n'est pas une droite: elle traverse les dix-huit décades de l'axe vertical alors que n'a pas atteint . La distance entre les points de franchissement — 29, puis 31 622, puis presque quarante millions, puis un milliard — est la mesure honnête de ce qui sépare ces classes.

Deux tris élémentaires

Trier est l'exemple canonique, pour trois raisons: le problème est facile à énoncer, les algorithmes se comptent à la main, et les écarts entre eux sont spectaculaires. Nous prenons le tableau du cours, celui que le chapitre 3 reprendra pour le tri fusion:

dont le résultat trié est $[3,9,10,27,38,43,82]$. Tous les comptages qui suivent ont été obtenus en exécutant les deux algorithmes en Python avec un compteur, jamais en les lisant.

Le tri par sélection

L'idée: chercher le plus petit élément, le mettre en première position, recommencer sur le reste.

TriSelection(A)
  n ← A.longueur
  pour i de 1 à n − 1 faire
    m ← i                            // indice du minimum du suffixe
    pour j de i + 1 à n faire
      si A[j] < A[m] alors m ← j fin si
    fin pour
    si m ≠ i alors échanger A[i] et A[m] fin si
  fin pour

L'invariant de la boucle externe est: au début du tour $i$, les cases $A[\mathrm{1..}i-1]$ contiennent les $i-1$ plus petits éléments du tableau initial, rangés en ordre croissant, et elles ne bougeront plus. Il est vrai avant le premier tour (préfixe vide), conservé par la recherche du minimum du suffixe, et donne à la sortie ($i=n$) un tableau trié: la dernière case contient le maximum, faute de concurrent.

Sur le tableau du cours, l'exécution donne:

Comptage réel (Python): 21 comparaisons, 5 échanges. Les 21 comparaisons se lisent directement sur l'algorithme: le tour $i$ en fait $n-i$, donc

soit $7\cdot 6/2=21$ pour $n=7$. Ce nombre ne dépend pas du contenu du tableau: les deux boucles sont bornées, aucune n'a de sortie anticipée. Vérifié en Python: sur le tableau déjà trié comme sur le tableau trié à l'envers, le compteur affiche 21.

C'est un algorithme non adaptatif: lui donner un tableau déjà trié ne lui fait rien gagner. Son seul atout est le nombre d'échanges, au plus $n-1$ (5 ici, et l'énumération exhaustive des $5040$ permutations de sept éléments distincts donne un minimum de 0 et un maximum de 6). Quand déplacer un élément coûte très cher — de gros enregistrements sur disque — cet atout compte.

Le tri par insertion

L'idée est celle du joueur de cartes: on prend les éléments un par un et on insère chacun à sa place dans la partie déjà triée, en décalant ce qui doit l'être.

TriInsertion(A)
  pour i de 2 à A.longueur faire
    x ← A[i]                         // l'élément à insérer
    j ← i − 1
    tant que j ≥ 1 et A[j] > x faire  // on compare, puis on décale
      A[j + 1] ← A[j]
      j ← j − 1
    fin tant que
    A[j + 1] ← x
  fin pour

L'invariant de la boucle externe: au début du tour $i$, le sous-tableau $A[\mathrm{1..}i-1]$ contient les $i-1$ premiers éléments du tableau initial, triés. La boucle interne termine parce que $j$ décroît strictement dans $\{0,1,\dots ,i-1\}$, ensemble fini donc bien fondé. À la sortie, $i=n+1$ et est trié — remarquez qu'ici, contrairement au tri par sélection, les éléments du préfixe ne sont pas les plus petits du tableau, mais bien les premiers arrivés.

Deux étapes méritent d'être suivies à la main. À l'étape 3, on insère $3$: il est plus petit que $43$, que $38$ et que $27$, on le décale donc jusqu'en tête — 3 comparaisons et 3 décalages. À l'étape 5, on insère $82$: une seule comparaison avec $43$ suffit à constater qu'il est déjà bien placé — 1 comparaison, aucun décalage. C'est là toute la différence avec le tri par sélection: le tri par insertion s'arrête dès qu'il peut.

Démonstration. L'étape $i$ (insertion de $A[i]$ dans le préfixe trié de longueur $i-1$) fait au moins une comparaison — celle qui teste A[i−1] > x — et au plus $i-1$, lorsque $x$ va en tête et que la boucle s'arrête faute de cases, sans comparaison finale. Sommer les bornes sur $i=2,\dots ,n$ donne $n-1$ et . Les deux bornes sont atteintes: la première par un tableau croissant, la seconde par un tableau décroissant.

Pour le cas moyen, notons $p\in \{1,\dots ,i\}$ la position finale de $x$ dans le préfixe de longueur $i$. Sous la loi uniforme sur les permutations, $p$ est uniforme sur ces $i$ positions. Si $p\ge 2$, l'algorithme effectue $i-p$ décalages puis une comparaison qui échoue, soit comparaisons; si , il décale fois et sort parce que atteint , soit comparaisons. L'espérance de l'étape vaut donc , ce qui est l'expression (2.6). Le terme dominant est , dont la somme sur vaut : le cas moyen est bien quadratique, environ la moitié du pire cas.

La formule (2.6) a été confrontée à l'énumération exhaustive en Python: $T_{\text{moy}}(7)=2087/140=14,9071$ et $T_{\text{moy}}(8)=5399/280=19,2821$, reproduits exactement par les et permutations.

La figure 2.3 illustre un point que l'analyse asymptotique masque et que l'ingénieur doit voir: la moyenne et le pire cas sont dans la même classe. Passer de $n^2/2$ à $n^2/4$ divise le temps par deux, ce qui est appréciable mais ne change ni la courbe ni la taille maximale traitable d'un facteur significatif ($\sqrt{2}\approx 1,41$). La seule chose qui change vraiment la classe est le , linéaire: c'est ce qui rend le tri par insertion excellent sur des données presque triées, et c'est pourquoi les bibliothèques standard l'utilisent encore — à l'intérieur d'algorithmes plus rapides, sur les petits sous-tableaux.

La recherche séquentielle

Après trier, chercher. Le problème: déterminer si une valeur $v$ figure dans un tableau $A$ de $n$ éléments, et si oui à quelle position.

RechercheSequentielle(A, v)
  pour i de 1 à A.longueur faire
    si A[i] = v alors retourner i fin si
  fin pour
  retourner ABSENT                 // sentinelle: v ne figure pas dans A

L'invariant est: au début du tour $i$, la valeur $v$ ne figure pas dans $A[\mathrm{1..}i-1]$. Il est vrai au départ (préfixe vide) et conservé par le test. Si la boucle s'achève sans retour, l'invariant avec $i=n+1$ dit que $v$ n'est nulle part: la réponse «absent» est justifiée. La terminaison est acquise, la boucle étant bornée.

Le coût, en nombre de comparaisons:

• meilleur cas: 1 comparaison, la valeur est en tête — $\Theta (1)$;
• pire cas: $n$ comparaisons, la valeur est en queue ou absente — $\Theta (n)$;
• cas moyen, si la valeur est présente et sa position uniforme sur $\{1,\dots ,n\}$: $\frac{1}{n}{\sum }_{k=1}^{n}k=\frac{n+1}{2}$ comparaisons — également.

Sur le tableau du cours, chercher $9$ coûte 5 comparaisons (il est en cinquième position), chercher $100$ en coûte 7 et échoue, et la moyenne sur les sept valeurs présentes vaut $(7+1)/2=4$. Le pire cas et le cas moyen sont dans la même classe: diviser le travail moyen par deux ne change pas la nature du problème.

Ces trois nombres disent aussi que le cas moyen ne sauve pas la recherche séquentielle. Sur un million d'éléments, elle fait $10^6$ comparaisons dans le pire cas, soit cinquante mille fois plus que les 20 comparaisons qui suffiraient à une recherche dichotomique — à condition que le tableau soit trié, ce que la recherche séquentielle n'exige pas. C'est l'objet du chapitre 3, avec la récursivité et le principe «diviser pour régner»: la dichotomie, le tri fusion, et le théorème qui donne d'un coup le coût de tous les algorithmes de cette forme. Retenez pour l'instant l'ordre de grandeur: $\Theta (n)$ contre $\Theta (\log n)$, un million contre vingt.

La machine qui exécute: architecture et mémoire

Jusqu'ici, un algorithme s'exécutait sur une machine abstraite, la machine RAM, où chaque opération élémentaire coûte une unité. Il est temps de regarder la machine réelle qui se cache derrière ce modèle, pour deux raisons. D'abord, elle explique pourquoi le modèle RAM est raisonnable: un ordinateur exécute réellement une suite d'instructions simples, une par une, chacune en un temps borné. Ensuite, elle explique où le modèle se trompe, et de combien: tous les accès à la mémoire ne coûtent pas la même chose, et l'écart se chiffre en ordres de grandeur.

Le programme enregistré

En 1945, un rapport rédigé par John von Neumann pour l'EDVAC, l'un des premiers calculateurs électroniques américains, décrit une organisation dont presque tous les ordinateurs actuels descendent. Son idée centrale tient en une phrase: le programme est rangé dans la mémoire, au même titre que les données. Les machines antérieures se programmaient en recâblant des panneaux; changer de calcul prenait des jours. Avec le programme enregistré, changer de calcul revient à écrire d'autres nombres en mémoire. C'est, réalisée en électronique, la leçon de la machine universelle du chapitre 5: un programme est une donnée.

Les registres sont de petites mémoires internes au processeur, quelques mots seulement, mais accessibles sans passer par le bus: c'est là que le calcul se fait réellement. La mémoire centrale est grande et lente; les registres sont minuscules et rapides. Cette tension entre taille et vitesse est le sujet des deux sous-sections suivantes.

Une machine jouet et son jeu d'instructions

Pour voir la machine travailler, fixons une machine minuscule, dont les mots ont 8 bits. Une instruction occupe un mot: ses 3 bits de tête forment le code d'opération, ses 5 bits de queue une adresse. Cinq bits désignent $2^5=32$ cases: la mémoire compte donc 32 octets. Le jeu d'instructions est le suivant.

Ici M[a] désigne le contenu de la case d'adresse a. L'instruction ADD 20 s'écrit donc 010 suivi de $20=(10100{)}_2$, soit le mot $(01010100{)}_2$, c'est-à-dire l'entier 84. Si la case 1 contient 84, rien dans ses bits ne dit s'il s'agit de l'instruction «ajouter le contenu de la case 20» ou du nombre 84: tout dépend de ce que le processeur fait de la case. Il l'exécute si le compteur ordinal y pointe; il l'additionne si une instruction ADD 1 la désigne. Cette indistinction est la force du programme enregistré — et, on le verra au chapitre 9, l'origine de toute une famille d'attaques.

Le cycle chercher–décoder–exécuter

Le compteur ordinal est incrémenté pendant la recherche, avant l'exécution: c'est pourquoi un saut n'a qu'à écrire une nouvelle valeur dans PC pour que le cycle suivant aille chercher ailleurs. Une boucle n'est rien d'autre qu'un saut vers une adresse déjà visitée.

La hiérarchie mémoire

On ne sait pas fabriquer une mémoire à la fois grande, rapide et bon marché. Les technologies rapides (les bascules des registres et de la mémoire statique) coûtent cher par bit et occupent de la place; les technologies denses (la mémoire dynamique, la mémoire flash, le disque magnétique) sont lentes. La solution est d'empiler plusieurs niveaux, du plus petit et plus rapide au plus grand et plus lent. Les valeurs ci-dessous sont des ordres de grandeur typiques d'un ordinateur personnel récent, pas des mesures: elles varient d'un modèle à l'autre, et c'est leur rapport qui compte.

D'une ligne à l'autre, la capacité est multipliée et le temps d'accès aussi. Entre le cache L1 et la mémoire centrale, il y a environ deux ordres de grandeur; entre la mémoire centrale et un disque magnétique, environ cinq. Le processeur ne parle qu'au premier niveau; chaque niveau garde une copie d'une partie du niveau suivant, en espérant que ce soit la partie dont on aura besoin. Que cet espoir soit le plus souvent fondé tient à une propriété des programmes.

Un cache exploite les deux. Lorsque le processeur demande une case absente du cache, celui-ci ne copie pas seulement cette case mais tout le bloc (cache line) qui la contient, typiquement 64 octets: c'est le pari de la localité spatiale. Et il garde les blocs récemment utilisés, en évinçant les plus anciens quand la place manque: c'est le pari de la localité temporelle. Une demande servie par le cache est un succès (hit); une demande qui doit descendre au niveau suivant est un échec (miss).

La mémoire virtuelle

Le dernier étage de la hiérarchie relie la mémoire centrale au disque, et il le fait par un mécanisme qui sert au moins autant la sécurité que la vitesse.

La traduction est une simple découpe de bits. Avec des adresses de 32 bits et des pages de $4$ Kio $=2^{12}$ octets, les 12 bits de poids faible d'une adresse donnent la position dans la page (le déplacement) et les 20 bits de poids fort le numéro de page: l'espace virtuel compte $2^{20}=1048576$ pages. L'adresse virtuelle $(00403\mathrm{A}7\mathrm{C}{)}_{16}$ se lit donc page , déplacement — trois chiffres hexadécimaux font exactement les douze bits du déplacement, ce qui est la raison pour laquelle on écrit ces adresses en hexadécimal. Si la table des pages associe la page au cadre , l'adresse physique est : le numéro de page est remplacé, le déplacement recopié.

La mémoire virtuelle apporte trois choses.

• L'isolation. Un programme ne peut désigner que les adresses de son propre espace virtuel; les cadres d'un autre programme n'apparaissent dans aucune de ses tables, il ne peut donc ni les lire ni les écrire. La table peut aussi marquer une page en lecture seule, ou interdire d'exécuter son contenu. C'est le premier mécanisme de contrôle d'accès d'un ordinateur, et le chapitre 9 y reviendra.
• L'illusion d'une mémoire plus grande que la mémoire physique: les pages peu utilisées attendent sur disque.
• Le partage contrôlé: deux programmes peuvent voir le même cadre, par exemple le code d'une bibliothèque commune, sans le dupliquer.

L'illusion se paie cher quand elle échoue. Un défaut de page servi par un disque SSD coûte de l'ordre de $100$ µs, soit mille fois un accès à la mémoire centrale de 100 ns. Pour que le temps moyen ne dépasse pas 110 ns — 10 % de ralentissement —, il faut, par la même formule (2.7) avec $t_c=100$ ns et $p=10^5$ ns, que $m\cdot 10^5\le 10$, soit . Avec un disque magnétique à 10 ms, la limite tombe à un défaut par million d'accès. Un programme dont les données ne tiennent pas en mémoire centrale et qui les parcourt sans localité ne ralentit donc pas de quelques pour cent: il s'effondre. La localité, encore elle, décide de tout.

Ce que la vue asymptotique ne voit pas

L'analyse asymptotique est un outil de tri des idées, pas un oracle. Trois de ses angles morts méritent d'être connus, et le troisième se calcule.

Les constantes existent

$O$, $\Omega$ et $\Theta$ ignorent délibérément les facteurs constants. Or, à classe égale, un algorithme peut être dix ou cent fois plus lent qu'un autre. Le tri fusion du chapitre 3 est en $\Theta (n\log n)$, mais il alloue un tableau auxiliaire et recopie des données; certaines de ses variantes en place, de même classe, sont deux fois plus lentes en pratique. Entre deux algorithmes de même classe, la notation asymptotique ne tranche pas: il faut mesurer, sur des données représentatives et sur la machine visée.

Ce n'est pas un défaut de la théorie, c'est sa définition. Elle répond à «comment le coût évolue-t-il quand les données grandissent?», pas à «lequel des deux dois-je écrire aujourd'hui?».

La hiérarchie mémoire

Le modèle RAM suppose qu'accéder à A[1] et à A[1000000] coûte la même chose. La section précédente a montré que c'est faux, et de combien: entre un accès servi par le cache de premier niveau et un accès qui descend en mémoire centrale, il y a environ deux ordres de grandeur, et l'exemple 2.6 a chiffré à un facteur 7,5 l'écart entre deux parcours d'une même matrice qui font exactement les mêmes opérations. Deux algorithmes en $\Theta (n)$ dont l'un parcourt la mémoire dans l'ordre et l'autre par sauts imprévisibles ne se comportent pas de la même façon, et l'écart se voit au chronomètre alors qu'il est invisible dans le comptage d'opérations.

Cette différence est, elle aussi, un facteur constant — le modèle n'est donc pas «faux», il est aveugle à quelque chose d'important. Retenez qu'entre deux algorithmes de même classe, celui qui respecte la localité des accès gagne en général, et qu'un algorithme dont les données débordent de la mémoire centrale change de régime, parce que la pénalité d'un défaut de page se compte en dizaines de microsecondes.

Un algorithme en n log n peut perdre contre un algorithme quadratique

C'est l'angle mort le plus instructif, parce qu'il se quantifie. La définition de $O$ contient «à partir d'un certain rang $n_0$»; rien n'interdit à $n_0$ d'être grand.

C'est exactement ce que font les bibliothèques de tri réelles: un tri récursif rapide sur les grandes tailles, et un basculement vers le tri par insertion en dessous d'un seuil de quelques dizaines d'éléments, déterminé par mesure sur la machine visée. L'algorithme «théoriquement mauvais» n'a pas disparu; il a trouvé sa place.

Synthèse

• Un algorithme est une suite finie d'instructions non ambiguës qui termine et produit la sortie spécifiée. La terminaison et la correction ne sont pas des évidences: elles se démontrent. Une recette est ambiguë, une heuristique n'est pas garantie correcte, un programme est la réalisation d'un algorithme dans un langage.
• La correction d'une boucle se prouve par un invariant (vrai à l'entrée, conservé par un tour, et qui donne le résultat quand la condition de sortie devient fausse); la terminaison, par un variant, une quantité qui décroît strictement dans un ensemble bien fondé — typiquement un entier positif. L'algorithme d'Euclide se prouve ainsi: invariant $\gcd (a,b)=\gcd (a_0,b_0)$, variant $b$.
• On compte des opérations élémentaires, pas des secondes: le comptage est indépendant de la machine, prédictif et durable. On distingue le meilleur cas, le pire cas — la garantie — et le cas moyen, qui n'a de sens qu'avec la loi de probabilité qui le définit.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Puissance(x, n)
  r ← 1 ; b ← x ; e ← n
  tant que e > 0 faire
    si e est impair alors r ← r × b fin si
    b ← b × b
    e ← e div 2                      // division entière
  fin tant que
  retourner r

Références

• Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, 4^e éd., MIT Press, Cambridge, chap. 1–3 (algorithmes, invariants de boucle, notations asymptotiques) et chap. 2.1–2.2 (tri par insertion).
• Knuth, D. E., The Art of Computer Programming, vol. 1 (Fundamental Algorithms), 3^e éd., Addison-Wesley, section 1.1 (définition d'un algorithme) et section 1.2.1 (démonstrations par récurrence appliquées aux programmes).
• Knuth, D. E., The Art of Computer Programming, vol. 3 (Sorting and Searching), 2^e éd., Addison-Wesley, section 5.2.1 (tri par insertion) et 5.2.3 (tri par sélection).
• Sipser, M., Introduction to the Theory of Computation, 3^e éd., Cengage, chap. 7.1 (mesure de complexité, notations asymptotiques).
• Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, chap. 1 (ce que les algorithmes rendent possible, et à quel prix).
• Patterson, D. A. et Hennessy, J. L., Computer Organization and Design, Morgan Kaufmann — chapitre 2 pour le jeu d'instructions et le cycle d'exécution, chapitre 5 pour les caches, la localité et la mémoire virtuelle.
• von Neumann, J., First Draft of a Report on the EDVAC, Moore School of Electrical Engineering, Université de Pennsylvanie, 1945 — le programme enregistré.
• Polycopiés du cours ICC de l'EPFL, partie «Algorithmique et complexité».