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

Ce chapitre traite des deux premières questions. La complexité fait l’objet d’un chapitre dédié.

Exemple fil rouge : la division euclidienne

Basons-nous sur un exemple concret : celui de la division euclidienne.

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

(7, 1)

Trace de l’algorithme

La trace d’un algorithme consiste à noter la valeur de chaque variable à chaque étape. C’est un outil essentiel pour comprendre le fonctionnement d’un programme.

Écrivons la trace pour \(a=22\) et \(b=3\) :

À la sortie de la boucle, \(q = 7\) et \(r = 1\). On a bien \(22 = 3 \times 7 + 1\) avec \(0 \leq 1 < 3\).

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.

Un variant de boucle est une quantité qui doit :

• être un entier positif ou nul à l’entrée de chaque tour de boucle ;
• décroître strictement à chaque itération.

Puisqu’un entier positif qui décroît strictement finit nécessairement par atteindre 0 ou devenir négatif, la boucle se terminera forcément.

Application à la division euclidienne

Dans notre exemple, un bon variant de boucle est \(r\) lui-même (ou plus précisément, la valeur de r au début de chaque tour).

• Positif à l’entrée de chaque tour ? Oui, car la boucle ne s’exécute que si \(r \geq b > 0\), donc \(r > 0\).
• Décroissance stricte ? Oui, car à chaque tour, \(r\) est remplacé par \(r - b\), et \(b > 0\), donc la nouvelle valeur de \(r\) est strictement inférieure à l’ancienne.

La boucle se termine donc nécessairement.

Remarques.

• 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.
• Une boucle for se termine toujours (car le nombre d’itérations est fixé à l’avance).

Preuve de la correction : l’invariant de boucle

Un invariant de boucle est une proposition qui :

• est vérifiée avant la première itération (initialisation) ;
• reste vraie après chaque itération (conservation).

Remarque. Un invariant bien choisi, combiné à la condition d’arrêt de la boucle, permet de montrer que l’algorithme produit le résultat attendu.

Application à la division euclidienne

L’invariant de boucle est \[a = b \times q + r \quad \text{avec } r \geq 0.\]

Initialisation. Avant la boucle, \(q = 0\) et \(r = a\), donc \(b \times q + r = b \times 0 + a = a\). L’invariant est vérifié.

Conservation. Supposons que \(a = b \times q + r\) au début d’un tour. Après les affectations \(q \leftarrow q + 1\) et \(r \leftarrow r - b\), on obtient : \[b \times (q+1) + (r-b) = bq + b + r - b = bq + r = a.\] L’invariant est conservé.

Conclusion. À la sortie de la boucle, l’invariant \(a = bq + r\) est toujours vrai, et la condition d’arrêt nous donne \(r < b\). On a donc bien \(a = bq + r\) avec \(0 \leq r < b\) : c’est exactement la définition de la division euclidienne. L’algorithme est correct.

Méthode générale

1. Choisir et exprimer un invariant judicieux.
2. Démontrer qu’il est vérifié avant d’entrer dans la boucle (utiliser les préconditions).
3. 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. Instancier l’invariant en sortie de boucle et en déduire une postcondition (utiliser la négation de la condition du while).

Un deuxième exemple : la multiplication par additions successives

def multiplication(a, b):
    """
    Entrée : a et b sont deux entiers naturels
    Sortie : le produit a * b
    """
    resultat = 0
    compteur = 0
    while compteur < b:
        resultat = resultat + a
        compteur = compteur + 1
    return resultat

print(multiplication(7, 5))

35

Terminaison. Le variant de boucle est \(b - \text{compteur}\). Cette quantité est un entier positif (car la boucle s’exécute tant que \(\text{compteur} < b\)) et décroît strictement de 1 à chaque tour. La boucle se termine.

Correction. L’invariant de boucle est : \(\text{resultat} = a \times \text{compteur}\).

• Initialisation. \(\text{resultat} = 0\) et \(\text{compteur} = 0\), donc \(\text{resultat} = a \times 0\). Vérifié.
• Conservation. Si \(\text{resultat} = a \times \text{compteur}\) au début d’un tour, après les affectations on obtient \(\text{resultat} + a = a \times \text{compteur} + a = a \times (\text{compteur} + 1)\). Vérifié.
• Conclusion. En sortie de boucle, \(\text{compteur} = b\) (car la boucle s’arrête quand \(\text{compteur} \geq b\)), donc \(\text{resultat} = a \times b\). L’algorithme est correct.

Exercices

Exercice 1 : trace d’un algorithme

Écrire la trace de l’algorithme de division euclidienne pour \(a = 15\) et \(b = 4\).

Exercice 2 : identifier le variant

Pour chacune des boucles suivantes, proposer un variant de boucle et prouver que la boucle se termine.

a)

def mystere_a(n):
    i = n
    while i > 0:
        i = i - 1
    return i

b)

def mystere_b(n):
    i = 1
    while i < n:
        i = i * 2
    return i

Exercice 3 : exponentiation

Considérons l’algorithme suivant qui calcule \(a^n\) :

def puissance(a, n):
    """Entrée : a un nombre, n un entier naturel
       Sortie : a^n"""
    resultat = 1
    compteur = 0
    while compteur < n:
        resultat = resultat * a
        compteur = compteur + 1
    return resultat

1. Écrire la trace pour \(a = 2\) et \(n = 4\).
2. Proposer un variant de boucle et prouver la terminaison.
3. Proposer un invariant de boucle et prouver la correction.

Exercice 4 : recherche du maximum

def maximum(L):
    """Entrée : L une liste non vide d'entiers
       Sortie : le plus grand élément de L"""
    m = L[0]
    for i in range(1, len(L)):
        if L[i] > m:
            m = L[i]
    return m

1. Proposer un invariant de boucle pour cet algorithme. (Indication : que peut-on dire de m par rapport à L[0], L[1], ..., L[i] ?)
2. En déduire que l’algorithme est correct.

Exercice 5 : algorithme d’Euclide

L’algorithme d’Euclide calcule le PGCD de deux entiers :

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

1. Écrire la trace pour \(a = 48\) et \(b = 18\).
2. Proposer un variant de boucle et prouver la terminaison.
3. Quel est l’invariant de boucle ? (Indication : on pourra montrer que \(\text{pgcd}(a, b)\) ne change pas d’une itération à l’autre.)

Exercice 6 : trouver l’erreur

L’algorithme suivant prétend calculer la somme des entiers de 1 à \(n\). Montrez, en utilisant un invariant de boucle, que cet algorithme est incorrect. Corrigez-le ensuite.

def somme_fausse(n):
    s = 0
    i = 0
    while i < n:
        s = s + i
        i = i + 1
    return s