Algorithmes, programmes et complexité

Cours complet · informatique (MP2I/MPI), chapitre 3 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

3.1 Deux mots qu'on confond, et qu'il faut séparer

Un algorithme est une méthode : une suite finie d'opérations qui, à partir de données d'entrée, produit un résultat. Un programme en est une mise en œuvre dans un langage donné. La dichotomie est un algorithme ; les quinze lignes de C du chapitre chap:diviser en sont un programme, et les huit lignes d'OCaml en sont un autre — le même algorithme, deux programmes.

La distinction n'est pas scolaire. Elle décide de ce qu'on peut affirmer. « Cet algorithme fait $O (lo g n)$ comparaisons » est une propriété de la méthode, vraie dans tous les langages. « Ce programme s'exécute en 3 ms » est une propriété d'un programme sur une machine un jour donné. Les deux se mesurent, mais pas de la même façon, et l'un ne remplace jamais l'autre.

3.2 Paradigmes

Définition 3.1Trois manières de dire ce qu'on veut

Impératif structuré : on décrit une suite d'actions qui modifient un état. Les boucles et l'affectation en sont les outils. C en est l'exemple du programme.
Déclaratif fonctionnel : on décrit le résultat comme une expression, composée de fonctions, sans état modifié. OCaml en est l'exemple.
Logique : on décrit les relations que le résultat doit satisfaire, et un moteur cherche ce qui les satisfait. Le programme ne le rencontre qu'une fois : à l'occasion des bases de données (chapitre chap:sql), où l'on écrit quelles lignes on veut, jamais comment les trouver.

iRemarqueCe que le programme écarte

« On ne présente pas de théorie générale sur les paradigmes de programmation, on se contente d'observer les paradigmes employés sur des exemples. » Et le saut inconditionnel — l'instruction GOTO — est explicitement hors programme : c'est une instruction qui permet d'aller n'importe où dans le code, et dont l'abandon est précisément ce qui a rendu la programmation structurée raisonnable.

Exemple 3.2La même somme, trois paradigmes


/* Impératif : un état (s) que l'on modifie tour après tour. */
int s = 0;
for (int i = 0; i < n; i = i + 1) { s = s + t[i]; }


(* Fonctionnel : une expression, aucun état. *)
let rec somme = function [] -> 0 | x :: r -> x + somme r


-- Déclaratif : on dit CE QU'ON VEUT, pas comment l'obtenir.
SELECT SUM(valeur) FROM mesures;

3.3 Compilé, interprété

Définition 3.3Deux façons d'exécuter un texte

Un langage compilé est traduit en entier, avant exécution, en un fichier que la machine sait exécuter. Un langage interprété est lu et exécuté au fil de la lecture par un autre programme, l'interpréteur.

	Compilé (C, OCaml)	Interprété (Python)
Erreurs de type	détectées avant l'exécution	découvertes pendant
Vitesse	le code machine est direct	une couche s'interpose
Cycle de travail	compiler, puis lancer	lancer

Le programme demande de connaître le passage « d'un fichier texte source en un fichier objet puis en un fichier exécutable », et la « différence entre fichiers d'interface et fichiers d'implémentation » — vue au chapitre chap:langage-c.

iRemarqueOCaml sait faire les deux

ocamlopt produit du code machine, ocamlc un bytecode interprété, et la boucle interactive ocaml se comporte comme un interpréteur. « Compilé » et « interprété » qualifient donc une mise en œuvre, pas un langage.

3.4 Les flottants, ou pourquoi $0, 1 + 0, 2 \neq = 0, 3$

Définition 3.4Ce qu'est un flottant

Un double occupe 64 bits, répartis en un signe, un exposant et une mantisse. Il représente donc un nombre de la forme $\pm m \times 2^{e}$ , où $m$ ne compte qu'un nombre fini de bits. Les réels représentables sont en nombre fini ; tout le reste est arrondi au plus proche.

AttentionLa divergence entre le calcul théorique et le calcul effectué


0.1 +. 0.2 = 0.3        (* false *)
0.1 +. 0.2              (* 0.30000000000000004 *)

