Méthodes de programmation

Résumé en cinq points

Algorithmes et programmes

Algorithme, programme, paradigmes

Un algorithme est une suite finie d'opérations non ambiguës qui transforme une entrée en sortie, décrite indépendamment de toute machine. Un programme est sa mise en œuvre dans un langage précis. L'algorithme d'Euclide peut être programmé en C, en OCaml ou en Python, dans plusieurs styles.

On ne fait pas de théorie des paradigmes, on les observe sur des exemples.

• Impératif structuré : une suite d'instructions qui modifient un état (variables, cases de tableau), organisée par conditionnelles, boucles et fonctions. C'est le style du C et du Python du lycée. Le saut inconditionnel (GOTO) est hors programme.
• Déclaratif fonctionnel : le programme est une expression à évaluer, les fonctions sont des valeurs comme les autres, on privilégie la récursivité et les données non modifiables. C'est le style naturel d'OCaml, qui permet aussi l'impératif (références, tableaux, boucles).
• Logique : on décrit des faits et des règles, le système cherche les réponses. Il n'est évoqué qu'avec les bases de données.

Langage compilé ou interprété

Un compilateur traduit une fois pour toutes le fichier source en code exécutable. Un interpréteur exécute le programme au fur et à mesure de sa lecture. En toute rigueur, c'est une mise en œuvre du langage qui est compilée ou interprétée. Python est usuellement interprété.

