Lorsqu'on utilise une boucle (for ou while), on modifie souvent des variables à chaque itération. Mais certaines propriétés restent vraies tout au long de la boucle : ce sont les invariants.
On souhaite calculer la somme des éléments d’une liste.
liste = [2, 5, 7, 3]
somme = 0
for valeur in liste:
somme += valeur
Pendant l’exécution, à chaque tour de boucle :
somme contient la somme des éléments déjà parcourus de la liste.Donc, invariant de boucle :
somme contient la somme des éléments de
listedéjà vus.
liste = [6, 4, 9, 1]
maximum = liste[0]
for element in liste[1:]:
if element > maximum:
maximum = element
Ici, l’invariant est :
maximumcontient la plus grande valeur parmi celles déjà parcourues.
| Terme | Signification |
|---|---|
| Invariant de boucle | Une propriété qui reste vraie à chaque tour de boucle |
| Avant la boucle | L’invariant est déjà vrai avant la première itération |
| Après chaque itération | L’invariant reste vrai, même si les variables changent |
| Utilité | Vérifier la logique, corriger un bug, ou prouver que l’algorithme fonctionne |