Centrale Option Informatique MP 2017Sujet, corrigé et rapport du jury

Mots synchronisants

Pas encore noté

Explorer les annales

BanqueCentrale Année2017 FilièreMP MatièreInformatique

Annales Centrale MP Informatique Centrale MP 2017 MP Informatique Informatique 2017

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Mots synchronisants

Notations

Pour tout ensemble fini $E$ , on note $|E|$ son cardinal.
On appelle machine tout triplet ( $Q, Σ, δ$ ) où $Q$ est un ensemble fini non vide dont les éléments sont appelés états, $Σ$ un ensemble fini non vide appelé alphabet dont les éléments sont appelés lettres et $δ$ une application de $Q \times Σ$ dans $Q$ appelée fonction de transition. Une machine correspond donc à un automate déterministe complet sans notion d'état initial ou d'états finaux.
Pour un état $q$ et une lettre $x$ , on note $q \cdot x = δ(q, x)$ .
L'ensemble des mots (c'est-à-dire des concaténations de lettres) sur l'alphabet $Σ$ est noté $Σ^*$ .
Le mot vide est noté $ε$ .
On note $ux$ le mot obtenu par la concaténation du mot $u$ et de la lettre $x$ .
On note $δ^*$ l'extension à $Q \times Σ^*$ de la fonction de transition $δ$ définie par

{∀q ∈ Q, δ^∗(q, ε) = q; ∀(q, x, u) ∈ Q × Σ × Σ^∗, δ^∗(q, xu) = δ^∗(δ(q, x), u)

Pour un état $q$ de $Q$ et un mot $m$ de $Σ^*$ , on note encore $q.m$ pour désigner $δ^*(q, m)$ .

Pour deux états

q

q^', q^'

est dit accessible depuis

q

s'il existe un mot

u

tel que

q^' = q \cdot u

.
On dit qu'un mot

m

Σ^*

est synchronisant pour une machine (

Q, Σ, δ

) s'il existe un état

q_0

Q

tel que pour tout état

q

Q, q.m = q_0

.
L'existence de tels mots dans certaines machines est utile car elle permet de ramener une machine dans un état particulier connu en lisant un mot donné (donc en pratique de la « réinitialiser » par une succession précise d'ordres passés à la machine réelle).
La partie I de ce problème étudie quelques considérations générales sur les mots synchronisants, la partie II est consacrée à des problèmes algorithmiques classiques, la partie III relie le problème de la satisfiabilité d'une formule logique à celui de la recherche d'un mot synchronisant de longueur donnée dans une certaine machine et enfin la partie IV s'intéresse à l'étude de l'existence d'un mot synchronisant pour une machine donnée. Les parties I, II et III peuvent être traitées indépendamment. La partie IV, plus technique, utilise la partie II.
Dans les exemples concrets de machines donnés plus loin, l'ensemble d'états peut être quelconque, de même que l'alphabet (

Σ = {0, 1}, {a, b, c}\dots

). Par contre, pour la modélisation en Caml, l'alphabet

Σ

sera toujours considéré comme étant un intervalle d'entiers

[ [0, p - 1] ]

où

p = |Σ|

. Une lettre correspondra donc à un entier entre 0 et

p - 1

. Un mot de

Σ^*

