Un des plus vieux algorithmes connus est décrit par Euclide dans le livre VII de ses éléments. Il permet de calculer le pgcd de deux entiers à l'aide de comparaisons et soustractions.
Voici la version réseau de Petri de cet algorithme :
Pour calculer le pgcd de a et b, placer un jeton tout en bas, a jetons et b jetons dans les places juste au-dessus, puis faire tourner le réseau de Petri. Lorsque le calcul est fini, le jeton unique est revenu en bas, et une des places juste au-dessus est vide. L'autre contient un nombre de jetons égal au pgcd de a et b.
La traduction en C (faisant usage du passage de paramètres par valeur) donne
int pgcd(int a, int b) {
while (b!=a) {
if (b<a) {
a -= b;
}
else {
b -= a;
}
}
return b;
}
Pour garantir la sécurité d'un algorithme, on a besoin de prouver que, quelles que soient les données entrées pour a et b, le calcul du pgcd prend un temps fini, c'est-à-dire que l'algorithme se termine.
Un variant est un élément, dépendant des variables, d'un ensemble bien ordonné, et qui décroît au cours de l'exécution de l'algorithme.
Au cours de l'exécution de l'algorithme, les valeurs prises successivement par le variant forment une chaîne décroissante. L'ordre étant supposé bien fondé, une telle chaîne ne peut être infinie. Donc l'algorithme se termine au bout d'un temps fini.
Pour prouver la terminaison d'un algorithme, il suffit donc
Souvent, on prend un variant dans N dont la relation d'ordre < est bien fondée. Mais l'algorithme d'Euclide porte sur deux entiers x et y. Ceux-ci forment un couple (x,y) et on choisit l'ordre lexicographique sur ces couples d'entiers. Alors
Le couple (x,y) est donc bien un variant. Ce qui prouve la terminaison de l'algorithme d'Euclide.
Le raisonnement ci-dessus ne fonctionne que si x et y sont strictement positifs. L'algorithme s'arrête quand x et y sont égaux et ne va donc pas rendre négatif ou nul une des variables x et y, sauf si elle l'était déjà au départ. Le programme comporte donc un bug : si a ou b est négatif ou nul le programme C ne s'arrête jamais (il « plante » ). La programmation défensive consiste à supposer que l'utilisateur va mal utiliser la fonction (par exemple en fournissant des données inadéquates). On cherche donc à se défendre contre les entiers négatifs ou nul, par exemple avec cette version de la fonction :
int pgcd(int a, int b) {
assert (a>0);
assert (b>0);
int x=a,y=b;
while (y!=x) {
if (y<x) {
x -= y;
} else {
y -= x;
}
}
return y;
}
Un invariant d'un algorithme est une proposition logique dépendant des valeurs des variables. la différence avec un variant est que l'implication ⇒ donne des chaînes croissantes stationnaires (c'est un ordre bien fondé à l'envers).
Le fonctionnement des invariants est similaire à celui des variants.
Pour prouver qu'un algorithme fait bien ce qu'il est censé faire (à condition qu'il termine), on doit donc
Alors cela prouve qu'il est vrai aussi à la fin, et que l'algorithme est correctement partiel.
On propose comme invariant :
le pgcd de x et y est égal au pgcd de a et b.
En effet, à la fin, x==y donc cet
invariant permet de montrer la correction partielle
de l'algorithme d'Euclide. Pour cela on a besoin du
Comme p divise q et q divise p, p=q ce qui démontre le lemme.
En supposant donc ( « hypothèse de récurrence » ) qu'en entrant dans la boucle, x et y sont tels que leur pgcd est celui de a et b,
On a donc bien un invariant. Or il est vrai au début de l'algorithme puisqu'à ce moment, l'invariant s'écrit « le pgcd de a et b est le pgcd de a et b ».
Ceci montre la correction partielle de l'algorithme d'Euclide dans les cas où il termine, c'est sur le pgcd de a et b.
Comme on a montré que l'algorithme d'Euclide (version débuguée) termine, il est correct :
On a vu au I que l'algorithme d'Euclide met un temps fini pour calculer un pgcd, indépendamment des valeurs de a et b. Mais on a souvent besoin d'estimer plus finement ce temps. Il y a plusieurs manières de définir la complexité d'un algorithme.
Il y a deux sortes d'instructions :
while,
de temps indépendant de a et b et supposé négligeable,L'étude de la complexité de l'algorithme d'Euclide
revient donc à compter les passages dans la boucle,
et plus précisément de quelle manière le nombre de
passages dans la boucle dépend de a et b. On peut
déléguer ce travail à C, en modifiant la fonction
pgcd pour qu'au lieu de renvoyer le
pgcd, elle renvoie la valeur d'un compteur p
(comme « pas » ) :
int pgcd(int a, int b) {
int p = 0;
while (b!=a) {
p++;
if (b<a) {
a -= b;
}
else {
b -= a;
}
}
return p;
}
On apprend que le plus petit nombre de passage dans la boucle est 0 : c'est ce qui se passe quand on calcule le pgcd d'un nombre avec lui-même.
La complexité dans le meilleur cas est donc constante O(1).
Le programme C ci-dessus révèle que le pire cas
est celui où on calcule le pgcd de a et 1 : dans
ce cas on soustrait 1, a-1 fois de suite, à x, jusqu'à ce que
x==1.
La complexité dans le pire cas est linéaire O(n).
On peut faire un relevé statistique avec la
fonction pgcd ci-dessus (celle qui
renvoit le compteur p) avec un tableau d'effectif t :
int t [20] = {0};
int i,j;
for (i = 1; i<=20; i++) {
for (j = 1; j<=20; j++) {
t[pgcd(i,j)]++;
}
}
for (i = 0; i<20; i++) {
printf("%d : %d fois\n",i,t[i]);
}
L'affichage produit montre des statisiques intéressantes sur les 400 valeurs examinées de (1,1) à (20,20) dans l'ordre lexicographique :
0 : 20 fois 1 : 20 fois 2 : 24 fois 3 : 36 fois 4 : 40 fois 5 : 52 fois 6 : 64 fois 7 : 48 fois 8 : 32 fois 9 : 16 fois 10 : 12 fois 11 : 4 fois 12 : 4 fois 13 : 4 fois 14 : 4 fois 15 : 4 fois 16 : 4 fois 17 : 4 fois 18 : 4 fois 19 : 4 fois
Pour calculer la complexité de l'algorithme
d'Euclide en moyenne, on calcule une moyenne sur
nmax valeurs :
float temps_moyen(int nmax) {
float n,s;
float t[20];
int i,j;
for (i = 1; i<20; i++) {
t[i] = 0;
}
for (i = 1; i<=nmax; i++) {
for (j = 1; j<=nmax; j++) {
n++;
t[pgcd(i,j)]++;
}
}
s = 0.0;
for (i = 0; i<nmax; i++) {
s += t[i]*i;
}
return s/n;
}
On apprend par exemple que pour calculer le pgcd de deux nombres entre 1 et 20, on boucle en moyenne 5,94 fois. Pour n allant de 1 à 20, le nombre moyen de passages dans la boucle pour 1≤a≤20 et 1≤b≤20 est représenté graphiquement ci-dessous :
Et pour a et b allant jusqu'à 100 :
La complexité en moyenne semble logarithmique.