User:NotARealCat/sandbox

This is the user sandbox of NotARealCat. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Original[edit]

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[edit]

Cet algorithme, dû à John Hopcroft, a pour but de fusionner les états non-distinguables d'un automate (nondistinguishable states en anglais). Il est basé sur le raffinement d'une partition des états d'un automate déterministe fini. Chaque élément de la partition est une classe d'équivalence pour la relation R de Myhill-Nerode.

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.

P := {F, Q \ F};                                                                  d F désigne les états 
W := {F}                                                                          d
for each a in A do                                                                d
     ajouter (min(F, Q\F),a) à W;                                                 d
while (W ≠ l'ensemble vide) do                                                    d
     choisir ensemble (Z,a) dans W et l'enlever de W                              d
     for each X de P coupé par (Z,a) en X' et X'' do                              d
          remplacer X in P par les deux ensembles X' et X''                       d
          for each b in A do                                                      d
               if (X,b) est in W                                                  d
                    remplacer (X,b) in W par (X',b) et (X'',b)                    d
               else                                                               d
                    ajouter le plus petit de (X',b) et (X'',b) à W;               d
          end;                                                                    d
     end;                                                                         d
end;                                                                              d

^ ^a ^b Hopcroft 1971.
^ Le terme coupure est employé par Carton 2008, p. 49.
^ Carton 2008, p. 49.
^ Aho, Hopcroft & Ullman 1974
^ ^a ^b Cite error: The named reference BBCF was invoked but never defined (see the help page).
^ Valmari, Anti (March 2012). "Fast brief practical DFA minimization". Information Processing Letters. Vol. 112. p. 213-217. doi:10.1016/j.ipl.2011.12.004. {{cite news}}: Unknown parameter |numéro= ignored (help).

[Hopcroft-1] Hopcroft 1971.

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

[3] Carton 2008, p. 49.

[4] Aho, Hopcroft & Ullman 1974

[BBCF-5] Cite error: The named reference BBCF was invoked but never defined (see the help page).

[6] Valmari, Anti (March 2012). "Fast brief practical DFA minimization". Information Processing Letters. Vol. 112. p. 213-217. doi:10.1016/j.ipl.2011.12.004. {{cite news}}: Unknown parameter |numéro= ignored (help).

[1]

[2]

[3]

[4]

[5]

[6]