Théorie des langages : Exercices info3 a&g ds
Télécharger PDF② YRfRfeyY② INFO3 - A&G - DS0 12 34 56 78 90 12 34 56 78 90 12 34 56 78 90 12 34 56 78 90 12 34 56 78 90 12 34 56 78 90 12 34 56 78 90 12 34 56 78 9
←−N’oubliez pas d’indiquer votre
numéro d’étudiant en grisant les cases
du tableau.
Donnez aussi votre numéro
d’étudiant au format standard
.................................
*QMbB;M2b
ěhQmb H2b TT `2BHb ûH2+i`QMB[m2b bQMi BMi2`/Bib ̈ HǶ2t+2TiBQM /2b KQMi`2bX
ěG2 bmD2i +QKTQ`i2 j 2t2`+B+2b BM/ûT2M/ MibX
ě:`Bb2x H2b + b2b /2b #QMM2b `ûTQMb2bX lM + b2 K H ;`Bbû2 2bi +QMbB/û`û2 +QKK2!XliBHBb2x mM2 2M+`2 7QM+û2c
T b /2 +` vQM ̈ T TB2` Qm HQ`b `2T bb2x pQb `ûTQMb2b ̈ HǶ2M+`2 p Mi /2 `2M/`2 pQi`2 +QTB2X
ěG2b [m2biBQMb♣T2mp2Mi pQB`THmbB2m`b T`QTQbBiBQMb +Q``2+i2bX
ělM2 K mp Bb2 `ûTQMb2 7 Bi T2`/`2 /2b TQBMibX
ěGǶ #b2M+2 /2 `ûTQMb2 p mi y TQBMiX
1 Le décalage à droite est la multi-
plication par 2 en binaire
࠭estion 1♣En notationliࡉle-endian, à quel en-
tier correspond le tableau ci-aprèsk01234 U[k]RyRRR28 1×2+1×4+1×8+1×1629 301×2 0+0×2 1+1×2 2+1×2 3+1×2 4
aucunedesréponsesproposéesn’estcorrecte
࠭estion 2Quel est le programme correspondant
à l’automate?BDCA ࠭estion 3Pour permettre de traiter facilement
l’effet de l’affectationD[0]:=0surψs , choississez une
version équivalente au terme∑ ℓ=Nℓ=0 D[ℓ]×2ℓ deψs D[0]×20 +∑ ℓ=Nℓ=1 D[ℓ]×2ℓ D[0]×2+∑ ℓ=Nℓ=1 D[ℓ]×2ℓ ∑ℓ=N ℓ=1
D[0] +D[ℓ]×2ℓ ∑ℓ=N ℓ=1D[ℓ]×2 ℓ
࠭estion 4Rédigez la preuve associée à la transi-tionq 5→q s
sur votre copie.
réservé au correcteur
࠭estion 5Quelle propriété avez-vous choisi pourψ 2? (ℓ=N ∑ℓ=1 D[ℓ]×2ℓ )? =2×( k=N∑ k=0U[k]×2 k) (ℓ=N ∑ℓ=i+1 D[ℓ]×2ℓ )? =2×( k=N∑ k=0U[k]×2 k) (ℓ=N ∑ℓ=i D[ℓ]×2ℓ )? =2×( k=N∑ k=iU[k]×2 k) (ℓ=N ∑ℓ=i+1 D[ℓ]×2ℓ )? =2×( k=N∑ k=iU[k]×2 k) ࠭estion 6Quelle est la transition qui correspond
à l’étape de vérification?②② ②
YRfkf8NY② q0 →q1 q1 →q2 q2 →q3 q2 →q5 ࠭estion 7Rédigez la preuve associée à la transi-tionq 1→q 2
sur votre copie.
réservé au correcteur
࠭estion 8La transitionq0 →q1 est
une transition affectation
une transition test
࠭estion 9De quelle forme est la preuve associée
à la transitionq0 →q1 ψ0 ∧U[N]=0=⇒ψ1 ψ0 ≡ψ1 [U[N]←0]ψ 1≡ψ 0
[U[N]←0]ψ 0=⇒ψ 1∧U[N]=0 ψ1 ∧U[N]=0=⇒ψ0 ࠭estion10Enfaisantlapreuvedecorrectionpar-
tielle, quelles conditions d’utilisation obtient-on?U[N]=2 N+1aucune U[N]=0U[N]̸=0 N≥0
N+1>N
࠭estion 11♣Pourquoi l’algorithme commence
t’il par vérifier queU[N]=0?
sinon l’indiceisortirait du tableauD
pour vérifier les conditions d’utilisation
sinon il bouclerait
sinonladernièrecasedutableauDcontiendrait
un 2
sinon le tableauDne peut pas représenter le
double deU
sinon le résultat ne pourrait pas être correct
aucunedesréponsesproposéesn’estcorrecte
2 Multiplication Rapide
࠭estion 12Exécutez l’algorithme mॺ avecA=
3.2etB=5; que valentx, y, r, ien sortie?
x=3.2,y=0,r= 16,i=1
x=3.2,y=0,r= 16,i=3
x= 16.0,y=0,r= 16,i=4
x= 12.8,y=0,r= 16,i=2
࠭estion 13♣Que calcule la variablei?
la somme des parités cumulatives dey
le quotient deypar 2
le nombre de réduction par 2 du problème
le logarithme (entier) en base 2 dey
le nombre d’itération de la boucle
aucunedesréponsesproposéesn’estcorrecte
࠭estion 14♣ PrenonsB =2i . Par rapport à l’al-
gorithme naif qui ferait2i additions, l’algorithme mॺ
en fait (en ordre de grandeur)iB 2log 2(B) √B B2 aucunedesréponsesproposéesn’estcorrecte
࠭estion 15Lequel des automates correspond à
l’algorithme mॺ?♠♦♣♥ ࠭estion 16♣Enq0 , que peut-on dire des va-
riables?x=? elles ont une valeur non nuller=i y=0
elles n’ont pas de valeurx=A y=B
aucunedesréponsesproposéesn’estcorrecte
࠭estion 17Dans quel ordre doit-on étudier les
transitions pour faire une preuve complète de correc-
tion partielle?q 1→q s;q 4→q 1;q 2→q 4;q 3→q 1;q 2→q 3; q1 →q2 ;q0 →q1 q1 →qs ;q3 →q1 ;q4 →q1 ;q2 →q4 ;q2 →q3 ;q 0→q 1q 0→q 1;q 1→q 2;q 2→q 3;q 2→q 4;q 3→q 1; q4 →q1 ;q1 →qs q1 →qs ;q4 →q1 ;q2 →q4 ;q1 →q2 ;q0 →q1 ࠭estion 18♣Donnez la propriété de correction
en sortie de programmer=x×y r=A×yy=0 r=x×By=2 ix×y=A×B r=A×B②② ②
YRfjf83Y② aucunedesréponsesproposéesn’estcorrecte
࠭estion19♣Rédigezlapreuveassociéeàlatran-sitionq 1→q s
sur votre copie.
réservé au correcteur
࠭estion 20♣Donnez l’invariantψ1 enq1 x=Ay=0 r+x×yy≥0 r+ x× y= A× B
r+(x−i)×(y+i)=A×B
r×x+y=A+Br=x+2×y aucunedesréponsesproposéesn’estcorrecte
࠭estion21Dequelleformeestlapreuveassociée
à la transitionq4 →q1 ?ψ 4≡ψ 1
[r←r+x;y←y−1]ψ 4=⇒ψ 1
∧r=r+x∧y=y+1ψ 1≡ψ 4
[r←r+x;y←y−1]ψ 4
∧r=r+x∧y=y+1=⇒ψ1 ࠭estion 22Rédigez la preuve associée à la tran-sitionq 3→q 1
sur votre copie.
réservé au correcteur
࠭estion 23Pourquoi la variablein’apparaît-elle
pas dans l’invariantψ3 associé àq3 ?
parce qu’elle n’apparaît que dans une branche
du ”i”
parce qu’elle disparaît quand on fait l’affecta-
tioni:=i+1
parce qu’elle n’a pas d’effet sur le calcul du ré-sutlatr parcequ’ellesertpourlapreuvedeterminaison
࠭estion 24♣En faisant la preuve de correction
partielle quelles conditions d’utilisation obtient-on?B̸=0 x, r∈7HQ i
A>0B∈BMi B≥0A∈BMi aucunedesréponsesproposéesn’estcorrecte
࠭estion 25Que se passe-t’il si on exécute l’algo-
rithme mॺ avecA=0?
l’algorithme boucle
l’algorithme termine mais le résultat est incor-rect l’algorithme termine et le résultat est correct
l’algorithme peut ne pas terminer, cela dépenddeB ࠭estion 26Que se passe-t’il si on exécute l’algo-
rithme mॺ avecB=0?
l’algorithme boucle
l’algorithme termine et le résultat est correct
l’algorithme termine mais le résultat est incor-rect l’algorithme peut ne pas terminer, cela dépenddeA 3 Preuve de correction partielle
࠭estion 27♣À quoi sert l’étape de vérification?
à s’assurer qu’on sort de la boucle
à s’assurer qu’on ne peut pas revenir en arrière
dans la boucle
à s’assurer que les propriétés choisies sont des
invariants
à garantir la terminaison de la boucle
à s’assurer que le long de la boucle chaque pro-
priété implique la suivante
àgarantirquelespropriétéssontvraiesdèsl’en-
trée dans la boucle
àgarantirquelesinvariantssonttousdifférents
aucunedesréponsesproposéesn’estcorrecte
࠭estion 28♣Une preuve de correction partielle
ne prouve pas que le programme termine
est invalide si le programme ne termine pas
peut-être valide même si le programme ne ter-
mine pas
prouve que les propriétés associées aux états
sont des invariants
prouve que les conditions d’utilisation sont sa-
tisfaites
aucunedesréponsesproposéesn’estcorrecte
࠭estion 29♣Obtenir{0≥1,A=A}comme
conditions d’utilisation signifie que
l’algorithmetermineetrendlerésultatsouhaité
l’algorithme est correct (correction partielle)
car une des conditions est satisfaite
l’algorithme doit commencer par tester siA=A ②②② YRf9f8dY② l’algorithme n’est pas utilisable
l’algorithme est correct (correction partielle)
sans condition sur ses paramètres
si on atteint l’état de sortie le résultat sera cor-rect l’algorithme est correct (correction partielle)
car toutes les conditions sont satisfaites
aucunedesréponsesproposéesn’estcorrecte
࠭estion 30♣«la propriétéψest un invariant de
l’étatq» signifie
ensortiedeprogrammelapropriétéψestvalide
à chaque exécution du programmeqla pro-
priétéψest satisfaite
l’exécution passe par l’étatqquand la propriété
ψest vraie
les variables du programme satisfont la pro-priétéψ les valeurs des variables à l’étatqsatisfont la
propriétéψ
à chaque fois que l’exécution atteint l’étatqla
propriétéψest valide
aucunedesréponsesproposéesn’estcorrecte
࠭estion31♣Laméthodedepreuvedecorrection
partielle de programme est l’oeuvre de
Alan Mathison Tॽॺing
Stephen Cole Kleene
John ॾon Neॽmann
Donald Ervin Knॽॼh
Charles Antony Richard Hoaॺe
Robert William Floঁd
Edsger Wybe Dijkॻॼॺa
aucunedesréponsesproposéesn’estcorrecte
࠭estion32♣Obtenir{}commeconditionsd’uti-
lisation signifie
l’algorithme est correct (correction partielle)
sans condition sur ses paramètres
l’algorithmedoitcommenceravecunemémoirevide si on atteint l’état de sortie le résultat sera cor-rect l’algorithme est correct (correction partielle)
car toutes les conditions sont satisfaites
l’algorithme est correct (correction partielle)
car une des conditions est satisfaite
l’algorithmetermineetrendlerésultatsouhaité
l’algorithme n’est pas utilisable
aucunedesréponsesproposéesn’estcorrecte
②②