Comment démontrer qu'un algorithme avec une boucle donne toujours le bon résultat ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, on nous demande souvent de « prouver » un algorithme, et j'avais du mal à comprendre ce que cela signifiait : le programme marche, pourquoi le démontrer ? J'ai compris le jour où un de mes programmes, testé sur dix exemples, s'est révélé faux sur un cas limite. L'invariant de boucle m'est alors apparu comme la version informatique du raisonnement par récurrence.

L'enjeu et les notions du programme

Prouver la correction et la terminaison d'un algorithme itératif par un invariant (récurrence) et un variant (suite d'entiers décroissante).

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Tester un programme sur des exemples ne prouve pas qu'il est juste. Problématique : comment démontrer qu'un algorithme comportant une boucle donne le bon résultat pour toutes les entrées ?

2. 2. NSI : l'algorithme étudié

   2,5 min

   Division de $a\ge 0$a≥0 par $b>0$b>0 par soustractions : on pose $q=0$q=0 et $r=a$r=a ; tant que $r\ge b$r≥ b, on remplace $r$r par $r-b$r-b et $q$q par $q+1$q+1. On renvoie $q$q et $r$r.

   Exemple avec $a=17$a=17, $b=5$b=5 : $(q;r)$(q;r) vaut $(0;17)$(0;17), $(1;12)$(1;12), $(2;7)$(2;7), $(3;2)$(3;2). On s'arrête car $2<5$2<5 : quotient 3, reste 2, et $17=5\times 3+2$17=5×3+2.

3. 3. Mathématiques : invariant et variant

   4,5 min

   Invariant : « $a=bq+r$a=bq+r et $r\ge 0$r≥0 ». Initialisation : avant la boucle, $q=0$q=0, $r=a$r=a, donc $bq+r=a$bq+r=a, et $r=a\ge 0$r=a≥0. Conservation : si $a=bq+r$a=bq+r et $r\ge b$r≥ b au début d'un tour, après le tour $b(q+1)+(r-b)=bq+r=a$b(q+1)+(r-b)=bq+r=a, et $r-b\ge 0$r-b≥0. Par récurrence sur le nombre de tours, l'invariant est vrai après chaque tour.

   À la sortie, la condition de boucle est fausse : $r<b$r<b. Avec l'invariant, $a=bq+r$a=bq+r et $0\le r<b$0≤ r<b : ce sont exactement le quotient et le reste de la division euclidienne. L'algorithme est correct.

   Terminaison : $r$r est un entier positif qui diminue de $b\ge 1$b≥1 à chaque tour ; une suite d'entiers naturels strictement décroissante ne peut pas être infinie. Le nombre de tours est $q$q. C'est le variant de boucle.

   Le cas limite $b=0$b=0 montre l'utilité des hypothèses : $r$r ne décroît plus et la boucle ne s'arrête jamais.

4. 4. Conclusion

   1,5 min

   Un invariant de boucle est une récurrence déguisée : vrai au départ, conservé à chaque tour, il donne le résultat à la sortie. Un variant, entier qui décroît, prouve l'arrêt. Ensemble, ils démontrent un algorithme pour toutes les entrées. J'ouvre sur les outils de preuve automatique, utilisés pour les logiciels du métro ou des avions.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre invariant (propriété conservée) et variant (quantité qui décroît).
• Oublier de prouver la terminaison.
• Ne pas utiliser la condition de sortie dans la conclusion.

Revoir les notions

• Suites : récurrence et limites (Terminale spé maths) →
• Nombres et calculs (Seconde) →

Autres questions : logique et calculabilité

• Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
• Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?
• Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?
• Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?

Toutes les questions maths-nsi →