sera représenté par une liste de lettres (donc d'entiers).

type lettre == int;;
type mot == lettre list;;

De même, en Caml, l'ensemble d'états

Q

d'une machine sera toujours considéré comme étant l'intervalle d'entiers

[ [0, n - 1] ]

où

n = |Q|

type etat == int;;

Ainsi, la fonction de transition

δ

d'une machine sera modélisée par une fonction Caml de signature etat

- >

lettre

- >

etat. On introduit alors le type machine

type machine = { n_etats : int ; n_lettres : int ; delta : etat -> lettre -> etat} ; ;

n_etats correspond au cardinal de

Q

, n_lettres à celui de

Σ

et delta à la fonction de transition. Pour une machine nommée M , les syntaxes M.n_etats, M.n_lettres ou M.delta permettent d'accéder à ses différents paramètres. Dans le problème, on suppose que M. delta s'exécute toujours en temps constant.
Par exemple, on peut créer une machine MO à trois états sur un alphabet à deux lettres ayant comme fonction de transition la fonction

f0

donnée ci-après.

let fO etat lettre = match etat,lettre with
| 0,0 -> 1
| 0,1 -> 1
| 1,0 -> 0
| 1,1 -> 2
| 2,0 -> 0
| 2,1 -> 2;;
fO : int -> int -> int = <fun>
let MO = { n_etats = 3 ; n_lettres = 2 ; delta = f0 };;

La figure 1 fournit une représentation de la machine

M_0

Figure 1 La machine

M_0

On pourra observer que les mots 11 et 10 sont tous les deux synchronisants pour la machine

M_0

.
Dans tout le sujet, si une question demande la complexité d'un programme ou d'un algorithme, on attend une complexité temporelle exprimée en

O(\dots)

I Considérations générales

A

- Que dire de l'ensemble des mots synchronisants pour une machine ayant un seul état ?

Dans toute la suite du problème, on supposera que les machines ont au moins deux états.

I.B

- On considère la machine

M_1

représentée figure 2. Donner un mot synchronisant pour

M_1

s'il en existe un. Justifier la réponse.

Figure 2 La machine

M_1

I.C

- On considère la machine

M_2

représentée figure 3. Donner un mot synchronisant de trois lettres pour

M_2

. On ne demande pas de justifier sa réponse.

I.D

- Écrire une fonction delta_etoile de signature machine

\to

etat

\to

mot

\to

etat qui, prenant en entrée une machine

M

, un état

q

et un mot

u

, renvoie l'état atteint par la machine

M

en partant de l'état

q

et en lisant le mot

u

.
I.E - Écrire une fonction est_synchronisant de signature machine

\to

mot

\to

bool qui, prenant en entrée une machine

M

et un mot

u

, dit si le mot

u

est synchronisant pour

M

.
I.F - Montrer que pour qu'une machine ait un mot synchronisant, il faut qu'il existe une lettre

x

et deux états distincts de

Q, q

q^'

, tels que

q \cdot x = q^' \cdot x

.
I.

G

- Soit

LS(M)

le langage des mots synchronisants d'une machine

M = (Q, Σ, δ)

. On introduit la machine des parties

Mˆ = (Qˆ, Σ, δˆ)

où

Qˆ

est l'ensemble des parties de

Q

et où

δˆ

est définie par

∀P ⊂ Q, ∀x ∈ Σ, δ^(P, x) = {δ(p, x), p ∈ P}

I.G.1) Justifier que l'existence d'un mot synchronisant pour

M

se ramène à un problème d'accessibilité de certain(s) états(s) depuis certain(s) état(s) dans la machine des parties.
I.G.2) En déduire que le langage

LS(M)

des mots synchronisants de la machine

M

est reconnaissable.

Figure

3M_2

: une machine à 4 états

I.G.3) Déterminer la machine des parties associée à la machine

M_0

puis donner une expression régulière du langage

LS(M_0)

.
I.H - Montrer que si l'on sait résoudre le problème de l'existence d'un mot synchronisant, on sait dire, pour une machine

M

et un état

q_0

M

choisi, s'il existe un mot

u

tel que pour tout état

q

Q

, le chemin menant de

q

q \cdot u

passe forcément par

q_0

II Algorithmes classiques

On appellera graphe d'automate tout couple (

S, A

) où

S

est un ensemble dont les éléments sont appelés sommets et

A

une partie de

S \times Σ \times S

