Théorie des langages : Exercices egalite de tableaux avec sentinelle
Télécharger PDFExercice 1 : Égalité de tableaux avec sentinelle
On peut manipuler un tableau sans en connaître la taille à condition de pouvoir détecter la fin du tableau. Un moyen consiste à mettre une valeur spéciale, appelée sentinelle, dans la case qui suit la dernière case utile du tableau. Il faut choisir une sentinelle différente des valeurs possibles des autres cases du tableau. Dans cet exercice, on considère des tableaux contenant des entiers et on prend la valeur -1 comme sentinelle.
Exemple de tableaux A et B, à sentinelle, égaux :
i : 0 1 2 3 4 5 6 7 8 ...
A[i] : 5 3 4 7 -1 2 1 0 8 ...
B[i] : 5 3 4 7 -1 2 9 ...
Le but de cet exercice est de montrer la correction partielle du programme suivant, censé tester l'égalité de deux tableaux A et B avec sentinelle. Chaque instruction return amène à un état de sortie différent.
Programme :
égalité de tableaux
int i ;
i := 0 ;
while(A[i] == B[i]) {
if (A[i] == -1) { return true; }
i := i + 1 ;
}
return false;
Exercice 2 : Calcul du PGCD de deux entiers
On considère l'algorithme, donné sous forme d'automate, qui calcule le PGCD (« Plus Grand Diviseur Commun ») de deux entiers A et B donnés. À la sortie de l'automate, on obtient a = PGCD(A, B), où PGCD(A, B) représente le résultat mathématique.
Automate de la Figure 1 :
q0 : a ← A ; b ← B q1 : a ≠ b q2 : a ≤ b → b ← b - a q3 : a > b → a ← a - b q4 : a ≠ b q5 : a = b
Programmes proposés :
P1 :
int a, b;
a := A ; b := B ;
while(a ≠ b) {
if (a > b) { a := a - b }
else { b := b - a }
}
P2 :
int a, b;
a := A ; b := B ;
while(a ≠ b) {
while(a ≤ b) { b := b - a }
while(a > b) { a := a - b }
}
P3 :
int a, b;
a := A ; b := B ;
while(a ≠ b) {
if (a ≤ b) { b := b - a }
else { a := a - b }
}
P4 :
int a, b;
a := A ; b := B ;
while(true) {
if(a = b) { break }
if(a ≤ b) { b := b - a }
else { a := a - b }
}
P5 :
int a, b;
a := A ; b := B ;
while(a ≠ b) {
while(a ≤ b) { b := b - a }
while(a > b) { a := a - b }
}
P6 :
int a, b;
a := A ; b := B ;
while(a ≠ b) {
if (a > b) { a := a - b }
if (a ≤ b) { b := b - a }
}
Question : Le(s)quel(s) de ces programmes correspondent à l'automate de la Figure 1 ?
Réponse : P3
Propriétés du PGCD et principe de l'algorithme
On note x | y le fait que x divise y, c'est-à-dire que y est un multiple de x (∃k ∈ ℕ*, y = k × x). Voici quelques propriétés du PGCD utiles pour prouver la correction de l'algorithme :
1) PGCD(x, x) = x
2) p | x ∧ p | y ⇒ p | PGCD(x, y)
3) p | x ∧ p | y ⇒ p | (x - y)
4) p | x ∧ p | y ⇒ p | (x + y)
5) p | q ∧ q | p ⇒ q = p
Ces propriétés permettent de démontrer les égalités suivantes :
(i) PGCD(a, b - a) = PGCD(a, b) si a ≤ b
(ii) PGCD(a - b, b) = PGCD(a, b) si a ≥ b
Preuve de la propriété (i)
Soit p = PGCD(a, b) et q = PGCD(a - b, b).
Puisque p = PGCD(a, b), alors p | a et p | b (d'après la définition du PGCD). Mais alors p | (b - a) (d'après la propriété 3), et donc p | PGCD(a - b, b) (d'après la propriété 2).
Puisque q = PGCD(a - b, b), alors q | (a - b) et q | b (d'après la propriété 2). Mais alors q | a (d'après la propriété 4), et donc q | PGCD(a, b) (d'après la propriété 2).
Conclusion : q = p (d'après la propriété 5), autrement dit PGCD(a - b, b) = PGCD(a, b). On démontre de la même manière que PGCD(a, b - a) = PGCD(a, b).
Preuve de correction partielle de l'algorithme (Figure 1)
Invariant en q1 : PGCD(a, b) = PGCD(A, B).
Initialisation : À l'entrée de l'automate (état q0), on a a = A et b = B, donc l'invariant est trivialement vrai.
Conservation :
1. Si a ≤ b, alors b ← b - a. D'après la propriété (i), PGCD(a, b - a) = PGCD(a, b), donc PGCD(a, b) = PGCD(A, B) reste vrai.
2. Si a > b, alors a ← a - b. D'après la propriété (ii), PGCD(a - b, b) = PGCD(a, b), donc PGCD(a, b) = PGCD(A, B) reste vrai.
Terminaison : La boucle while(a ≠ b) se termine lorsque a = b. À ce moment, d'après la propriété 1, PGCD(a, a) = a, et donc a = PGCD(A, B).
FAQ
1. Pourquoi utilise-t-on une sentinelle dans un tableau ?
Une sentinelle permet de détecter la fin d'un tableau sans connaître sa taille exacte. Elle est une valeur spéciale qui ne peut pas apparaître dans les données valides.
2. Comment choisir une sentinelle adaptée ?
La sentinelle doit être différente de toutes les valeurs possibles dans le tableau. Par exemple, pour des entiers positifs, on peut utiliser -1 comme sentinelle.
3. Quels sont les invariants possibles pour prouver la correction d'un algorithme ?
Un invariant est une propriété qui reste vraie à chaque itération de la boucle. Pour l'algorithme du PGCD, l'invariant typique est PGCD(a, b) = PGCD(A, B).