Ni $0, 1$ ni $0, 2$ ne s'écrivent exactement en base 2 — pas plus que $1/3$ ne s'écrit exactement en base 10. Chacun est arrondi, et les deux erreurs se cumulent.

Le programme demande d'« illustrer l'impact de la représentation par des exemples de divergence entre le calcul théorique d'un algorithme et les valeurs calculées par un programme ». En voici un second, plus inquiétant :


double x = 0.0;
for (int i = 0; i < 10; i = i + 1) { x = x + 0.1; }
/* x n'est PAS égal à 1.0 : c'est 0.9999999999999999 */

Un algorithme dont la condition d'arrêt serait x == 1.0 ne s'arrêterait jamais. La boucle théorique termine ; le programme, non.

Bonne pratique (Comparer deux flottants à une précision près)

« Les comparaisons entre flottants prennent en compte la précision », dit le programme. On ne teste jamais l'égalité :


#include <math.h>
const double EPS = 1e-9;
if (fabs(a - b) < EPS) { /* a et b sont « égaux » à EPS près */ }

Et l'on compte les tours de boucle sur un entier, jamais sur un flottant qu'on incrémente.

3.5 Terminaison et correction

C'est le cœur du chapitre. Un programme peut échouer de deux façons indépendantes : ne pas s'arrêter, ou s'arrêter sur un résultat faux. On les traite séparément.

Définition 3.5Les trois propriétés

Soit $A$ un algorithme, muni d'une précondition $P$ sur ses entrées et d'une postcondition $Q$ sur sa sortie.

$A$ termine si, pour toute entrée vérifiant $P$ , l'exécution s'arrête.
$A$ est partiellement correct si, pour toute entrée vérifiant $P$ , lorsque l'exécution s'arrête, la sortie vérifie $Q$ .
$A$ est totalement correct s'il est partiellement correct et qu'il termine.

La formule du programme est exactement celle-ci : « la correction est partielle quand le résultat est correct lorsque l'algorithme s'arrête, la correction est totale si elle est partielle et si l'algorithme termine ».

ImportantCorrection partielle et terminaison sont indépendantes

La boucle while (true) { } est partiellement correcte pour n'importe quelle postcondition : elle ne s'arrête jamais, donc l'implication « si elle s'arrête, alors $Q$ » est vraie par vacuité. C'est absurde et c'est instructif : la correction partielle seule ne garantit rien. Il faut les deux preuves.

3.5.1 Le variant : prouver qu'on s'arrête

Définition 3.6Variant de boucle

Un variant d'une boucle est une quantité entière $V$ telle que, à chaque tour :

$V$ décroît strictement ;
$V$ reste minorée (par $0$ , typiquement).

Une suite d'entiers strictement décroissante et minorée est finie : la boucle s'arrête donc, après au plus $V_{initial} - V_{min}$ tours.

Exemple 3.7Recherche dichotomique : le variant est la largeur


/* Renvoie un indice i tel que t[i] == v, ou -1. Précondition : t trié
   croissant sur ses n premiers termes, n >= 0. */
int cherche(const int t[], int n, int v) {
    int g = 0, d = n - 1;
    while (g <= d) {
        int m = g + (d - g) / 2;      /* et non (g + d) / 2 : voir plus bas */
        if (t[m] == v) { return m; }
        if (t[m] < v) { g = m + 1; } else { d = m - 1; }
    }
    return -1;
}

Variant : $V = d - g + 1$ , le nombre de cases encore candidates.

$V \geq 0$ tant que la condition $g \leq d$ est vraie ;
à chaque tour, soit on retourne, soit $g$ augmente strictement, soit $d$ diminue strictement — donc $V$ décroît d'au moins $1$ .

La boucle termine. Et comme $V$ est en fait divisé par deux à chaque tour, elle termine en $O (lo g n)$ tours, ce qui est une information plus fine que la seule terminaison.

Attention`(g + d) / 2` déborde, `g + (d - g) / 2` non