dont les éléments sont appelés arcs. Pour un arc (

q, x, q^'

x

est l'étiquette de l'arc,

q

son origine et

q^'

son extrémité. Un graphe d'automate correspond donc à un automate non déterministe sans notion d'état initial ou d'état final.
Par exemple, avec

Σ =, {a, b}; S_0 =, {0, 1, 2, 3, 4, 5}; A_0 =, {(0, b, 0), (0, a, 3), (0, b, 2), (0, a, 1), (1, a, 1), (1, a, 2), (2, b, 1),; (2, b, 3), (2, b, 4), (3, a, 2), (4, a, 1), (4, b, 5), (5, a, 1)}

le graphe d'automate

G_0 = (S_0, A_0)

est représenté figure 4 .
Soient

s

s^'

deux sommets d'un graphe (

S, A

). On appelle chemin de

s

vers

s^'

de longueur

ℓ

toute suite d'arcs

(s_1, x_1, s_1^'), (s_2, x_2, s_2^'), \dots, (s_ℓ, x_ℓ, s_ℓ^')

A

telle que

s_1 = s, s_ℓ^' = s^'

et pour tout

i

[ [1, ℓ - 1] ], s_i^' = s_(i + 1)

. L'étiquette de ce chemin est alors le mot

x_1 x_2\dotsx_ℓ

et on dit que

s^'

est accessible depuis

s

. En particulier, pour tout

s \in S, s

est accessible depuis

s

par le chemin vide d'étiquette

ε

Figure 4 Le graphe d'automate

G_0

Dans les programmes à écrire, un graphe aura toujours pour ensemble de sommets un intervalle d'entiers

[ [0, n - 1] ]

et l'ensemble des arcs étiquetés par

Σ

(comme précédemment supposé être un intervalle

[ [0, p - 1] ]

) sera codé par un vecteur de listes d'adjacence

V :

pour tout

s \in S, V.(s)

est la liste (dans n'importe quel ordre) de tous les couples

(s^', x)

tel que

(s, x, s^')

soit un arc du graphe. Pour des raisons de compatibilité ultérieure, les sommets (qui sont, rappelons-le, des entiers) seront codés par le type etat.
Ainsi, avec l'alphabet

Σ = {a, b}

, la lettre

a

est codée 0 et la lettre

b

est codée 1 ; l'ensemble des arcs du graphe

G_0

, dont chaque sommet est codé par son numéro, admet pour représentation Caml :

V0 : (etat * lettre) list vect = [|
    [(0,1) ; (3,0) ; (2,1) ; (1,0)] ;
    [(1,0) ; (2,0)] ;
    [(1,1); (3,1); (4,1)];
    [(2,0)] ;
    [(1,0) ; (5,1)] ;
    [(1,0)]
|]

II.A - On veut implémenter une file d'attente à l'aide d'un vecteur circulaire. On définit pour cela un type particulier nommé file par
type 'a file={tab:'a vect; mutable deb: int; mutable fin: int; mutable vide: bool}
deb indique l'indice du premier élément dans la file et fin l'indice qui suit celui du dernier élément de la file, vide indiquant si la file est vide. Les éléments sont rangés depuis la case deb jusqu'à la case précédent fin en repartant à la case 0 quand on arrive au bout du vecteur (cf exemple). Ainsi, on peut très bien avoir l'indice fin plus petit que l'indice deb. Par exemple, la file figure 5 contient les éléments

4, 0, 1, 12

et 8 , dans cet ordre, avec

fin = 2

et deb

= 9

Figure 5 Un exemple de file où fin < deb

On rappelle qu'un champ mutable peut voir sa valeur modifiée. Par exemple, la syntaxe f .deb <- 0 affecte la valeur 0 au champ deb de la file

f

.
II.A.1) Écrire une fonction ajoute de signature 'a file

\to

a \to

unit telle que ajoute

f \times

ajoute

x

à la fin de la file d'attente

f

. Si c'est impossible, la fonction devra renvoyer un message d'erreur, en utilisant l'instruction failwith "File pleine".
II.A.2) Écrire une fonction retire de signature 'a file

\to

'a telle que retire

f

retire l'élément en tête de la file d'attente et le renvoie. Si c'est impossible, la fonction devra renvoyer un message d'erreur.
II.A.3) Quelle est la complexité de ces fonctions ?

