TD1 : Terminaison et correction des
algorithmes
Pr. ADDOU Mohammed
[Link]@[Link]
Master Intelligence Artificielle et Sciences des Données
Module: Complexité algorithmique et Théorie des graphes
1
Terminaison et correction des algorithmes
Exercice 1
L’algorithme PGCD_brute-force calcule PGCD(m, n), montrer
qu’il est correct :
2
Terminaison et correction des algorithmes
Pour montrer qu’un algorithme est correct, il faut montrer qu’il
termine et qu’il renvoie le résultat attendu.
Terminaison :
Avant et après la boucle "tant que" il y a un
nombre constant d’opérations.
Dans la boucle "tant que" il y a un nombre
constant d’opérations.
La boucle "tant que" s’exécute au plus n fois (si t
= 1 alors m mod t = n mod t = 0)
3
Terminaison et correction des algorithmes
L’algorithme renvoie le résultat attendu pour n’importe quelle donnée :
Le premier “si” est correct (si n = 0 alors le PGCD est 0)
Invariant de boucle : t ≥ P GCD(m, n).
1. Initialisation : le PGCD est plus petit que n, donc correct.
2. Conservation :
On suppose que l’invariant est vrai au début d’une itération, on
montre qu’il est vrai au début de l’opération suivante.
Puisque 𝑡 ≥ 𝑃𝐺𝐶𝐷(𝑚, 𝑛), si 𝑚 𝑚𝑜𝑑 𝑡 ≠ 0 et 𝑛 𝑚𝑜𝑑 𝑡 ≠ 0
alors 𝑡 > 𝑃𝐺𝐶𝐷(𝑚, 𝑛) et donc l’invariant est vrai au début de
l’itération suivante.
3. Terminaison :
La boucle termine si t est un diviseur de m et de n, puisque
𝑡 ≥ 𝑃𝐺𝐶𝐷(𝑚, 𝑛), alors 𝑡 = 𝑃𝐺𝐶𝐷(𝑚, 𝑛) d’où le résultat
4
Terminaison et correction des algorithmes
Exercice 2
1. Montrer que le programme sommer termine quel que soit
l’argument n.
2. Que calcule ce programme ?
3. Prouvez-le !
5
Terminaison et correction des algorithmes
1- Le programme ne contient pas d’appel récursif et une
unique boucle for dont le corps ne modifie ni l’indice de boucle
ni les bornes.
• i est un variant : entier (strictement) plus petit que n et
strictement croissant à chaque nouveau passage dans la
boucle (incrémenté de 1 par le for)
• Si on préfère les variants pris dans (N, <), n − i est un tel
variant.
6
Terminaison et correction des algorithmes
𝑛−1 𝑛 𝑛−1
2- On a 𝑠𝑜𝑚𝑚𝑒𝑟 𝑛 = 0 𝑘 =
2
7
Terminaison et correction des algorithmes
𝑖 𝑖+1
3- On considère l’invarian 𝑠(𝑖) = en fin de la boucle for
2
Au premier passage à la fin de la ligne 4, on a : s = 0 et i = 0 donc
l’invariant est vérifié. Si l’invariant est vérifié en sortie de boucle for, au
passage suivant, on aura effectué :
avant après
i i i+1
s s s+i+1
𝑖 𝑖+1
Donc si 𝑠(𝑖) = , on a bien
2
𝑖 𝑖+1 𝑖+1 𝑖+2
𝑠 𝑖+1 =𝑠 𝑖 +𝑖+1= +𝑖+1=
2 2
et l’invariant est préservé.
Lorsque l’on quitte le programme, on a effectué un dernier passage dans la
boucle for avec i = n − 1, l’invariant lors de cette sortie de boucle nous
𝑛−1 𝑛
donne : 𝑠 𝑛 − 1 = , qui est la valeur retournée par le
8 2
programme.
Terminaison et correction des algorithmes
Exercice 3
Considérons l’algorithme suivant :
Fonction F(n : Entier) : Entier;
Variables
x, y : Entier; 1. Calculer F(0), F(1) et F(2).
Début 2. Que calcule la fonction F(n), pour tout entier n
x := n; ≥0?
y := n; 3. Prouver l’invariant de boucle : 𝑥𝑗 + 2𝑦𝑗 = 3𝑛,
Tant Que (y <> 0) Faire pour tout entier j ≥ 0.
x := x + 2; 4. Donner alors la preuve de l’algorithme F(n).
y := y - 1;
FinTQ
Retourner x;
Fin
9
Terminaison et correction des algorithmes
1- Calculons F(0), F(1) et F(2) :
F(0) = 0
F(1) = 1
F(2) = 6
10
Terminaison et correction des algorithmes
2- Déterminons ce que calcule la fonction 𝐹 𝑛 , pour
tout entier 𝑛 ≥ 0
• Avant la boucle, 𝑥 = 𝑛 et 𝑦 = 𝑛
• La boucle décrémente 𝑦 de 1 et incrémente 𝑥 de 2.
• Il y aura alors 𝑛 itérations.
• La valeur finale de 𝑥 et donc : 𝑛 + 2𝑛 = 3𝑛
• Par suite, 𝐹 𝑛 = 3𝑛, ∀𝑛 ≥ 0
11
Terminaison et correction des algorithmes
3- Prouvons l’invariant de boucle : 𝑥𝑗 + 2𝑦𝑗 = 3𝑛,
pour tout entier 𝑗 ≥ 0.
Commençons par les faits :
𝑥0 = 𝑛 et 𝑦0 = 𝑛
𝑥𝑗+1 = 𝑥𝑗 + 2, ∀𝑗 ≥ 0.
𝑦𝑗+1 = 𝑦𝑗 − 1, ∀𝑗 ≥ 0.
12
Terminaison et correction des algorithmes
Preuve de l’invariant de boucle (Par récurrence sur j).
Base :
pour 𝑗 = 0, on a 𝑥0 + 2𝑦0 = 𝑛 + 2𝑛 = 3𝑛. La
propriété est vérifiée pour 𝑗 = 0.
Induction :
soit 𝑗 ≥ 0 et supposons que 𝑥𝑗 + 2𝑦𝑗 = 3𝑛.
Montrons que 𝑥𝑗+1 + 2𝑦𝑗+1 = 3𝑛. On a :
𝑥𝑗+1 + 2𝑦𝑗+1 = 𝑥𝑗 + 2 + 2 𝑦𝑗 − 1 = 𝑥𝑗 + 2𝑦𝑗 = 3𝑛
13
Terminaison et correction des algorithmes
Donnons alors la preuve de l’algorithme 𝐹(𝑛):
L’algorithme 𝐹(𝑛) se termine, car il efectue 𝑛 itérations et
chaque itération se termine.
Exploitation de l’invariant de boucle :
• 𝑦𝑗 est une suite arithmétique de premier terme 𝑦0 = 𝑛
𝑗≥0
et de raison 𝑟 = −1.
• Donc , 𝑦𝑗 = 𝑦0 + 𝑟 𝑗 − 0 = 𝑛 − 𝑗, ∀𝑗 ≥ 0
• On en déduit que 𝑥𝑗 = 3𝑛 − 2𝑦𝑗 = 𝑛 + 2𝑗
• Comme il y a 𝑛 itérations, la dernière valeur de 𝑗 est 𝑛, et par
suite, 𝑥𝑛 = 𝑛 + 2𝑛 = 3𝑛
• Or, 𝐹 𝑛 = 𝑥𝑛 donc 𝐹 𝑛 = 3𝑛 et l’algorithme est
14
correct.