22bis Cours Correction

Questions fondamentales

Les trois questions fondamentales à se poser à propos de tout algorithme sont les suivantes :

• donne-t-il un résultat ou ne s’arrête-t-il jamais ? (Notion de terminaison) ;
• donne-t-il le résultat attendu ou calcule-t-il autre chose ? (Notion de correction) ;
• donne-t-il le résultat en un temps raisonnable ou faut-il attendre très longtemps ? (Notion de complexité).

Correction

Comment prouve-t-on qu’un algorithme fait bien ce qui est attendu de lui ? Basons-nous sur un exemple : celui de la division euclidienne.

🐍 Script Python

def division(a : int,b : int):
    """
    Entrée : a et b sont deux entiers positifs non nuls
    Sortie : quotient q et reste r de la division euclidienne de a par b
    """
    q = 0
    r = a
    while r >= b:
        q = q + 1
        r = r - b
    return (q, r)

print(division(22, 3))

Écrire la trace de l’algorithme pour \(a=19\) et \(b=3\).

Trace de l'algorithme

• \(a=19\) et \(b=3\)
• \(q = 0\)
• \(r = a = 19\)
• \(r \geq b\) ? \(19 \geq 3\) ? oui
  • \(q = q + 1 = 2\)
  • \(r = r - b = 19 - 3 = 16\)
• \(r \geq b\) ? \(16 \geq 3\) ? oui
  • \(q = q + 1 = 3\)
  • \(r = r - b = 16 - 3 = 13\)
• \(r \geq b\) ? \(13 \geq 3\) ? oui
  • \(q = q + 1 = 4\)
  • \(r = r - b = 13 - 3 = 10\)
• \(r \geq b\) ? \(10 \geq 3\) ? oui
  • \(q = q + 1 = 5\)
  • \(r = r - b = 10 - 3 = 7\)
• \(r \geq b\) ? \(7 \geq 3\) ? oui
  • \(q = q + 1 = 6\)
  • \(r = r - b = 7 - 3 = 4\)
• \(r \geq b\) ? \(4 \geq 3\) ? oui
  • \(q = q + 1 = 7\)
  • \(r = r - b = 4 - 3 = 1\)
• \(r \geq b\) ? \(1 \geq 3\) ? non : fin de la boucle while
• return \((q = 7, r = 1)\)

Preuve de la correction : l’invariant de boucle

Un invariant de boucle est une proposition qui :

• est vérifiée à l’initialisation de la boucle ;
• reste vraie à chaque itération de la boucle.
• après le dernier tour de boucle, la véracité de l'invariant de boucle correspond à ce qui est attendu de l'algorithme (correction de l'algorithme)

Remarque. Cette méthode permet de décrire une proposition qui sera vraie à l’issue de la boucle. Un invariant de boucle bien choisi doit, conjointement à la condition d’arrêt de la boucle, permettre de montrer que l’algorithme est correct, c’est-à-dire qu’il fait bien ce que l’on attend de lui.

Dans notre exemple ci-dessus de la division euclidienne, l’invariant de boucle est \(a=bq+r\). En effet :

• À l’initialisation, \(q=0\) et \(r=a\), ainsi \(bq+r=b\times0+a=a\).
• À chaque tour de boucle, \(q\) devient \(q+1\) et \(r\) devient \(r−b\). Si au début de la boucle on \(a=bq+r\), après les affectations on obtient : \(b(q+1)+(r-b)=bq+b+r-b=bq+r\). Donc \(a=bq+r\) reste vraie à chaque itération de la boucle.

Ainsi, \(a=bq+r\) est notre invariant de boucle. À l’issue de l’algorithme, \(a=bq+r\) et comme la boucle s’est terminée cela signifie aussi que \(r<b\) (condition d’arrêt de la boucle while). C’est ce que l’on souhaitait obtenir. Cet algorithme est donc correct.

Méthode

1. Choisir et exprimer un invariant judicieux.
2. Initialisation : Démontrer qu’il est vérifié avant d’entrer dans la boucle (utiliser les préconditions).
3. Conservation : Démontrer que s’il est vérifié au début d’une itération quelconque, il l’est aussi au début de l’itération suivante (utiliser le corps de la boucle).
4. Conclusion : Instancier l’invariant en sortie de boucle et en déduire une postcondition (utiliser la négation de la condition du while).