On considère l'algorithme 1 s'appliquant à un graphe d'automate

G = (S, A)

et à un ensemble de sommets

E

(on note

n = |S|

\infty

, vide et rien des valeurs particulières).
II.B - Justifier que l'algorithme 1 termine toujours.
II.

C

- Donner la complexité de cet algorithme en fonction de

|S|

|A|

. On justifiera sa réponse.
II.D - Justifier qu'au début de chaque passage dans la boucle «tant que

F

n'est pas vide», si

F

contient dans l'ordre les sommets

s_1, s_2, \dots, s_r

, alors

D[s_1] ⩽ D[s_2] ⩽ \dots ⩽ D[s_r]

D[s_r] - D[s_1] ⩽ 1

.
II.E - Pour

s

sommet de

G

, on note

d_s

la distance de

E

s

c'est-à-dire la longueur d'un plus court chemin d'un sommet de

E

s

(avec la convention

d_s = \infty

s'il n'existe pas de tel chemin).
II.E.1) Justifier brièvement qu'à la fin de l'algorithme, pour tout sommet

s, D[s] \neq \infty

si et seulement si

s

est accessible depuis un sommet de

E

et que

d_s ⩽ D[s]

. Que désigne alors

c

?
II.E.2) Montrer qu'en fait, à la fin, on a pour tout sommet

s, D[s] = d_s

. Que vaut alors

P[s]

?
II.F - Écrire une fonction accessibles de signature

((etat*lettre) list) vect -> etat list -> int * int vect * (etat*lettre) vect

prenant en entrée un graphe d'automate (sous la forme de son vecteur de listes d'adjacence V) et un ensemble E de sommets (sous la forme d'une liste d'états) et qui renvoie le triplet (

c, D, P

) calculé selon l'algorithme précédent. Les constantes

\infty

, vide et rien seront respectivement codées dans la fonction accessibles par -1 ,

(- 2, - 1)

(- 1, - 1)

créer une file d'attente $F$, vide au départ
créer un tableau $D$ dont les cases sont indexées par $S$ et initialisées à $\infty$
créer un tableau $P$ dont les cases sont indexées par $S$ et initialisées à vide
créer une variable $c$ initialisée à $n$
pour tout $s \in E$ faire
    insérer $s$ à la fin de la file d'attente $F$
    fixer $D[s]$ à 0
    fixer $P[s]$ à rien
    diminuer $c$ de 1
fin pour
tant que $F$ n'est pas vide faire
    extraire le sommet $s$ qui est en tête de $F$
    pour tout arc $\left(s, y, s^{\prime}\right) \in A$ tel que $D\left[s^{\prime}\right]=\infty$ faire
        fixer $D\left[s^{\prime}\right]$ à $D[s]+1$
        fixer $P\left[s^{\prime}\right]$ à $(s, y)$
        insérer $s^{\prime}$ à la fin de la file d'attente $F$
        diminuer $c$ de 1
    fin pour
fin tant que
renvoyer ( $c, D, P$ )

Algorithme 1

II.G - Écrire une fonction chemin de signature etat

\to

(etat*lettre) vect

\to

mot qui, prenant en entrée un sommet s et le vecteur P calculé à l'aide de la fonction accessibles sur un graphe

G

et un ensemble

E

, renvoie un mot de longueur minimale qui est l'étiquette d'un chemin d'un sommet de

E

s

