Théorie des langages : Sujet automate et grammaires
Télécharger PDFAutomates et Grammaires : Fonctions tabulées en bijection
Exercice 1
Un tableau G[0..N−1] permet de représenter une fonction g définie sur [0..N−1]. Il suffit de placer dans la case k du tableau G la valeur de la fonction g en k.
Exemple : Considérons g(k) = (k + 2) mod N. Le tableau G contient les valeurs précalculées de g.
k : 0 1 2 3 4 ... k ... N−2 N−1
G[k] : 2 3 4 5 6 ... g(k) ... 0 1
En pratique, on utilise la technique des fonctions tabulées pour calculer rapidement sin, sin⁻¹, ..., au moyen de tableaux préremplis sin, sin⁻¹, ...
Dans cet exercice, on considère des fonctions g et f de [0..N−1] → [0..N−1], tabulées respectivement dans les tableaux G et F. On aimerait déterminer si g et f forment une bijection, c’est-à-dire si ∀k ∈ [0..N−1], g(f(k)) = k. Avec les versions tabulées G et F des fonctions, cela devient : G et F forment une bijection si ∀k ∈ [0..N−1], G[F[k]] = k.
Q1. Compléter le tableau F pour une bijection
k : 0 1 2 3 4
G[k] : 2 3 4 0 1
F[k] : 3 4 0 1 2
Q2. Automate correspondant au programme
q0 : j := 0 → q1
q1 : j < N → q3
q3 : G[F[j]] ≠ j → q5 (result := false)
q3 : G[F[j]] = j → q4
q4 : j := j + 1 → q1
q2 : j ≥ N → qs (result := true)
Q3. Propriété de correction ψs
ψs : {
result = true ⇒ (∀k ∈ [0..N−1], G[F[k]] = k)
result = false ⇒ (∃k ∈ [0..N−1], G[F[k]] ≠ k)
}
Q4. Preuve de correction
ψ2 : {
j = N ⇒ (∀k ∈ [0..N−1], G[F[k]] = k)
}
ψ1 : {
j ≤ N ∧ (∀k ∈ [0..j−1], G[F[k]] = k)
}
ψ4 : {
j + 1 ≤ N ∧ (∀k ∈ [0..j], G[F[k]] = k)
}
ψ3 : {
0 ≤ j ∧ j + 1 ≤ N ∧ (∀k ∈ [0..j−1], G[F[k]] = k)
}
ψ5 : {
∃k ∈ [0..N−1], G[F[k]] ≠ k
}
Q5. Conditions d’utilisation
Le programme est correct si on l’utilise pour un tableau ayant un nombre de cases N ≥ 0.
Exercice 2 : Preuve de correction partielle de l’algorithme d’exponentiation rapide
Algorithme :
x := A ; y := N ; r := 1 ;
while (y > 0) {
if (y % 2 = 0) { x := x × x ; y := y / 2 ; }
else { r := r × x ; y := y − 1 ; }
}
Q1. Transitions de l’automate
q0 : x ← A ; y ← N ; r ← 1 → q1
q1 : y ≤ 0 → qs
q1 : y > 0 → q2
q2 : y mod 2 ≠ 0 → q4
q2 : y mod 2 = 0 → q3
q3 : x := x × x ; y := y / 2 → q1
q4 : r := r × x ; y := y − 1 → q1
Q2. Exécution de l’automate
a) Pour les valeurs A = 3, N = 3 :
État : q0 → q1 → q2 → q4 → q1 → q2 → q3 → q1 → q2 → q4 → q1 → qs
x : 3 → 3 → 3 → 9 → 9 → 9 → 9 → 9 → 9 → 9 → 9
y : 3 → 3 → 2 → 2 → 1 → 1 → 1 → 0 → 0 → 0 → 0
r : 1 → 1 → 1 → 3 → 3 → 3 → 3 → 3 → 27 → 27 → 27
b) Pour les valeurs A = 2, N = 0 :
État : q0 → q1 → qs
x : 2 → 2
y : 0 → 0
r : 1 → 1
Q3. Propriété de correction ψs
ψs : { r = Aⁿ ∧ y = 0 }
Q4. Preuve de correction partielle
ψ1 : { r × xʸ = Aⁿ ∧ y ≥ 0 }
ψ2 : { r × xʸ = Aⁿ ∧ y ≥ 0 }
ψ4 : { r × x × xʸ = Aⁿ ∧ y ≥ 1 } ≡ { r × xʸ⁺¹ = Aⁿ ∧ y ≥ 1 }
ψ3 : { r × x²ʸ/² = Aⁿ ∧ y ≥ 0 } ≡ { r × xʸ = Aⁿ ∧ y ≥ 0 }
Q5. Conditions d’utilisation
Le programme garantit que r = Aⁿ à la sortie si N ≥ 0.
FAQ
Qu’est-ce qu’une fonction tabulée en bijection ?
Une fonction tabulée en bijection signifie que chaque élément de l’ensemble de départ est associé à un unique élément de l’ensemble d’arrivée, et réciproquement. Dans ce contexte, cela se traduit par G[F[k]] = k pour tout k.
Comment vérifier si deux fonctions tabulées forment une bijection ?
Pour vérifier si deux fonctions tabulées G et F forment une bijection, il suffit de parcourir les indices et de vérifier que pour chaque k, G[F[k]] = k. Si cette condition est remplie pour tous les indices, alors les fonctions sont en bijection.
Quelle est la propriété de correction de l’algorithme d’exponentiation rapide ?
La propriété de correction de l’algorithme d’exponentiation rapide est que, à la sortie, r = Aⁿ et y = 0. Cela garantit que la variable r contient bien la valeur de l’exponentiation.