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

Fiche de révision : Pourquoi une boucle s'arrête et pourquoi elle est juste

L’essentiel de la leçon, ce qu’il faut retenir, les pièges et un petit test : une page à relire avant le contrôle.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · Tle · algorithmique

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 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

⚠ 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

  1. Deux questions, pas une
  2. Les deux outils
  3. Une preuve complète sur un exemple minuscule
  4. Ce que la preuve rapporte

Je me teste

  1. Que doit être un variant de boucle ?

    1. Une propriété vraie à chaque tour
    2. Un entier positif qui décroît strictement
    3. Une variable qui compte les tours
  2. Un invariant prouve la correction à condition d'être vrai…

    1. seulement à la sortie de la boucle
    2. seulement après le premier tour
    3. 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

La leçon complète, ses exercices et ses jeux : ludicademy.fr/lecon/2416fiche de révision · usage libre en classe et à la maison

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.