Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode
- Terminaison et correction sont deux questions distinctes, à prouver séparément
- Le variant est un entier positif qui décroît strictement : il force l'arrêt
- L'invariant est vrai avant la boucle et conservé par chaque tour, donc vrai à la sortie
Deux questions, pas une
Essayer un programme sur quelques cas ne prouve rien : les essais montrent la présence de bogues, jamais leur absence. Prouver un algorithme à boucle demande de répondre à DEUX questions séparées, et l'on ne peut pas répondre à l'une par l'autre.
La TERMINAISON : cette boucle s'arrête-t-elle, toujours ? La CORRECTION : si elle s'arrête, le résultat est-il celui qu'on voulait ? Un algorithme qui s'arrête toujours en donnant une réponse fausse et un algorithme juste qui ne s'arrête jamais sont deux échecs distincts, qui se réparent différemment.
Les deux outils
| La question | L'outil | Ce qu'on doit exhiber | Ce que ça prouve |
|---|---|---|---|
| S'arrête-t-elle ? | Le VARIANT | Un entier positif qui décroît strictement à chaque tour | Un entier positif ne décroît pas indéfiniment |
| Est-elle juste ? | L'INVARIANT | Une propriété vraie avant, et conservée par chaque tour | Elle est donc vraie à la sortie |
| Les deux ensemble | La preuve complète | Variant plus invariant plus condition de sortie | Le résultat annoncé, toujours |
Une preuve complète sur un exemple minuscule
Prenons la recherche du maximum d'une liste non vide, et prouvons-la entièrement. L'algorithme : max prend la valeur du premier élément, i prend la valeur 2 ; tant que i est inférieur ou égal à la longueur, si l'élément i dépasse max alors max prend sa valeur, puis i prend la valeur i plus 1.TERMINAISON. Posons comme variant la quantité « longueur moins i plus 1 ». Elle est entière. Elle est positive tant que la boucle tourne, puisque la condition impose i inférieur ou égal à la longueur. Et elle décroît strictement de un à chaque tour, puisque i augmente de un et que la longueur ne change pas. Un entier positif qui décroît strictement atteint forcément le plancher : la boucle s'arrête. CORRECTION. Posons comme invariant : « max contient le plus grand des i moins 1 premiers éléments ». Vérifions-le avant le premier tour, avec i valant 2 : max contient le premier élément, qui est bien le plus grand du premier élément tout seul. Vrai. Supposons-le vrai en début de tour, et faisons le tour : soit l'élément i dépasse max et devient le nouveau max, soit il ne le dépasse pas et max reste le plus grand ; dans les deux cas, après incrémentation de i, max contient bien le plus grand des i moins 1 premiers. L'invariant est conservé. SORTIE. On sort quand i vaut longueur plus 1 ; l'invariant dit alors que max contient le plus grand des « longueur » premiers éléments, c'est-à-dire de toute la liste. C'est exactement ce qu'on voulait, et cela vaut pour n'importe quelle liste non vide, sans en essayer une seule.

Ce que la preuve rapporte
Un invariant explicite n'est pas un exercice scolaire : c'est la phrase qu'on écrit en commentaire au-dessus de la boucle, et qui permet à quiconque de la relire six mois plus tard sans la dérouler. Quand un algorithme rate, l'invariant désigne aussi le coupable — on cherche le tour où il cesse d'être vrai, et l'on tient la ligne fautive sans avoir à tout relire.






- Terminaison et correction sont deux questions distinctes, à prouver séparément
- Le variant est un entier positif qui décroît strictement : il force l'arrêt
- L'invariant est vrai avant la boucle et conservé par chaque tour, donc vrai à la sortie
- Invariant plus condition de sortie donnent le résultat, pour toute donnée et sans essai
Que doit être un variant de boucle ?
C'est l'impossibilité de décroître indéfiniment dans les entiers positifs qui force l'arrêt.
Un invariant prouve la correction à condition d'être vrai…
S'il est faux au départ, aucun tour ne le rendra vrai : la preuve tombe, y compris sur une liste vide.