(ou un message d'erreur s'il n'en existe pas).

III Réduction SAT

On s'intéresse dans cette partie à la satisfiabilité d'une formule logique portant sur des variables propositionnelles

x_1, \dots, x_m

. On note classiquement

\land

le connecteur logique « et »,

\lor

le connecteur «ou» et

f¯

la négation d'une formule

f

.
On appelle littéral une formule constituée d'une variable

x_i

ou de sa négation

x¯_i

, on appelle clause une disjonction de littéraux.
Considérons une formule logique sous forme normale conjonctive c'est-à-dire sous la forme d'une conjonction de clauses. Par exemple,

F_1 = (x_1 \lor x¯_2 \lor x_3) \land (x¯_1 \lor x¯_4) \land (x_2 \lor x¯_3 \lor x_4)

est une formule sous forme normale conjonctive formée de trois clauses et portant sur quatre variables propositionnelles

x_1, x_2, x_3

x_4

.
Soit

F

une formule sous forme normale conjonctive, composée de

n

clauses et faisant intervenir

m

variables. On suppose les clauses numérotées

c_1, c_2, \dots, c_n

. On veut ramener le problème de la satisfiabilité d'une telle formule au problème de la recherche d'un mot synchronisant de longueur inférieure ou égale à

m

sur une certaine machine. On introduit pour cela la machine suivante associée à

F

$Q$ est formé de $mn + n + 1$ états, un état particulier noté $f$ et $n(m + 1)$ autres états qu'on notera $q_(i, j)$ avec $(i, j) \in [ [1, n] ] \times [ [1, m + 1] ];$
$- Σ = {0, 1}$ ;
$δ$ est défini par
$f$ est un état puits, c'est-à-dire $δ(f, 0) = δ(f, 1) = f$ ,
pour tout entier $i$ de $[ [1, n] ], δ(q_(i, m + 1), 0) = δ(q_(i, m + 1), 1) = f$ ,
pour tout $i$ dans $[ [1, n] ]$ et $j$ dans $[ [1, m] ]$ ,

éîéîδ(q_(i, j), 1) = {f, si le littéral x_j apparaît dans la clause c_i; q_(i, j + 1), sinon; δ(q_(i, j), 0) = {f, si le littéral x¯_j apparaît dans la clause c_i; q_(i, j + 1), sinon

III.

A

- Représenter la machine associée à la formule

F_1

.
III.

B

- Donner une distribution de vérité

(v_1, v_2, v_3, v_4) \in [ [0, 1] ]^4

(la valeur

v_i

étant associée à la variable

x_i

) satisfaisant

F_1

. Le mot

v_1 v_2 v_3 v_4

est-il synchronisant?
III.

C

- Montrer que tout mot

u

de longueur

m + 1

est synchronisant. À quelle condition sur les

q_(i, 1) \cdot u

un mot

u

de longueur

m

est-il synchronisant ?
III.

D

- Montrer que si la formule

F

est satisfiable, toute distribution de vérité la satisfaisant donne un mot synchronisant de longueur

m

pour l'automate.
III.

E

- Inversement, prouver que si l'automate dispose d'un mot synchronisant de longueur inférieure ou égale à

m, F

est satisfiable. Donner alors une distribution de vérité convenable.

IV Existence

On reprend dans cette partie le problème de l'existence d'un mot synchronisant pour une machine

M

.
IV.A - Soit

M = (Q, Σ, δ)

une machine.

Pour toute partie

E

Q

et tout mot

u

Σ^*

, on note

E.u = {q.u, q \in E}

.
IV.A.1) Soit

u

un mot synchronisant de

M

u_0, u_1, \dots, u_r

une suite de préfixes de

u

rangés dans l'ordre croissant de leur longueur et telle que

u_r = u

. Que peut-on dire de la suite des cardinaux

|Q.u_i|

?
IV.A.2) Montrer qu'il existe un mot synchronisant si et seulement s'il existe pour tout couple d'états (

q, q^'

) de

Q^2

un mot