Sur de grands tableaux, $g + d$ peut dépasser la capacité d'un int alors que $g$ et $d$ y tiennent tous deux. Le résultat devient négatif, et l'accès t[m] sort du tableau. Ce bogue a vécu neuf ans dans la bibliothèque standard de Java. C'est le dépassement de capacité du chapitre chap:langage-c, rencontré là où personne ne le cherchait.

3.5.2 L'invariant : prouver qu'on a juste

Définition 3.8Invariant de boucle

Un invariant est une propriété $I$ qui est vraie :

avant le premier tour (initialisation) ;
après chaque tour, si elle l'était avant (conservation).

Par récurrence, $I$ est alors vraie à la sortie de la boucle. Jointe à la négation de la condition de boucle, elle donne la postcondition — c'est l'utilisation, et c'est la troisième étape qu'on oublie.

Méthode : Prouver une boucle en trois temps

Trouver l'invariant : c'est presque toujours « ce que j'ai fait jusqu'ici est correct sur la partie déjà traitée ».
Établir initialisation et conservation.
Utiliser : à la sortie, l'invariant et la négation de la condition donnent la postcondition.

Exemple 3.9Le maximum d'un tableau, prouvé


/* Renvoie le plus grand des n premiers termes de t. Précondition : n >= 1. */
int maximum(const int t[], int n) {
    assert(n >= 1);
    int m = t[0];
    int i = 1;
    /* INVARIANT : m est le maximum de t[0..i-1], et 1 <= i <= n. */
    while (i < n) {
        if (t[i] > m) { m = t[i]; }
        i = i + 1;
    }
    return m;
}

Démonstration

Initialisation. Avant le premier tour, $i = 1$ et $m = t [0]$ : $m$ est bien le maximum de $t [0..0]$ , qui n'a qu'un élément. L'encadrement $1 \leq i \leq n$ tient car $n \geq 1$ .

