Théorie des langages : Exercices egalite de tableaux avec sentinelle
Télécharger PDFÉ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.1 Un moyen consiste à mettre une valeur spéciale, appeléesentinelle, 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 dansNet on prend
la valeur-1comme sentinelle.
Exemple de tableauxAetB, à sentinelle, égaux:
i012345678. . .
A[i]5347-12108. . .
B[i]5347-129. . .
Le but de cet exercice est de montrer la correction partielle du programme suivant, censé tester l’égalité
de 2 tableauxAetBavec sentinelle. Dans cet exercice on considèrera que chaque instructionreturn
ne fait pas d’affectation mais amène à un état de sortie différent. On obtient un automate à 6 états(deq 0àq 5
) avec deux états de sortieq4 etq5 .
égalité de tableaux
int i ;
i:=0 ;
while(A[i]==B[i]){
if (A[i]==-1){ return true;} i := i+1 ;} return false;
1. C’est ainsi que sont implantées les chaînes de caractères avec pour sentinelle le caractère’\0’.
Exercice 2Calcul du pgcd de deux entiers
On considère l’algorithme, donné sous forme d’automate, qui caclule lepgcd(« Plus Grand Diviseur
Commun ») de deux entiersAetBdonnés. On prétend qu’à la sortie de l’automate on aura «a=
pgcd(A, B)» oùpgcd(A, B)représente le résultat mathématique qu’on essaie de calculer.// q0 a←A;b←B// q1 a? =b// a6=b qs q3 b←b−a88 q2 a≤bhh a>b66 q4 a←a−bff Figure1 – Algorithme dupgcdsous forme d’automateP1 int a,b;
a:=A ; b:=B ;
while(a6=b){
if (a>b){ a:=a-b } else { b:=b-a }} P6
int a,b;
a:=A ; b:=B ;
while(true){
if(a=b){ break }
if(a≤b){ b:=b-a } else { a:=a-b }} P4
int a,b;
a:=A ; b:=B ;
while(a6=b){
if(a≤b){ b:=b-a }
if(a>b){ a:=a-b }} P5
int a,b;
a:=A ; b:=B ;
while(a6=b){
while(a≤b){ b:=b-a }
while(a>b){ a:=a-b }} P2
int a,b;
a:=A ; b:=B ;
while(a6=b){
if (a≤b){ b:=b-a } else { a:=a-b }} P3
int a,b;
a:=A ; b:=B ;
if(a6=b){
if (a≤b){ b:=b-a } else { a:=a-b }} Figure2 – Le(s)quel(s) de ces programmes correspondent à l’automate de la Figure 1 ?
Propriétés du pgcd et principe de l’algorithmeOn notex|yle fait quexdivisey, c’est-à-dire
queyest un multiple dex, soit encore∃k∈N∗ , y=k×x. On rappelle quelques propriétés dupgcd
qui seront utiles pour prouver la correction de ce programme.
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 deux égalités suivantes
(i)pgcd(a, b−a) =pgcd(a, b)sia≤b
(ii)pgcd(a−b, b) =pgcd(a, b)sia≥b
sur lesquelles repose l’algorithme.
Question :Complétez la preuve de(i)sur le QCM.
solutionSoitp def
=pgcd(a, b)etqdef =pgcd(a−b, b).
Puisquep=pgcd(a, b)alorsp|aet........et doncp|................(d’après...) mais alorsp|pgcd(................,...)
(d’après...) et doncp|...(par définition de...).
Puisqueqdef =pgcd(a−b, b)alorsq|................etq|bet doncq|a(d’après...) mais alorsq|pgcd(..........)
(d’après...) et doncq|...(par définition de...).
Conclusion :q=p(d’après...), autrement ditpgcd(......................) =pgcd(..........). On démontre
de la même manière quepgcd(a, b−a) =pgcd(a, b).
Question : Faîtes au brouillonla preuve de correction partielle de l’algorithme de l’automate de
la Figure 1 en suivant la méthode de Floyd-Dijkstra-Hoare afin de montrer qu’à la sortie du programme
«a=pgcd(A, B)».Ensuite répondez aux questions du QCM.
Indication :Vous prendrez pour invariant enq1 une propriété de la forme :pgcd(a, b) =pgcd(A, B)