Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire
Tle · Algorithmique

Pourquoi une boucle s'arrête et pourquoi elle est juste

terminaison et invariant, les deux preuves d'un programme

≈ 5 min de lecture · palier Tle · trois questions à la fin

Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode

En bref
  • 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 questionL'outilCe qu'on doit exhiberCe que ça prouve
S'arrête-t-elle ?Le VARIANTUn entier positif qui décroît strictement à chaque tourUn entier positif ne décroît pas indéfiniment
Est-elle juste ?L'INVARIANTUne propriété vraie avant, et conservée par chaque tourElle est donc vraie à la sortie
Les deux ensembleLa preuve complèteVariant plus invariant plus condition de sortieLe 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.

L'invariant doit être vrai AVANT le premier tour, y compris quand la boucle n'en fait aucun. C'est le cas limite qu'on saute toujours, et c'est là que se cachent les erreurs de liste vide : un invariant qu'on n'a vérifié qu'après le premier tour n'a pas été vérifié du tout.

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.

SkeletJ'ai testé sur vingt listes. Ça marche à tous les coups.
OscarVous avez donc prouvé qu'il marche sur vingt listes.
SkeletSur les autres aussi, probablement.
Oscar« Probablement ». Un variant et un invariant vous donneraient « toujours ».
SkeletC'est plus long à écrire que vingt essais.
OscarEt c'est valable sur une infinité de listes. Comparez le rendement, plutôt que la peine.
À retenir
  • 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
Exercice

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.

Exercice

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.

Expressions à emporter

Expression Traduction
terminaisonla preuve que la boucle s'arrête
variantun entier positif qui décroît
invariantla propriété que chaque tour conserve

Maintenant, jouez-la

Trois questions pour voir

La règle est lue. Voyons si elle est entrée : trois questions, ici même, sans compte.

7 exercices corrigés de logique en Tle → sans compte, corrigés à chaque réponse

La règle est lue ; il reste à la faire entrer. Trois minutes suffisent.

Jouer « le pont de cordes » → Quiz Express · sans compte

Ou choisissez votre salle :

Et côté jeux de société : 🎪 Démineur → les règles de démineur

Sur papier : 🖨️ La fiche de cette leçon

Pour réviser : 📝 La fiche de révision et celle du chapitre « algorithmique » (3 leçons)

Toutes les leçons Tle