22 Cours Terminaison

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é).

Terminaison⚓︎

Comment prouve-t-on qu’un algorithme se termine ? 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 terminaison : le variant de boucle⚓︎

Pour montrer que cet algorithme se termine, on doit prouver que la boucle while ne s’exécute pas indéfiniment.
Pour cela nous allons utiliser ce que l’on appelle un variant de boucle.
Le variant de boucle doit varier à chaque tour de boucle, et le nombre de valeurs possibles qu'il peut prendre étant limité (fini), le nombre de tours de boucle sera également limité. Nous prouvons ainsi que la boucle n'est pas infinie.

Nous allons définir un variant de boucle comme une valeur qui :

doit être positive ou nulle dans la boucle;
décroît strictement à chaque itération de la boucle.

Ce variant de boucle est donc lié à la condition de la boucle while.
Dans notre exemple, le variant de boucle est facile à trouver : c’est \(r-b\).
La valeur \(r-b\) est positive à la première itération (\(r=a\) et \(a>b\) donc \(r-b=a-b>0\)). De plus elle décroit à chaque itération de la boucle puisque l’on soustrait \(b\) (qui est positif non nul) à \(r\). Donc au bout d’un certain nombre d’itérations, notre variant de boucle sera négatif; ce qui met fin à la boucle while puisque la boucle se poursuit à la condition que \(r \geq b\), autrement dit \(r-b \geq 0\).

Autre exemple :⚓︎

🐍 Script Python

L = [10, 5, 6, 7, 3, 4, 5]
while L: #autrement dit : tant que L est non vide
    print(L.pop())

Quel variant de boucle va-t-on choisir ?

Réponse

On veut trouver un nombre qui est positif pour représenter que la liste est non vide, puis qui ne le sera plus si la liste est vide.
De plus, il doit être strictement décroissant à chaque tour de boucle.
Dans ce cas, on prend comme variant de boucle : len(L) (ou en français : la longueur de la liste).
En effet, à chaque tour de boucle, on effectue L.pop() qui fait décroitre de \(1\) la longueur de la liste.
Au départ, cette longueur est strictement positive, on sait qu'elle décroit strictement à chaque itération, et la boucle s'arrête dès que la longueur est nulle.
C'est donc bien un variant de boucle qui nous prouve que la boucle n'est pas infinie et que l'algorithme se termine bien.

Remarque : une boucle for se termine toujours.

Un variant de boucle permet de prouver qu’une boucle while se termine mais ne permet pas de prouver que l’algorithme fait ce que l’on attend de lui. C’est le rôle de l’invariant de boucle.