Les variants et invariants de boucle

Lors de l'écriture d'algorithmes un peu plus évolués, on se pose très souvent deux questions essentielles :

1. Est-ce que ma boucle va s’arrêter ?
2. Est-ce que mon algorithme fait bien ce que je veux ?

---

Le variant de boucle : garantir l’arrêt d’une boucle

Définition

Un variant de boucle est une variable (ou une quantité) dont la valeur évolue à chaque itération et qui se rapproche d’une valeur permettant l’arrêt de la boucle.

Si le variant évolue toujours dans le bon sens, alors la boucle ne peut pas être infinie.

---

Exemple simple

p = 1
while p < 23:
    p = 2 * p

On considère une boucle qui :

• commence avec une variable p valant 1 ;
• se répète tant que p est strictement inférieur à 23 ;
• multiplie p par 2 à chaque tour.

La condition d’arrêt est : p devient supérieur ou égal à 23.
Le variant est la variable p.
À chaque tour de boucle, la valeur de p augmente strictement.

On peut visualiser l’évolution de p :

Tour de boucle	Valeur de p
0	1
1	2
2	4
3	8
4	16
5	32

On est certain que p dépassera 23 : la boucle s’arrête.

---

À retenir

Un bon variant :

• est lié à la condition de boucle ;
• change à chaque itération ;
• permet de prouver la terminaison de la boucle.

---

L’invariant de boucle : garantir la correction de l’algorithme

Définition

Un invariant de boucle est une propriété qui est : VRAIE avant la boucle ET après chaque itération.

L’invariant permet de vérifier que chaque tour de boucle fait correctement son travail.

---

Méthode de raisonnement

Pour vérifier un invariant, on suit toujours 3 étapes, proches d’un raisonnement par récurrence :

• Initialisation : Montrer que l’invariant est vrai avant le premier tour de boucle.
• Maintenance : Montrer que si l’invariant est vrai au début d’un tour, il reste vrai après ce tour.
• Terminaison : Quand la boucle s’arrête, l’invariant permet de conclure que le résultat final est correct.

---

Exemple simple d’invariant

Somme des éléments d’une liste

s = 0
for i in range(len(liste)):
    s = s + liste[i]

On considère un algorithme qui :

• parcourt une liste élément par élément ;
• utilise une variable s initialisée à 0 ;
• ajoute chaque élément de la liste à s.

Invariant

Au début de chaque itération, s est égal à la somme des éléments déjà parcourus.

Initialisation

Avant de commencer, aucun élément n’a été parcouru et s vaut 0.
La somme d’une liste vide est bien 0.

Maintenance

À chaque tour, on ajoute le nouvel élément à s.
La propriété reste vraie.

Terminaison

Quand tous les éléments ont été parcourus, s contient la somme de toute la liste.

---

Exemple complet : tri par insertion

Objectif : trier une liste de nombres par ordre croissant.

def insertion(liste):
    for i in range(len(liste)):
        element = liste[i]
        j = i - 1
        while j >= 0 and element < liste[j]:
            liste[j+1] = liste[j]
            j -= 1
        liste[j+1] = element
    return liste

Principe de l’algorithme :

• on parcourt la liste de gauche à droite ;
• à chaque étape, on insère l’élément courant à la bonne place parmi les éléments précédents déjà traités.

Visualisation de l'algorithme

---

Invariant :

Au début de chaque itération, la sous-liste située avant la position courante est triée.

---

• Initialisation
  Au départ, la sous-liste contient un seul élément.
  Une liste à un seul élément est toujours triée.

• Maintenance
  À chaque étape :

  • on compare l’élément courant avec ceux de gauche ;
  • on décale les éléments plus grands ;
  • on insère l’élément à la bonne position.

  À la fin de l’itération, la sous-liste reste triée.

• Terminaison
  Quand la boucle se termine, toute la liste est triée.
  L’algorithme est donc correct.

---

Résumé

Notion	À quoi ça sert ?
Variant	Montrer que la boucle s’arrête
Invariant	Montrer que l’algorithme est correct

✅ Variant → terminaison
✅ Invariant → correction