Les trois questions fondamentales à se poser à propos de tout algorithme sont les suivantes :
Ce chapitre traite des deux premières questions. La complexité fait l’objet d’un chapitre dédié.
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)
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\) :
| Étape | q |
r |
r >= b |
|---|---|---|---|
| Init. | 0 | 22 | Vrai |
| Tour 1 | 1 | 19 | Vrai |
| Tour 2 | 2 | 16 | Vrai |
| Tour 3 | 3 | 13 | Vrai |
| Tour 4 | 4 | 10 | Vrai |
| Tour 5 | 5 | 7 | Vrai |
| Tour 6 | 6 | 4 | Vrai |
| Tour 7 | 7 | 1 | Faux |
À la sortie de la boucle, \(q = 7\) et \(r = 1\). On a bien \(22 = 3 \times 7 + 1\) avec \(0 \leq 1 < 3\).
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 :
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.
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).
La boucle se termine donc nécessairement.
Remarques.
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.for i in range(n) se termine toujours, car le nombre de tours est fixé avant d’entrer dans la boucle. En revanche, une boucle for qui parcourt une liste que l’on allonge dans la boucle peut ne jamais s’arrêter.Un invariant de boucle est une proposition qui :
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.
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\). De plus, \(r = a \geq 0\) car \(a\) est un entier positif. L’invariant est vérifié.
Conservation. Supposons que \(a = b \times q + r\) et \(r \geq 0\) 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.\] De plus, le tour n’a lieu que si \(r \geq b\), donc la nouvelle valeur \(r - b\) est positive ou nulle. 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.
while, en déduire une postcondition, c’est-à-dire une propriété vraie à la sortie de l’algorithme (ici, \(a = bq + r\) avec \(0 \leq r < b\)).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}\).
Écrire la trace de l’algorithme de division euclidienne pour \(a = 15\) et \(b = 4\).
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
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
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
m par rapport à L[0], L[1], ..., L[i] ?)L’algorithme d’Euclide calcule le PGCD (plus grand commun diviseur) de deux entiers naturels :
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
a % b ; on pourra en déduire que \(\text{pgcd}(a, b)\) ne change pas d’une itération à l’autre.)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