u_(q, q^')

tel que

q \cdot u_(q, q^') = q^' \cdot u_(q, q^')

.
On veut se servir du critère établi ci-dessus pour déterminer s'il existe un mot synchronisant. Pour cela, on associe à la machine

M

la machine

M˜ = (Q˜, Σ, δ~)

définie par :

$Q˜$ est formé des parties à un ou deux éléments de $Q$ ;
$δ~$ est définie par $\forall(E, x) \in Q˜ \times Σ, δ~(E) = {δ(q, x), q \in E}$ .
$IV.B -$ Si $n = |Q|$ , que vaut $n~ = |Q˜|$ ?
IV.C - On a dit que pour la modélisation informatique, l'ensemble d'états d'une machine doit être modélisée par un intervalle $[ [0, n - 1] ]$ . $Q˜$ doit donc être modélisé par l'intervalle $[ [0, n~ - 1] ]$ . Soit $φ_n$ une bijection de $Q˜$ sur $[ [0, n~ - 1] ]$ . On suppose qu'on dispose d'une fonction set_to_nb de signature int $\to$ (etat list) -> etat telle que set_to_nb $nℓ$ pour $n$ élément de $ℕ^*$ et $ℓ$ liste d'états renvoie

{φ_n({i}), si ℓ = [i] avec i ∈ [ [0, n − 1] ]; φ_n({i, j}), si ℓ = [i; j] avec (i, j) ∈ [ [0, n − 1] ]^2, i < j

On suppose qu'on dispose aussi d'une fonction réciproque nb_to_set de signature int

\to

etat

\to

(etat list) telle que nb_to_set

nq

pour

n

élément de

ℕ^*

q

élément de

[ [0, n~ - 1] ]

renvoie une liste d'états de la forme

[i]

[i; j]

(avec

i < j

) correspondant à

φ_n^(- 1)(q)

. Ces deux fonctions de conversion sont supposées agir en temps constant.
Enfin, pour ne pas confondre un état de

Q˜

avec sa représentation informatique par un entier, on notera

q¯

l'entier associé à l'état

q

.
Écrire une fonction delta2 de signature machine

\to

etat

\to

lettre

\to

etat qui prenant en entrée une machine

M

, un état

q¯

Q˜

et une lettre

x

, renvoie l'état de

Q˜

atteint en lisant la lettre

x

depuis l'état

q

dans

M˜

.
IV.D - Il est clair qu'à la machine

M˜

, on peut associer un graphe d'automate

G˜

dont l'ensemble des sommets est

Q˜

et dont l'ensemble des arcs est

{(q, x, δ~(q, x)), (q, x) \in Q˜ \times Σ}

. On associe alors à

G˜

le graphe retourné

G_R˜

qui a les mêmes sommets que

G˜

mais dont les arcs sont retournés (i.e (

q, x, q^'

) est un arc de

G˜_R

si et seulement si

(q^', x, q)

est un arc de

G˜)

.
Écrire une fonction retourne_machine de signature machine

\to

((etat*lettre) list) vect qui à partir d'une machine

M

, calcule le vecteur

V

des listes d'adjacence du graphe

G˜_R

.
IV.E - Justifier qu'il suffit d'appliquer la fonction accessibles de la partie II au graphe

G˜_R

et à l'ensemble des sommets de

G˜_R

correspondant à des singletons pour déterminer si la machine

M

possède un mot synchronisant.
IV.F - Écrire une fonction existe_synchronisant de signature machine

\to

bool qui dit si une machine possède un mot synchronisant.

Jan Černý, chercheur slovaque, a conjecturé au milieu des années 60 que si une machine à n états possédait un mot synchronisant, elle en avait un de longueur inférieure ou égale

a^‵(n - 1)^2

. La construction faite dans la partie III affirme que la recherche, dans une machine, d'un mot synchronisant de longueur inférieure ou égale à une valeur

m

fixée est au moins aussi difficile en terme de complexité que celui de la satisfiabilité d'une formule logique à m variables sous forme normale conjonctive (qu'on sait être un problème «difficile»).

Pas de description pour le moment

Commentaires• Centrale Option Informatique MP 2017

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...