Utilisateur:NotARealCat/Brouillon

Cette page est un brouillon appartenant à NotARealCat

Conseils de rédaction

→ N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
→ Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
Indiquez les éléments démontrant la notoriété du sujet (aide).
Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

→ Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

L'algorithme, appelé ainsi d'après son inventeur, est dû à John Hopcroft^[1] et il a été présenté en 1971; l'algorithme est décrit par le pseudo-code suivant :

P := {F, Q \ F};                                             "Partition initiale"
W := l'ensemble vide;                                        "Candidats en attente"
for each a in A do
     ajouter (min(F, Q\F),a) à W;                            "Initialisation de l'ensemble W"
while (W ≠ l'ensemble vide) do
     choisir ensemble (Z,a) dans W et l'enlever de W
     for each X de P coupé par (Z,a) en X' et X'' do         "Calcul de la coupe"
          remplacer X in P par les deux ensembles X' et X''  "Raffinement de la partition"
          for each b in A do                                 "Mise-à-jour de l'ensemble" 
               if (X,b) est in W                             "des candidats en attente"
                    remplacer (X,b) in W par (X',b) et (X'',b)
               else
                    ajouter le plus petit de (X',b) et (X'',b) à W;
          end;
     end;
end;

L'algorithme débute avec la partition la plus grossière, dont les deux classes sont composées des états terminaux et des autres. La partition est progressivement raffinée en un nombre croissant de classes plus petites. Chaque tour de l'algorithme partage des ensembles d'états en deux parties plus petites.

L'opération de base est la coupure (« splitting » en anglais)^[2]. Un ensemble d'états $X$ est coupé par la paire $(Z,a)$ formée d'un ensemble $Z$ et d'une lettre $a$ si les ensembles

X'=\{q\in X\mid q\cdot a\in Z\}

et

X''=\{q\in X\mid q\cdot a\notin Z\}

sont tous les deux non vides. Dans le cas contraire, on dit que $X$ est stable pour $(Z,a)$ .

L'algorithme maintient un ensemble ${\mathcal {W}}$ de couples $(Z,a)$ , candidats à couper des éléments de la partition en cours; cet ensemble de candidats en attente est appelé le « waiting set » en anglais.

Le lemme suivant^[3] est facile à prouver, mais il est à la base du mécanisme de mise-à-jour du waiting set dans l'algorithme :

Lemme — Soient $X$ et $Z=Z'\cup Z''$ deux ensembles d'états, avec $Z'$ et $Z''$ disjoints non vides, et soit $a$ une lettre.

Si $X$ est stable pour $(Z,a)$ et pour $(Z',a)$ , alors $X$ est stable pour $(Z'',a)$ .
Si $X$ est stable pour $(Z',a)$ et pour $(Z'',a)$ , alors $X$ est stable pour $(Z,a)$ .

L'algorithme choisit itérativement un ensemble $(Z,a)$ dans l'ensemble candidats en attente ${\mathcal {W}}$ , et pour chaque partie $X$ de la partition courante, il teste si $X$ est coupé par $(Z,a)$ . Dans l’affirmative, la partition est mise à jour en remplaçant $X$ par les deux parties $X'$ et $X''$ résultant de la coupure. De plus, l'ensemble des candidats en attente est augmenté, pour toute lettre $b$ , de $(X',b)$ et (X'',b) ou du plus petit de $(X',b)$ et $(X'',b)$ , selon que $(X,b)$ est dans ce waiting set ou non.

La complexité en temps de l’algorithme de Hopcroft, dans le pire des cas, est $O(sn\log n)$ où $n$ est le nombre d'états de l'automate et $s$ est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des $sn$ transitions de l'automate, les ensembles retirés du waiting set qui contiennent l'état d'arrivé d'une transition sont de taille divisé par deux au moins moitié à chaque fois, donc chaque transition participe à au plus $O(\log(n))$ étapes de coupure dans l'algorithme. Une structure de données appropriée permet de réaliser le raffinement d'une partition par une coupure en un temps proportionnel au nombre de transitions qui y sont impliquées^[1]^,^[4].

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010^[5]. L'algorithme initial demande que l'automate de départ soit déterministe et complet. Une extension au cas des automates incomplets a aussi été décrite^[6]. L'implémentation est en temps $O(n+m\log m)$ , où $m$ est le nombre de transitions de l'automate. On a toujours $m\leq sn$

Il reste un certain degré de liberté dans le choix du candidat que l'on retire de l'ensemble des candidats en attente. Cela dépend aussi du choix de la structure de donnée choisie : l'ensemble peut être par exemple organisé en pile (structure LIFO) ou en file (structure FIFO). Des expériences pratiques ont conclu à une meilleure efficacité de la représentation par pile plutôt que par file, et cet avantage a été démontré. Il a aussi été prouvé qu'un choix approprié de la stratégie permet à l'algorithme de Hopcroft d'être toujours meilleur que l'algorithme de Moore^[5]. En particulier, l'algorithme a une complexité en moyenne en $O(sn\log \log n)$ .

Modification

Algorithme de Hopcroft, pseudo-code et explication

Cet algorithme, présenté par John Hopcroft en 1971, fusionne les états non-distinguables d'un automate (nondistinguishable states en anglais). Il fonctionne par raffinement successif d'une partition initialement grossière de l'ensemble $Q$ des états de l'automate déterministe fini à minimiser. Chaque élément de la partition finale est une classe d'équivalence pour la relation $R$ de Myhill-Nerode.

Relation de Myhill-Nérode — Soit un langage $L$ et deux mots $x$ et $y$ . On a $xRy$ si et seulement si pour tout mot $z$ , on a équivalence entre $xz$ est dans $L$ et $yz$ est dans $L$ .

On définit avant tout l'opération primordiale dans l'algorithme de Hopcroft : la coupure (ou splitting en anglais). Un ensemble d'états $X$ est coupé par la paire $(Z,a)$ formée d'un ensemble d'états $Z$ et d'une lettre $a$ si les ensembles

X'=\{q\in X\mid q\cdot a\in Z\}

et

X''=\{q\in X\mid q\cdot a\notin Z\}

sont tous les deux non vides. Si ça n'est pas le cas, on dit alors que $X$ est stable pour le couple $(Z,a)$ .

Algorithme de Hopcroft

P := {T, Q\T};                                                              P est notre partition initiale.
W := {}                                                                     W est la pile des coupes à tester.
Pour tout a lettre de A :
     ajouter (min(T, Q/T), a) à W                                           min(A, B) renvoie l'ensemble de plus petit cardinal.
Tant que W est non vide :
     prendre (S, a) dans X
     Pour tout E dans P, E coupé par (S, a) :
          B', B'' <- Coupure(B, (S, a))                                     B' et B'' issus de la coupure de B par (S, a)
          remplacer B par B'  et B'' dans P
          Pour tout b lettre de A :
               Si (B, b) ∈ W :
                    remplacer (B, b) par (B' , b) et (B'', b) dans W
               Sinon :
                    ajouter ((min(B' , B''), b)) à W.

On pose au préalable le lemme suivant; qui est à la base du mécanisme de mise à jour de la pile d'attente $W$ .

Lemme — Soient $X$ et $Z=Z'\cup Z''$ deux ensembles d'états, avec $Z'$ et $Z''$ disjoints non vides, et soit $a$ une lettre.

Si $X$ est stable pour $(Z,a)$ et pour $(Z',a)$ , alors $X$ est stable pour $(Z'',a)$ .
Si $X$ est stable pour $(Z',a)$ et pour $(Z'',a)$ , alors $X$ est stable pour $(Z,a)$ .

Le but de l'algorithme est d'obtenir par coupes successives un automate déterministe minimal. On rappelle qu'un automate déterministe est minimal si et seulement si tous ses états sont séparables. L'algorithme procède donc en testant la stabilité de chaque groupe d'états de la partition $P$ par toutes les coupes possibles.

Initialement, l'algorithme débute avec la partition $P$ composée de l'ensemble des états terminaux $T$ et de l'ensemble des états non terminaux $Q/T$ . $W$ est la file d'attente des candidats pour raffiner la partition $P$ . On ajoute à $W$ tout couple de la forme $(S,a)$ , avec $a$ une lettre de $A$ , $S$ l'ensemble de plus petit cardinal entre $T$ et $T/Q$ .

A chaque itération de la boucle while, on prend un couple $(S,a)$ de $W$ . Si tout élément de P est stable par cette coupe, on retire le couple $(S,a)$ de $W$ . Sinon, pour chaque élément non stable par la coupe $(S,a)$ , on rajoute à la partition P les deux sous-ensembles obtenus par la coupure de ces éléments par $(S,a)$ . On ajoute alors à W l'ensemble des $(S',a)$ , avec $S'$ le plus petit ensemble obtenu par la coupe.

A chaque itération, soit la pile $W$ se vide d'un élément, soit $P$ se raffine. $P$ ne pouvant se raffiner indéfiniment, l'automate étant fini, le nombre d'itérations est donc fini, majoré par le nombre de transitions de l'automate. Dans le cas d'un automate complet, cette borne vaut $|A|*n$ , avec $A$ l'alphabet et n le nombre d'état. Ceci prouve donc la terminaison de l'algorithme.

Complexité et optimalité

L'algorithme de Hopcroft s'exécute en pire cas en $O(sn\cdot log(n))$ , où $s$ désigne le cardinal de l'alphabet et $n$ désigne le nombre d'état de l'automate. Il y a au plus $sn$ transitions, et pour chacune d'entre elles, les ensembles retirés de $W$ contenant l'état d'arrivée de la transition voient leurs tailles diminuer au moins de moitié. De ce fait, chaque transition participe au plus à $O(log(n))$ étapes de coupure.

On peut adapter l'algorithme au cas des automates déterministes finis non complets. La complexité en temps de cette version de l'algorithme est en $O(n+m\cdot log(m))$ , où $m$ est le nombre totale de transition de l'automate, qui vérifie $m\leq sn$ . L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus actuellement en 2016.

Il est possible d'appliquer l'algorithme de Hopcroft à partir de plusieurs structures de données différentes, notamment pour le choix de la coupe à tester. Les expériences montrent que la structure de pile pour $W$ est la plus efficace, par la suite cet avantage a été démontré. Un choix adapté de la coupe tentée permet à l'algorithme de Hopcroft d'être toujours meilleur que l'algorithme de Moore^[7]. La complexité en moyenne de l'algorithme est en $O(sn\cdot log(log(n)))$

↑ ^{a et b} Hopcroft 1971.
↑ Le terme coupure est employé par Carton 2008, p. 49.
↑ Carton 2008, p. 49.
↑ Aho, Hopcroft et Ullman 1974
↑ ^{a et b} Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BBCF
↑ Anti Valmari, « Fast brief practical DFA minimization », Information Processing Letters, vol. 112, n^o 6,‎ mars 2012, p. 213-217 (DOI 10.1016/j.ipl.2011.12.004).
↑ « Analyse d’algorithmes, langages et automates », sur https://www.lix.polytechnique.fr/, 2011 (consulté le 4 décembre 2016)

[Hopcroft-1] {a et b} Hopcroft 1971.

[2] Le terme coupure est employé par Carton 2008, p. 49.

[3] Carton 2008, p. 49.

[4] Aho, Hopcroft et Ullman 1974

[BBCF-5] {a et b} Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BBCF

[6] Anti Valmari, « Fast brief practical DFA minimization », Information Processing Letters, vol. 112, n^o 6,‎ mars 2012, p. 213-217 (DOI 10.1016/j.ipl.2011.12.004).

[7] « Analyse d’algorithmes, langages et automates », sur https://www.lix.polytechnique.fr/, 2011 (consulté le 4 décembre 2016)

[1]

[2]

[3]

[4]

[5]

[6]

[7]