J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Centrale Option Informatique MP 2017

Mots synchronisants

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo centrale
🔗 Explorer
Banque
Centrale
Année
2017
Filière
MP
Matière
Info
Centrale MPCentrale 2017MP InfoInfo 2017
2025_08_29_cc4c5e4a72ab12b5d941g

Mots synchronisants

Notations

  • Pour tout ensemble fini , on note son cardinal.
  • On appelle machine tout triplet ( ) où 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 dans 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 et une lettre , on note .
  • L'ensemble des mots (c'est-à-dire des concaténations de lettres) sur l'alphabet est noté .
  • Le mot vide est noté .
  • On note le mot obtenu par la concaténation du mot et de la lettre .
  • On note l'extension à de la fonction de transition définie par
  • Pour un état de et un mot de , on note encore pour désigner .
Pour deux états et est dit accessible depuis s'il existe un mot tel que .
On dit qu'un mot de est synchronisant pour une machine ( ) s'il existe un état de tel que pour tout état de .
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 ( ). Par contre, pour la modélisation en Caml, l'alphabet sera toujours considéré comme étant un intervalle d'entiers où . Une lettre correspondra donc à un entier entre 0 et . 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 d'une machine sera toujours considéré comme étant l'intervalle d'entiers où .
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 , 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 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 .
Figure 1 La machine
On pourra observer que les mots 11 et 10 sont tous les deux synchronisants pour la machine .
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 .

I Considérations générales

I. - 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.
- On considère la machine représentée figure 2. Donner un mot synchronisant pour s'il en existe un. Justifier la réponse.
Figure 2 La machine
- On considère la machine représentée figure 3. Donner un mot synchronisant de trois lettres pour . On ne demande pas de justifier sa réponse.
- Écrire une fonction delta_etoile de signature machine etat mot etat qui, prenant en entrée une machine , un état et un mot , renvoie l'état atteint par la machine en partant de l'état et en lisant le mot .
I.E - Écrire une fonction est_synchronisant de signature machine mot bool qui, prenant en entrée une machine et un mot , dit si le mot est synchronisant pour .
I.F - Montrer que pour qu'une machine ait un mot synchronisant, il faut qu'il existe une lettre et deux états distincts de et , tels que .
I. - Soit le langage des mots synchronisants d'une machine . On introduit la machine des parties où est l'ensemble des parties de et où est définie par
I.G.1) Justifier que l'existence d'un mot synchronisant pour 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 des mots synchronisants de la machine est reconnaissable.
Figure : une machine à 4 états
I.G.3) Déterminer la machine des parties associée à la machine puis donner une expression régulière du langage .
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 et un état de choisi, s'il existe un mot tel que pour tout état de , le chemin menant de à passe forcément par .

II Algorithmes classiques