Conservation. Supposons l'invariant vrai en début de tour : $m = max t [0.. i - 1]$ et $i < n$ . Le corps pose $m^{'} = max (m, t [i]) = max (max t [0.. i - 1], t [i]) = max t [0.. i]$ , puis $i^{'} = i + 1$ . Donc $m^{'} = max t [0.. i^{'} - 1]$ : l'invariant est rétabli. Et $i^{'} \leq n$ car $i < n$ .

Utilisation. À la sortie, la condition est fausse : $i \geq n$ . Joint à $i \leq n$ , cela donne $i = n$ . L'invariant s'écrit alors $m = max t [0.. n - 1]$ , qui est la postcondition.
Terminaison. $V = n - i$ décroît strictement de $1$ à chaque tour et reste positif.

Bonne pratique (L'invariant s'écrit en commentaire, à sa place)

Le programme demande l'« annotation d'un bloc d'instructions par une précondition, une postcondition, une propriété invariante », et précise : « ces annotations se font à l'aide de commentaires ». L'invariant se place juste avant la boucle, la précondition en tête de fonction. Un lecteur doit pouvoir vérifier votre preuve sans la reconstruire.

3.6 Complexité

3.6.1 Compter, et quoi compter

Définition 3.10Complexité en temps

On choisit une opération élémentaire représentative — comparaison, affectation, accès mémoire, opération arithmétique — et l'on compte combien de fois elle est exécutée, en fonction de la taille de l'entrée. Le résultat est donné en ordre de grandeur, avec la notation $O$ .

iRemarquePourquoi un ordre de grandeur, et pas un temps

Parce qu'un temps dépend de la machine, du compilateur, de ce que fait le voisin. L'ordre de grandeur, lui, ne dépend que de l'algorithme : un $O (n^{2})$ battra un $O (n lo g n)$ sur les petites entrées et perdra toujours sur les grandes, quelle que soit la machine. C'est une propriété de la méthode, et c'est la seule qui se transmette.

Ordre	Nom	Exemple du programme
$O (1)$	constant	accès à une case de tableau, empiler
$O (lo g n)$	logarithmique	recherche dichotomique
$O (n)$	linéaire	parcours, maximum, `List.length`
$O (n lo g n)$	quasi-linéaire	tri par partition-fusion, tri par tas
$O (n^{2})$	quadratique	tri par sélection, deux boucles imbriquées
$O (2^{n})$	exponentiel	exploration exhaustive des sous-ensembles

3.6.2 Pire cas, cas moyen

Définition 3.11Deux mesures

Pour une taille $n$ donnée, plusieurs entrées sont possibles, et le coût varie.

La complexité dans le pire cas est le maximum du coût sur toutes les entrées de taille $n$ . C'est une garantie : jamais pire.
La complexité dans le cas moyen est l'espérance du coût, pour une loi de probabilité donnée sur les entrées. Elle décrit le comportement usuel, mais ne garantit rien.

Le programme limite « l'étude de la complexité dans le cas moyen et du coût amorti à quelques exemples simples ».

Exemple 3.12Recherche séquentielle

Chercher $v$ dans un tableau de $n$ cases non trié, en s'arrêtant dès qu'on l'a trouvé.

Meilleur cas : $v$ est en première case, $1$ comparaison.
Pire cas : $v$ est en dernière case, ou absent : $n$ comparaisons, donc $O (n)$ .
Cas moyen : si $v$ est présent et que sa position est uniforme sur ${1, \dots, n}$ , le nombre moyen de comparaisons vaut

$\frac{1}{n} k = 1 \sum n k = \frac{n + 1}{2},$

soit $O (n)$ également : deux fois moins de comparaisons que le pire cas, donc environ deux fois plus rapide — mais du même ordre de grandeur.

3.6.3 Coût amorti

Définition 3.13Amortir une opération coûteuse mais rare

Le coût amorti d'une opération est le coût total d'une suite de $k$ opérations, divisé par $k$ . Il rend compte des cas où une opération est presque toujours bon marché et rarement très chère.

Exemple 3.14Le tableau qui double

Un tableau dynamique de capacité $c$ contenant $n$ éléments. Ajouter en fin coûte $O (1)$ … sauf quand le tableau est plein : il faut alors en allouer un de capacité $2 c$ et recopier les $n$ éléments, soit $O (n)$ .

Le pire cas d'un ajout est donc $O (n)$ . Mais sur $n$ ajouts successifs partant d'une capacité $1$ , les recopies ont lieu aux tailles $1, 2, 4, \dots, 2^{⌊ l o g_{2} n ⌋}$ , pour un coût total

$1 + 2 + 4 + \dots + 2^{⌊ l o g_{2} n ⌋} < 2 n .$

Le coût total des $n$ ajouts est donc $O (n)$ , et le coût amorti d'un ajout est $O (1)$ .

ImportantTrois mots à ne pas confondre

Pire cas	le maximum sur une opération. Garantie absolue.
Cas moyen	l'espérance sur une opération, sous une loi. Aucune garantie.
Amorti	la moyenne sur une suite d'opérations. Garantie sur le total, sans probabilités.

L'amorti n'est pas une moyenne probabiliste : il ne suppose rien sur les entrées. C'est la confusion la plus fréquente.

3.6.4 Complexité en espace

Définition 3.15Compter la mémoire

La complexité en espace compte la mémoire supplémentaire utilisée, hors entrée. Un tri en place est $O (1)$ en espace ; le tri par partition-fusion est $O (n)$ ; une fonction récursive de profondeur $p$ consomme $O (p)$ d'espace de pile, même si elle n'alloue rien — point sur lequel le chapitre chap:recursivite revient.

3.7 Ce qu'il faut retenir

ImportantLa grille de lecture de tout le livre

Chaque algorithme rencontré dans ce livre sera présenté avec quatre choses, et le programme officiel les exige toutes les quatre : « les algorithmes sont présentés au tableau en spécifiant systématiquement les entrées et sorties et en étudiant, dans la mesure du possible, leur correction et leur complexité ».

sa spécification — précondition, postcondition ;
sa terminaison — un variant ;
sa correction — un invariant, et son utilisation à la sortie ;
sa complexité — en temps et en espace, dans le pire cas au minimum.

Continuer sur Adloun : animation, QCM, fiches, exercices