Pourquoi une boucle s'arrête et pourquoi elle est juste
Objectif : terminaison et invariant, les deux preuves d'un programme
L’essentiel
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 ?
À 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
Le tableau à connaître
| 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 |
⚠ Attention, piège
- L'invariant doit être vrai AVANT le premier tour, y compris quand la boucle n'en fait aucun.
Exemples
- TERMINAISON. Posons comme variant la quantité « longueur moins i plus 1 ».
Le plan de la leçon
- Deux questions, pas une
- Les deux outils
- Une preuve complète sur un exemple minuscule
- Ce que la preuve rapporte
Je me teste
Que doit être un variant de boucle ?
- Une propriété vraie à chaque tour
- Un entier positif qui décroît strictement
- Une variable qui compte les tours
Un invariant prouve la correction à condition d'être vrai…
- seulement à la sortie de la boucle
- seulement après le premier tour
- avant le premier tour, et conservé ensuite
Le mot d’Oscar — Vous avez donc prouvé qu'il marche sur vingt listes.
Réponses : 1. B · 2. C