On appellera graphe d'automate tout couple ( ) où est un ensemble dont les éléments sont appelés sommets et une partie de dont les éléments sont appelés arcs. Pour un arc ( ), est l'étiquette de l'arc, son origine et 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
le graphe d'automate est représenté figure 4 .
Soient et deux sommets d'un graphe ( ). On appelle chemin de vers de longueur toute suite d'arcs de telle que et pour tout de . L'étiquette de ce chemin est alors le mot et on dit que est accessible depuis . En particulier, pour tout est accessible depuis par le chemin vide d'étiquette .
Figure 4 Le graphe d'automate
Dans les programmes à écrire, un graphe aura toujours pour ensemble de sommets un intervalle d'entiers et l'ensemble des arcs étiquetés par (comme précédemment supposé être un intervalle ) sera codé par un vecteur de listes d'adjacence pour tout est la liste (dans n'importe quel ordre) de tous les couples tel que 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 , la lettre est codée 0 et la lettre est codée 1 ; l'ensemble des arcs du graphe , 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 et 8 , dans cet ordre, avec et deb .
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 .
II.A.1) Écrire une fonction ajoute de signature 'a file ' unit telle que ajoute ajoute à la fin de la file d'attente . 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 'a telle que retire 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 et à un ensemble de sommets (on note et , vide et rien des valeurs particulières).
II.B - Justifier que l'algorithme 1 termine toujours.
II. - Donner la complexité de cet algorithme en fonction de et . On justifiera sa réponse.
II.D - Justifier qu'au début de chaque passage dans la boucle «tant que n'est pas vide», si contient dans l'ordre les sommets , alors et .
II.E - Pour sommet de , on note la distance de à c'est-à-dire la longueur d'un plus court chemin d'un sommet de à (avec la convention s'il n'existe pas de tel chemin).
II.E.1) Justifier brièvement qu'à la fin de l'algorithme, pour tout sommet si et seulement si est accessible depuis un sommet de et que . Que désigne alors ?
II.E.2) Montrer qu'en fait, à la fin, on a pour tout sommet . Que vaut alors ?
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 ( ) calculé selon l'algorithme précédent. Les constantes , vide et rien seront respectivement codées dans la fonction accessibles par -1 , et .
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 (etat*lettre) vect mot qui, prenant en entrée un sommet s et le vecteur P calculé à l'aide de la fonction accessibles sur un graphe et un ensemble , renvoie un mot de longueur minimale qui est l'étiquette d'un chemin d'un sommet de à (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 . On note classiquement le connecteur logique « et », le connecteur «ou» et la négation d'une formule .
On appelle littéral une formule constituée d'une variable ou de sa négation , 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,
est une formule sous forme normale conjonctive formée de trois clauses et portant sur quatre variables propositionnelles et .
Soit une formule sous forme normale conjonctive, composée de clauses et faisant intervenir variables. On suppose les clauses numérotées . 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 à sur une certaine machine. On introduit pour cela la machine suivante associée à :
  • est formé de états, un état particulier noté et autres états qu'on notera avec
    ;
  • est défini par
  • est un état puits, c'est-à-dire ,
  • pour tout entier de ,
  • pour tout dans et dans ,
éîéî
III. - Représenter la machine associée à la formule .
III. - Donner une distribution de vérité (la valeur étant associée à la variable ) satisfaisant . Le mot est-il synchronisant?
III. - Montrer que tout mot de longueur est synchronisant. À quelle condition sur les un mot de longueur est-il synchronisant ?
III. - Montrer que si la formule est satisfiable, toute distribution de vérité la satisfaisant donne un mot synchronisant de longueur pour l'automate.
III. - Inversement, prouver que si l'automate dispose d'un mot synchronisant de longueur inférieure ou égale à 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 .
IV.A - Soit une machine.
Pour toute partie de et tout mot de , on note .
IV.A.1) Soit un mot synchronisant de et une suite de préfixes de rangés dans l'ordre croissant de leur longueur et telle que . Que peut-on dire de la suite des cardinaux ?
IV.A.2) Montrer qu'il existe un mot synchronisant si et seulement s'il existe pour tout couple d'états ( ) de un mot tel que .
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 la machine définie par :
  • est formé des parties à un ou deux éléments de ;
  • est définie par .
    Si , que vaut ?
    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 . doit donc être modélisé par l'intervalle . Soit une bijection de sur . On suppose qu'on dispose d'une fonction set_to_nb de signature int (etat list) -> etat telle que set_to_nb pour élément de et liste d'états renvoie
On suppose qu'on dispose aussi d'une fonction réciproque nb_to_set de signature int etat (etat list) telle que nb_to_set pour élément de et élément de renvoie une liste d'états de la forme ou (avec ) correspondant à . Ces deux fonctions de conversion sont supposées agir en temps constant.
Enfin, pour ne pas confondre un état de avec sa représentation informatique par un entier, on notera l'entier associé à l'état .
Écrire une fonction delta2 de signature machine etat lettre etat qui prenant en entrée une machine , un état de et une lettre , renvoie l'état de atteint en lisant la lettre depuis l'état dans .
IV.D - Il est clair qu'à la machine , on peut associer un graphe d'automate dont l'ensemble des sommets est et dont l'ensemble des arcs est . On associe alors à le graphe retourné qui a les mêmes sommets que mais dont les arcs sont retournés (i.e ( ) est un arc de si et seulement si est un arc de .
Écrire une fonction retourne_machine de signature machine ((etat*lettre) list) vect qui à partir d'une machine , calcule le vecteur des listes d'adjacence du graphe .
IV.E - Justifier qu'il suffit d'appliquer la fonction accessibles de la partie II au graphe et à l'ensemble des sommets de correspondant à des singletons pour déterminer si la machine possède un mot synchronisant.
IV.F - Écrire une fonction existe_synchronisant de signature machine 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 . 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 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»).
Centrale Option Informatique MP 2017 - Version Web LaTeX | WikiPrépa | WikiPrépa