Invariant de boucle — NSI Terminale

Invariant de boucle

Démontrer qu'un algorithme fonctionne sur quelques exemples ne suffit pas à prouver qu'il est correct dans tous les cas. L'outil mathématique qui permet cette preuve rigoureuse s'appelle l'invariant de boucle.

1. Correction d'un algorithme

Un algorithme est dit correct lorsqu'il produit exactement le résultat attendu pour toute entrée valide. Tester un algorithme sur plusieurs exemples qui « fonctionnent » ne constitue pas une preuve : comme en mathématiques, vérifier qu'une propriété est vraie sur un cas particulier n'a pas valeur de démonstration.

Pour les algorithmes de tri par insertion et par sélection, nous avons pu observer qu'ils trient correctement les tableaux testés. Mais comment être certain qu'ils fonctionneront dans tous les cas possibles ? C'est là qu'intervient l'invariant de boucle.

2. Définition : qu'est-ce qu'un invariant de boucle ?

Définition

Un invariant de boucle est une propriété logique qui est vraie avant la première itération, et qui reste vraie avant chaque nouvelle itération tout au long de l'exécution de la boucle.

Intuitivement, c'est une assertion qui « résiste » à chaque passage dans la boucle. Trouver le bon invariant, c'est identifier ce qui ne change pas structurellement, même si les données évoluent.

3. Application : tri par insertion

L'algorithme

VARIABLE
  t : tableau d'entiers
  i, j, k : nombres entiers

DEBUT
  j ← 2
  tant que j <= longueur(t) :   // boucle principale
    i ← j - 1
    k ← t[j]
    tant que i > 0 et t[i] > k :   // boucle interne
      t[i+1] ← t[i]
      i ← i - 1
    fin tant que
    t[i+1] ← k
    j ← j + 1
  fin tant que
FIN
  

Identification de l'invariant

On divise le tableau t en deux parties à chaque itération : la partie déjà triée t[1…j-1] et le reste encore non trié. Observons l'évolution sur l'exemple t = [27, 10, 12, 8, 11] :

Itération	Valeur de j	État du tableau	t[1…j-1] trié ?
Avant la 1^re	j = 2	27 10 12 8 11	✔ [27] — 1 élément
Fin de la 1^re	j = 3	10 27 12 8 11	✔ [10, 27]
Fin de la 2^e	j = 4	10 12 27 8 11	✔ [10, 12, 27]
Fin de la 3^e	j = 5	8 10 12 27 11	✔ [8, 10, 12, 27]
Fin de la 4^e	j = 6	8 10 11 12 27	✔ [8, 10, 11, 12, 27]

✔

Invariant de boucle retenu

« Le sous-tableau t[1…j-1] est trié » — cette propriété est vraie avant chaque itération de la boucle principale.

4. Démonstration en 3 étapes

Identifier un candidat invariant ne suffit pas. Il faut le démontrer rigoureusement selon trois étapes incontournables :

Étape 1

Initialisation

Montrer que l'invariant est vrai avant la première itération de la boucle.

Étape 2

Conservation

Montrer que si l'invariant est vrai en début d'itération, il reste vrai en fin d'itération.

Étape 3

Terminaison

Une fois la boucle terminée, déduire que l'algorithme produit bien le résultat attendu.

Étape 1 — Initialisation

Preuve

Avant la première itération, j = 2, donc t[1…j-1] = t[1…1] ne contient qu'un seul élément. Un tableau à un seul élément est trivialement trié. L'invariant est vrai.

Étape 2 — Conservation

Preuve

Supposons que t[1…j-1] est trié en début d'itération. La boucle interne décale vers la droite les éléments t[j-1], t[j-2], … jusqu'à trouver la bonne position pour insérer l'élément k = t[j]. À la fin de cette opération, t[1…j] est trié. Après l'instruction j ← j+1, ce tableau t[1…j] devient le nouveau t[1…j-1]. L'invariant est donc conservé.

Étape 3 — Terminaison

Preuve

La boucle s'arrête lorsque j > n (longueur du tableau), soit j = n + 1. En substituant dans l'invariant, on obtient que t[1…(n+1)-1] = t[1…n] est trié. Or t[1…n] est le tableau complet. Le tableau est donc entièrement trié à la fin de l'algorithme.

5. À retenir