En C, la compilation transforme chaque fichier source fichier.c en fichier objet fichier.o, du code machine incomplet qui peut appeler des fonctions définies ailleurs. L'édition de liens assemble ensuite les fichiers objets en un exécutable. Le fichier d'interface (en-tête fichier.h, inclus par #include "fichier.h") déclare les types et les signatures offerts. Le fichier d'implémentation (fichier.c) contient les définitions. En OCaml, l'interface est un .mli et l'implémentation un .ml. On compile avec ocamlc (code intermédiaire pour une machine virtuelle) ou ocamlopt (code natif), ou on utilise la boucle interactive. L'interface permet d'utiliser un module sans dépendre des détails de son implémentation.

Représentation des flottants

Le type double en C et float en OCaml sont des flottants sur 64 bits, norme IEEE 754 : signe × mantisse × 2 puissance exposant, avec 1 bit de signe, 11 bits d'exposant et 52 bits de mantisse stockés. Pour un nombre normalisé, le premier bit de la mantisse vaut 1 et n'est pas stocké, d'où 53 bits de précision, environ 15 à 16 chiffres décimaux.

Ordres de grandeur : l'epsilon machine, écart entre 1 et le flottant suivant, vaut 2^-52 ≈ 2,2 × 10^-16. Le plus grand flottant fini vaut environ 1,8 × 10³⁰⁸. Les entiers de valeur absolue au plus 2⁵³ sont tous représentables exactement.

Conséquences :

• Erreur de représentation : 0,1 a un développement binaire infini (0,000110011…), il est arrondi. En OCaml, 0.1 +. 0.2 s'affiche 0.30000000000000004 et 0.1 +. 0.2 = 0.3 vaut false.
• Absorption : 10¹⁶ + 1 donne 10¹⁶, car près de 10¹⁶ deux flottants consécutifs sont espacés de 2.
• Perte d'associativité : (10¹⁶ + 1) + 1 donne 10¹⁶ alors que 10¹⁶ + (1 + 1) donne 10¹⁶ + 2.
• Cancellation : (1 + 10^-15) − 1 donne environ 1,11 × 10^-15, soit 11 % d'erreur relative.

Divergence entre théorie et calcul : la suite u₀ = 0,1, u_n+1 = 10 u_n − 0,9 est constante en théorie. En flottants, u₁ vaut 0,09999999999999998 et l'erreur est multipliée par 10 à chaque pas : u₁₇ ≈ −0,15, u₂₀ ≈ −247.

Règle : on ne compare jamais deux flottants par l'égalité. On teste |x − y| ≤ ε avec une tolérance ε adaptée, ou un écart relatif |x − y| ≤ ε × max(|x|, |y|). Les entiers machine ont aussi leurs limites : ils sont sujets au dépassement de capacité (en C, un dépassement sur un entier signé est un comportement indéfini).

Terminaison et correction

Définitions

On fixe une spécification : des préconditions sur l'entrée et une postcondition reliant entrée et sortie.

• Terminaison : pour toute entrée vérifiant les préconditions, l'exécution s'arrête.
• Correction partielle : pour toute telle entrée, si l'exécution s'arrête, le résultat vérifie la postcondition.
• Correction totale : correction partielle et terminaison.

Un programme qui ne s'arrête jamais est partiellement correct pour toute spécification. La correction partielle seule ne suffit donc pas. Pour la culture : on ne sait pas prouver que la boucle de Syracuse (n devient n/2 s'il est pair, 3n + 1 sinon, jusqu'à 1) termine pour tout n ≥ 1.

Variant et terminaison

Un variant de boucle est une quantité entière, positive ou nulle à chaque passage, qui décroît strictement à chaque itération. Comme il n'existe pas de suite infinie strictement décroissante d'entiers naturels, la boucle termine. Pour une fonction récursive, on utilise une quantité entière positive qui décroît strictement à chaque appel.

(* pgcd : int -> int -> int
   Précondition : a >= 0 et b >= 0.
   Postcondition : renvoie le pgcd de a et b. *)
let rec pgcd a b = if b = 0 then a else pgcd b (a mod b)

Le variant est b, car pour b > 0 on a 0 ≤ a mod b < b.

Pièges : une quantité réelle ne convient pas (1/n décroît strictement en restant positive, indéfiniment). Et une boucle qui part de x = 0.0, ajoute 0.1 et s'arrête quand x = 1.0 ne termine pas : après dix ajouts, x vaut 0.9999999999999999.

Invariant et correction

Un invariant de boucle est une propriété vraie avant la première itération et conservée par chaque itération. Elle est donc vraie à la sortie (récurrence sur le nombre de tours). Jointe à la condition de sortie, elle donne la postcondition.

Exemple : exponentiation rapide en C.

/* Entrée : n >= 0. Sortie : a puissance n (hors dépassement). */
int puissance(int a, int n) {
    assert(n >= 0);
    int r = 1, x = a, k = n;
    /* invariant : r * x^k = a^n et k >= 0 */
    while (k > 0) {
        if (k % 2 == 1) r = r * x;
        x = x * x;
        k = k / 2;
    }
    return r;
}

• Initialisation : 1 × aⁿ = aⁿ.
• Conservation : si k est impair, les nouvelles valeurs sont r x, x² et (k − 1)/2, et r x × (x²)^(k−1)/2 = r x^k. Si k est pair, (x²)^k/2 = x^k.
• Sortie : k = 0, donc r = aⁿ.
• Terminaison : k est un variant, car pour k > 0, 0 ≤ k/2 < k (division entière).

Pour a = 3 et n = 5, (r, x, k) vaut (1, 3, 5), (3, 9, 2), (3, 81, 1), (243, 6561, 0). Cette preuve vaut pour les entiers mathématiques. En machine, il faut aussi qu'aucun calcul ne déborde, et le dernier calcul de x² peut déborder même si le résultat tient dans un int.

Complexité

Pire cas

On compte les opérations élémentaires en fonction de la taille n de l'entrée. La complexité dans le pire cas est le maximum de ce nombre sur les entrées de taille n, exprimé par un ordre de grandeur : O(f(n)) signifie « au plus une constante fois f(n) pour n assez grand ».

La recherche séquentielle dans un tableau de taille n fait au plus n comparaisons : O(n). L'exponentiation rapide fait autant de tours que n a de chiffres binaires, ⌊log₂ n⌋ + 1 pour n ≥ 1 : O(log n), contre n multiplications pour la méthode naïve.

Cas moyen

La complexité en moyenne est l'espérance du coût quand l'entrée suit une loi de probabilité fixée, qu'il faut toujours énoncer. Exemple : recherche d'un élément présent dans un tableau de n éléments distincts, à une position uniforme. En position i, on fait i comparaisons. La moyenne vaut (1 + 2 + … + n)/n = (n + 1)/2, encore O(n).

Coût amorti

Le coût amorti d'une opération est le coût total d'une suite de m opérations divisé par m, dans le pire cas sur les suites. Exemple : tableau dynamique de capacité initiale 1. Ajouter un élément coûte 1 s'il reste de la place. Sinon, on alloue une capacité double et on recopie les c éléments, pour un coût c + 1. Pour n ajouts, les recopies coûtent au plus 1 + 2 + 4 + … + 2^p avec 2^p < n, soit moins de 2n, et le total est inférieur à 3n. Le coût amorti d'un ajout est O(1), alors qu'un ajout isolé peut coûter O(n).

Discipline de programmation

Spécification et annotations

Chaque fonction a sa spécification : sa signature (toujours précisée), les données attendues (préconditions) et ce qu'elle renvoie ou modifie (postcondition). Un bloc d'instructions s'annote en commentaire par une précondition, une postcondition ou un invariant. Les commentaires expliquent les choix plutôt que de paraphraser : « k est divisé par 2 » n'apporte rien, « on traite le bit de poids faible de k » éclaire.

(* maximum : int list -> int
   Précondition : l est non vide.
   Postcondition : renvoie le plus grand élément de l. *)
let rec maximum l = match l with
  | [] -> failwith "maximum : liste vide"
  | [x] -> x
  | x :: q -> max x (maximum q)

Programmation défensive et assertions

Des données invalides peuvent venir de causes internes (un bogue ailleurs dans le programme) ou externes (saisie, fichier mal formé). Programmer défensivement, c'est vérifier ce qui peut l'être. Une assertion affirme qu'une condition est vraie à un point du programme. Si elle est fausse à l'exécution, en C assert(c) arrête le programme en indiquant le fichier et la ligne, en OCaml assert c lève l'exception Assert_failure. Usages : valider une précondition (n ≥ 0 dans puissance), vérifier un indice avant un accès à un tableau, contrôler un risque de dépassement, vérifier qu'un pointeur n'est pas NULL.

Les garanties dépendent du langage. C a un typage faible : il convertit implicitement un double en int en tronquant et ne vérifie pas les accès t[i] (un accès hors bornes est un comportement indéfini). OCaml a un typage fort : 1 + 2.0 est refusé à la compilation (il faut float_of_int et +.) et un accès t.(i) hors bornes lève Invalid_argument.

Les exceptions ne servent pas qu'aux erreurs. Elles signalent aussi un résultat particulier mais prévu.

(* indice : 'a array -> 'a -> int
   Renvoie un indice de x dans t, lève Not_found si x est absent. *)
let indice t x =
  let rec cherche i =
    if i = Array.length t then raise Not_found
    else if t.(i) = x then i
    else cherche (i + 1)
  in cherche 0

L'appelant écrit try indice t x with Not_found -> -1 : l'absence est un cas normal.

Validation et test

Jeu de tests

Un jeu de tests est une liste d'entrées avec les sorties attendues, écrite à la main. Tester révèle des erreurs sans prouver la correction. On partitionne le domaine d'entrée en classes de comportement identique, avec un représentant par classe, et on teste les limites : 0, 1, liste vide, tableau à un élément, élément en première ou dernière position.

Exemple : une année est bissextile si elle est multiple de 4 sans l'être de 100, ou si elle est multiple de 400. Quatre classes, quatre tests : 2023 donne faux, 2024 vrai, 1900 faux, 2000 vrai.

Graphe de flot de contrôle

Ses sommets sont les instructions (ou blocs) et les tests, ses arcs les passages possibles de l'un à l'autre. Un test a un arc « vrai » et un arc « faux ». Un chemin est faisable si une entrée le parcourt.

int f(int x) {
    int y = 0;
    if (x > 0) y = 1;
    if (x < 0) y = 2;
    return y;
}

Sommets : A (y = 0), B (test x > 0), C (y = 1), D (test x < 0), E (y = 2), F (return). Arcs : A vers B, B vers C (vrai), B vers D (faux), C vers D, D vers E (vrai), D vers F (faux), E vers F. Des quatre chemins de A à F, celui qui passe par C et E est infaisable : x ne peut être à la fois positif et négatif.

Critères de couverture :

• des sommets : chaque instruction est exécutée. Ici {1, −1} suffit.
• des arcs : chaque branche de chaque test est empruntée. Ici {1, −1} suffit encore.
• des chemins faisables : il faut {1, −1, 0}, et la valeur limite 0 apparaît.

Couvrir tous les arcs fait passer par tous les sommets, l'inverse est faux : pour if (x < 0) x = -x sans « sinon », le test x = −3 passe par tous les sommets sans emprunter l'arc « faux ». Il faut ajouter x = 3. Une boucle crée un cycle et une infinité de chemins. On se limite alors aux chemins sans cycle, ou on borne le nombre de tours (zéro, un, plusieurs).

Test exhaustif d'une condition

Quand une condition combine des conditions par && ou ||, on réalise toutes les façons de l'évaluer, en tenant compte de l'évaluation paresseuse (dans c1 && c2, c2 n'est pas évaluée si c1 est fausse). Pour (a mod 4 = 0 && a mod 100 <> 0) || a mod 400 = 0 :

• non multiple de 4, non multiple de 400 : 2023
• multiple de 4, non multiple de 100, la fin n'est pas évaluée : 2024
• multiple de 4 et de 100, non multiple de 400 : 1900
• multiple de 400 : 2000.

Le cas « non multiple de 4 mais multiple de 400 » est impossible. On retrouve les quatre tests du partitionnement.

Méthodes

• Avant d'écrire une fonction, écrire sa signature, ses préconditions et sa postcondition.
• Pour une boucle : un variant entier naturel strictement décroissant, puis un invariant qui, avec la condition de sortie, donne la postcondition (initialisation, conservation, sortie).
• Pour une fonction récursive : variant sur les arguments, récurrence pour la correction.
• Pour la complexité : compter tours de boucle ou appels, donner le pire cas, énoncer la loi avant tout cas moyen.
• Ne jamais comparer des flottants par l'égalité. Se méfier des différences de nombres proches.
• En C surtout, placer des assertions sur les entrées, les indices et les pointeurs.
• Pour tester : partitionner, ajouter les limites, viser la couverture des arcs sur les chemins faisables.

Ce qu'il faut savoir refaire en khôlle

1. Expliquer pourquoi 0.1 +. 0.2 = 0.3 vaut false et comparer correctement deux flottants.
2. Décrire la chaîne source, objet, exécutable en C et le rôle d'un fichier d'en-tête.
3. Prouver la terminaison de l'algorithme d'Euclide par un variant.
4. Prouver la correction totale de l'exponentiation rapide et donner sa complexité.
5. Calculer le coût moyen d'une recherche séquentielle en énonçant l'hypothèse de probabilité.
6. Montrer que n ajouts dans un tableau dynamique à capacité doublée coûtent O(n).
7. Spécifier une fonction et y placer des assertions défensives.
8. Tracer un graphe de flot de contrôle, repérer un chemin infaisable et couvrir tous les arcs.

Les résultats à connaître

En informatique, les « résultats » sont les principes de preuve, les propriétés des flottants et les coûts de référence.

• Principe du variant : un entier naturel qui décroît strictement à chaque tour (ou appel récursif) garantit la terminaison : exigible avec justification.
• Principe de l'invariant : une propriété vraie à l'entrée et conservée par un tour est vraie à la sortie : exigible avec justification.
• Correction totale = correction partielle + terminaison. Un programme qui ne termine jamais est partiellement correct pour toute spécification : exigible.
• Fonction récursive : correction par récurrence (souvent forte) sur la quantité qui sert de variant : exigible.
• Flottants sur 64 bits : 53 bits de précision, addition non associative, absorption, cancellation, comparaison avec une tolérance : exigible, à savoir illustrer.
• Entiers machine bornés. En C, le dépassement d'un entier signé est un comportement indéfini : exigible.
• Une boucle qui divise un entier n ≥ 1 par 2 à chaque tour jusqu'à 0 fait ⌊log₂ n⌋ + 1 tours : exigible avec justification.
• Deux boucles imbriquées sur les couples i < j d'un tableau de taille n font n(n − 1)/2 tours : exigible avec justification.
• Recherche dichotomique dans un tableau trié de taille n ≥ 1 : au plus ⌊log₂ n⌋ + 1 tours, donc O(log n) : exigible avec justification.
• Coût amorti O(1) de l'ajout dans un tableau dynamique à capacité doublée : exigible avec justification sur cet exemple.
• Couvrir tous les arcs d'un graphe de flot de contrôle couvre tous les sommets, la réciproque est fausse : exigible.
• Hors programme signalé : génération automatique de tests, théorie des paradigmes, GOTO, cas moyen au-delà d'exemples simples.

Clés de démonstration

Terminaison par variant. On exhibe un entier v, positif ou nul à chaque test, qu'un tour fait baisser d'au moins 1. Une infinité de tours donnerait une suite infinie strictement décroissante d'entiers naturels, ce qui est impossible. L'astuce est de prendre v = taille de la zone qui reste à traiter, par exemple d − g + 1.

Correction par invariant. On écrit la postcondition, puis on la généralise en remplaçant la borne finale par la variable de boucle. On vérifie initialisation et conservation, puis on combine l'invariant avec la négation de la condition. L'astuce est de viser un invariant qui, à la sortie, donne exactement la postcondition.

Fonction récursive. Récurrence forte sur le variant : on traite le cas de base, puis on suppose les appels récursifs corrects. L'astuce est de vérifier que chaque appel porte sur un argument plus petit qui vérifie encore la précondition.

Complexité logarithmique. Si une taille entière, égale à n au départ, est au moins divisée par 2 à chaque tour, elle vaut au plus n/2^t après t tours. Elle tombe donc à 0 en au plus ⌊log₂ n⌋ + 1 tours. L'astuce est de raisonner sur la taille restante plutôt que sur les indices.

Coût amorti. On somme les coûts réels d'une suite de n opérations au lieu de borner chacune par son pire cas. L'astuce est la somme géométrique : 1 + 2 + … + 2^p < 2^{p + 1}.

Arcs et sommets. Tout sommet autre que l'entrée termine un arc, donc emprunter chaque arc fait passer par chaque sommet.

Exemples et contre-exemples à connaître

1. let rec f n = f n ne termine jamais, donc il est partiellement correct pour n'importe quelle spécification. C'est pourquoi on exige la correction totale.
2. « 0 ≤ i ≤ n » est un invariant de presque toute boucle de parcours, mais il ne prouve rien. Un invariant utile mentionne le résultat partiel.
3. En C, for (unsigned int i = n - 1; i >= 0; i--) ne termine jamais : un entier non signé est toujours positif ou nul, et 0 − 1 donne le plus grand entier non signé.
4. En C, double y = 7 / 2; donne 3.0 : la division est entière, car ses deux opérandes sont des int, et la conversion vient après.
5. int carre(int x) { return x + x; } passe les tests x = 0 et x = 2. Un test réussi ne prouve pas la correction, il faut des représentants de plusieurs classes.
6. Avec des int de 32 bits, 12! = 479 001 600 tient, mais 13! = 6 227 020 800 dépasse 2 147 483 647.
7. Une capacité augmentée de 1 au lieu de doublée coûte n(n − 1)/2 recopies pour n ajouts : plus de coût amorti O(1).
8. Pour a = c = 1 et b = 10⁸, la formule (−b + √Δ)/(2a) donne en flottants environ −7,45 × 10⁻⁹ au lieu de −1,0 × 10⁻⁸ : 25 % d'erreur par cancellation.
9. Dans while (i < n && t[i] != x), l'ordre compte : écrire t[i] != x && i < n lit t[n], hors du tableau, quand x est absent.

Techniques du chapitre

Technique 1, le variant « taille de la zone restante ». Mini-exercice : la boucle while (i < j) { echanger(t, i, j); i++; j--; } termine, avec i = 0 et j = n − 1 au départ. Variant : j − i + 1. Il vaut n ≥ 0 au départ. Dans un tour on a i < j, donc j − i + 1 ≥ 2, et il baisse de 2, donc reste positif ou nul.

Technique 2, l'invariant tiré de la postcondition. Mini-exercice : pour le maximum m d'un tableau t non vide, on parcourt i de 1 à n − 1. Postcondition : m est le maximum de t[0..n − 1]. Invariant au début du tour i : m est le maximum de t[0..i − 1]. Avec m = t[0] au départ, il est vrai pour i = 1, et à la sortie i = n donne la postcondition.

Technique 3, compter les tours d'une boucle doublante. Mini-exercice : for (int i = 1; i < n; i = 2 * i) fait combien de tours pour n ≥ 1 ? Au tour t, i vaut 2^{t − 1}. Il y a donc ⌈log₂ n⌉ tours. Vérification : n = 1 donne 0 tour, n = 8 donne 3 tours (1, 2, 4), n = 9 donne 4 tours.

Technique 4, comparer en écart relatif. Mini-exercice : en OCaml, let proches x y eps = abs_float (x -. y) <= eps *. max (abs_float x) (abs_float y). Pour x = 10²⁰ et y = 10²⁰ + 10⁵, l'écart relatif vaut environ 10⁻¹⁵ : proches en relatif, pas en absolu.

Technique 5, partitionner puis tester les limites. Mini-exercice : dans a b x teste a ≤ x ≤ b. Classes : x < a, x entre a et b, x > b, intervalle vide a > b, plus les limites x = a et x = b. Jeu : (1, 5, 0) faux, (1, 5, 3) vrai, (1, 5, 6) faux, (1, 5, 1) vrai, (1, 5, 5) vrai, (5, 1, 3) faux.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

/* pgcd : a >= 0, b >= 0. Renvoie le pgcd de a et b (pgcd(0, 0) = 0). */
int pgcd(int a, int b) {
    assert(a >= 0 && b >= 0);
    /* invariant : pgcd(a, b) = pgcd(a0, b0), a >= 0, b >= 0 */
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

(* division : int -> int -> int * int
   Précondition : a >= 0 et b > 0.
   Postcondition : (q, r) avec a = q * b + r et 0 <= r < b. *)
let division a b =
  assert (a >= 0 && b > 0);
  let q = ref 0 and r = ref a in
  (* invariant : a = !q * b + !r et !r >= 0 *)
  while !r >= b do
    r := !r - b;
    incr q
  done;
  (!q, !r)

/* t trié par ordre croissant, n >= 0. Renvoie un indice de x dans t, ou -1. */
int dicho(int t[], int n, int x) {
    int g = 0, d = n - 1;
    /* invariant : si x est dans t, il est dans t[g..d] */
    while (g <= d) {
        int m = g + (d - g) / 2;
        if (t[m] == x) return m;
        if (t[m] < x) g = m + 1;
        else d = m - 1;
    }
    return -1;
}

exception Trouve

(* a_doublon : 'a array -> bool *)
let a_doublon t =
  let n = Array.length t in
  try
    for i = 0 to n - 1 do
      for j = i + 1 to n - 1 do
        if t.(i) = t.(j) then raise Trouve
      done
    done;
    false
  with Trouve -> true

(* incremente : int array -> unit
   Ajoute 1 à l'entier codé par t. Si t ne contient que des 1, le remet à 0 et lève Failure. *)
let incremente t =
  let k = Array.length t in
  let i = ref 0 in
  while !i < k && t.(!i) = 1 do
    t.(!i) <- 0;
    incr i
  done;
  if !i = k then failwith "incremente : dépassement"
  else t.(!i) <- 1

#include <assert.h>
#include <limits.h>
/* fact : n >= 0. Renvoie n!, arrête le programme si n! dépasse INT_MAX. */
int fact(int n) {
    assert(n >= 0);
    int r = 1;
    for (int k = 2; k <= n; k++) {
        assert(r <= INT_MAX / k); /* r * k ne déborde pas */
        r = r * k;
    }
    return r;
}

/* Renvoie le premier indice de x dans t[0..n-1], ou n s'il est absent. */
int premier(int t[], int n, int x) {
    int i = 0;
    while (i < n && t[i] != x) i++;
    return i;
}

(* racines : float -> float -> float -> float * float
   Précondition : a <> 0, b > 0, b *. b -. 4. *. a *. c > 0. *)
let racines a b c =
  let r = sqrt (b *. b -. 4. *. a *. c) in
  let x2 = (-. b -. r) /. (2. *. a) in
  (c /. (a *. x2), x2)

(* puiss : int -> int -> int
   Précondition : n >= 0. Postcondition : x puissance n (hors dépassement). *)
let rec puiss x n =
  if n = 0 then 1
  else
    let y = puiss x (n / 2) in
    if n mod 2 = 0 then y * y else x * y * y

Erreurs fréquentes