Points clés du cours

La correction d'un algorithme ne se prouve pas par des exemples, mais par raisonnement mathématique.
Un invariant de boucle est une propriété vraie avant et après chaque itération.
La preuve s'articule toujours en trois temps : initialisation → conservation → terminaison.
Pour le tri par insertion, l'invariant « t[1…j-1] est trié » permet de conclure que le tableau est totalement trié en fin d'algorithme.

Contre-exemple — Invariant de boucle — NSI

Contre-exemple d'invariant de boucle

Terminale NSI — Algorithmique — Correction des algorithmes

Trouver un candidat invariant ne suffit pas : encore faut-il vérifier qu'il est réellement invariant, c'est-à-dire vrai à chaque itération. Un mauvais choix d'invariant mène à une démonstration incorrecte — ou impossible à terminer. Voici un exemple concret d'invariant mal choisi et ce qu'il implique.

1. L'algorithme étudié

On reprend l'algorithme de calcul de la somme des N premiers entiers :

i = 0
somme = 0
while i < N :
    i = i + 1
    somme = somme + i

On sait que l'invariant correct est : somme = i × (i+1) / 2. Mais supposons qu'un élève propose à la place l'invariant suivant :

Candidat invariant (mauvais choix)

« somme = i × i » — la somme est égale au carré de i.

2. Vérification itération par itération

Traçons l'exécution de l'algorithme et vérifions si la propriété somme = i² est bien vérifiée à chaque tour :

Tour	i	somme	i²	somme = i² ?
Avant la boucle	0	0	0	✔ vrai
Fin du tour 1	1	1	1	✔ vrai
Fin du tour 2	2	3	4	✘ faux (3 ≠ 4)
Fin du tour 3	3	6	9	✘ faux (6 ≠ 9)
Fin du tour 4	4	10	16	✘ faux (10 ≠ 16)

Contre-exemple trouvé

Dès le 2e tour, la propriété est fausse : somme = 3 mais i² = 4. La propriété somme = i² n'est donc pas un invariant de cette boucle.

3. Pourquoi l'étape de conservation échoue-t-elle ?

Essayons de démontrer la conservation avec cet invariant pour comprendre où ça bloque. On suppose qu'en début d'itération somme = i² et i < N. Après l'exécution du corps de la boucle :

// Début de l'itération : somme = i²
i = i + 1        // i devient i+1, notons i' = i+1
somme = somme + i  // somme devient somme + i' = i² + (i+1)

On obtient donc somme' = i² + (i+1). Pour que l'invariant soit conservé, il faudrait que somme' = i'², c'est-à-dire :

Calcul de vérification

i² + (i+1) = (i+1)²
i² + i + 1 = i² + 2i + 1
i = 2i

Cette égalité n'est vraie que si i = 0. Elle est fausse pour tout i ≥ 1. L'étape de conservation ne peut pas être démontrée.

4. Bon invariant vs mauvais invariant

✘ Mauvais invariant

somme = i²

Vrai pour i = 0 et i = 1, mais faux dès i = 2. La conservation échoue : on ne peut pas prouver que si c'est vrai au début d'un tour, ça le reste à la fin.

✔ Bon invariant

somme = i × (i+1) / 2

Vrai pour tout i ≥ 0. La conservation se démontre algébriquement à chaque tour, et la terminaison donne bien le résultat attendu.

5. Piège fréquent : vrai sur quelques cas ≠ invariant

On remarque que somme = i² est vrai pour i = 0 et i = 1. Un élève pourrait être tenté de conclure trop vite que c'est un invariant. C'est exactement le même raisonnement erroné que de « vérifier » un algorithme sur quelques exemples.

Règle d'or

Une propriété vraie sur quelques cas n'est pas forcément un invariant. Un invariant doit être démontré pour toutes les itérations sans exception, via les trois étapes : initialisation, conservation, terminaison.

6. À retenir

Points clés

Un contre-exemple suffit à réfuter un candidat invariant : il suffit de trouver une itération où la propriété est fausse.
Un invariant vrai seulement au début n'est pas un invariant de boucle.
L'étape de conservation est le vrai test : si elle ne peut pas être démontrée algébriquement, le candidat est invalide.
Pour trouver un bon invariant, on trace l'exécution et on cherche une relation stable entre les variables à chaque fin d'itération.