Raffinement de partition

En algorithmique, le raffinement de partition est une technique pour représenter une partition d'un ensemble comme une structure de données qui permet d'affiner cette partition en séparant chaque ensemble en plusieurs sous-ensembles. En ce sens, ce concept peut-être vu comme dual de la structure de données d'union-find, qui cherche à tenir à jour une partition en effectuant des opérations de fusion sur des couples d'ensembles.

Le raffinement de partition est un élément essentiel de plusieurs algorithmes efficaces en théorie des graphes ou en théorie des automates finis, tels que la minimisation des automates finis déterministes, l'algorithme de Coffman–Graham pour le séquençage de tâches, ou le parcours en largeur lexicographique des graphes.[1],[2],[3]

Structure de données

Un algorithme de raffinement de partition permet de tenir à jour une famille d'ensembles disjoints Si. À l'initialisation, cette famille contient un unique ensemble contenant tous les éléments présents dans la structure de données. À chaque étape de l'algorithme, on présente un ensemble X à l'algorithme, et chaque ensemble Si de la famille qui contient un élément de X est séparé en deux ensembles : l'intersection Si ∩ X et la différence Si \ X.

Un tel algorihme peut être réalisé en maintenant à jour des structures de données représentant les informations suivantes [4],[5]:

  1. La suite ordonnée des ensembles Si de la famille sous une forme qui permet d'insérer de nouveaux ensembles à un endroit quelconque de la suite. Cela peut-être fait par exemple à l'aide d'une liste doublement chaînée.
  2. Chaque ensemble Si comme une collection qui permet une suppression efficace des éléments de la collection. Cela peut-être fait avec une liste doublement chaînée.
  3. L'ensemble auquel appartient chaque élément dans la structure de données.

Une manière alternative de représenter la seconde partie de la structure de données est de stocker tous les éléments de tous les ensembles dans un tableau simple ordonné selon l'ensemble auquel ils appartiennent, et en représentant la collection des éléments d'un sous-ensemble Si par la position des éléments de début et de fin de ce sous-ensemble dans le tableau.

Pour réaliser l'opération de raffinement, on parcourt les éléments d'un ensemble X fixé. Pour chaque élément x de l'ensemble, on détermine l'ensemble Si qui contient x, et on vérifie qu'aucun autre ensemble n'a été créé pour représenter Si ∩ X. Si ce n'est pas le cas, on crée un second ensemble et on ajoute Si à une liste L d'ensembles qui ont été séparés par l'opération. Ensuite, indépendamment de la création d'un nouvel ensemble, on retire x de Si et on l'ajoute à Si ∩ X. Dans la représentation où tous les éléments sont stockés dans un tableau simple, déplacer x d'un ensemble à l'autre peut être réalisé en échangeant le contenu de la cellule contenant x avec le dernier élément de Si, puis en décrémentant l'indice de fin de Si et l'indice de début du nouvel ensemble Si ∩ X. Enfin, après que tous les éléments de X aient été traités de cette manière, on parcourt L et on sépare chaque ensemble courant Si (qui devient Si \ X) de l'ensemble Si ∩ X créé à partir de celui-ci, et on les note comme deux nouveaux ensembles créés par l'opération de raffinement.

Le temps pour réaliser une opération de raffinement de cette manière est en O(|X|). Il est indépendant du nombre d'éléments présents dans la famille d'ensembles, ainsi que du nombre total d'ensembles présents dans la structure de données. Par conséquent, le temps pour réaliser une suite de raffinements est proportionnel à la taille totale des ensembles passés en argument à l'algorithme à chaque étape du raffinement.

Applications

Minimisation des automates finis déterministes

Une des premières applications du raffinement de partition figure dans l'algorithme de minimisation des automates finis déterministes d'Hopcroft (1971)[6]. Dans ce problème, l'entrée de l'algorithme est un automate fini déterministe dont on cherche à trouver un automate équivalent ayant un nombre minimum d'états. L'algorithme d'Hopcroft tient à jour une partition des états de l'automate en sous-ensembles, en conservant la propriété que deux états quelconques appartenant à différents ensembles doivent correspondre à des états différents de l'automate en sortie. À l'initialisation, on a deux sous-ensembles, un contenant tous les états d'acceptation de l'automate, et l'autre contenant les états restants. À chaque étape, on choisit un des sous-ensembles Si et l'un des symboles d'entrée x de l'automate; les sous-ensembles d'états sont raffinés en états pour lesquels la transition étiquetée x mènent à Si et les états pour lesquels la transition étiquetée x mènent ailleurs. Lorsqu'un ensemble Si qui a déjà été choisi est séparé par un raffinement, seul le plus petit ensemble des deux sous-ensembles créés doit être choisi à nouveau. Ainsi, chaque état participe aux ensembles X pour O(s log n) étapes de raffinement, et la totalité de l'algorithme prend un temps en O(ns log n), où n est le nombre d'états initiaux et s la taille de l'alphabet. [6]

Séquençage de tâches

Sethi (1976)[7] applique le raffinement de partition à une implémentation de l'algorithme de Coffman-Graham pour le séquençage de tâches parallèle. Sethi montre qu'on peut l'utiliser pour réaliser un tri topologique en ordre lexicographique d'un graphe dirigé acyclique donné en temps linéaire. Cet ordonnancement est une des étapes-clefs de l'algorithme de Coffman-Graham. Dans cette application, les éléments des ensembles de nœuds du graphe en entrée et les ensembles X utilisés dans le raffinement de partition sont les ensembles de voisins des nœuds. Comme le nombre total de voisins de l'ensemble des nœuds du graphe est le nombre de liens du graphe, l'algorithme est en temps linéaire du nombre de liens.[7]

Parcours en largeur lexicographique

Le raffinement de partition est aussi une étape-clef du parcours en largeur lexicographique, un algorithme de parcours de graphe applicable à la détection des graphes cordaux et plusieurs autres classes de graphes importantes. Ici aussi, les éléments des ensembles sont les nœuds du graphe et l'ensemble X représente l'ensemble des voisins, donc l'algorithme est en temps linéaire en le nombre de liens du graphe. [8],[9]

Références
  1. (en) Robert Paige et Robert E. Tarjan, « Three partition refinement algorithms », SIAM Journal on Computing, vol. 16, no 6,‎ , p. 973–989 (DOI 10.1137/0216062, Math Reviews 917035).
  2. (en) Michel Habib, Christophe Paul et Laurent Viennot, « Partition refinement techniques: an interesting algorithmic tool kit », International Journal of Foundations of Computer Science, vol. 10, no 2,‎ , p. 147–170 (DOI 10.1142/S0129054199000125, Math Reviews 1759929).
  3. (en) Michel Habib, Christophe Paul et Laurent Viennot, « A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata », Proceedings of STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, Springer-Verlag, Lecture Notes in Computer Science, vol. 1373,‎ , p. 25–38 (ISBN 978-3-540-64230-5, DOI 10.1007/BFb0028546, Math Reviews 1650757).
  4. (en) Antti Valmari et Petri Lehtinen, « Efficient minimization of DFAs with partial transition functions », Proceedings of STACS 2008: 25th International Symposium on Theoretical Aspects of Computer Science, Dagstuhl, Allemagne, Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, leibniz International Proceedings in Informatics (LIPIcs), vol. 1,‎ , p. 645–656 (ISBN 978-3-939897-06-4, DOI 10.4230/LIPIcs.STACS.2008.1328, Math Reviews 2873773, lire en ligne).
  5. (en) Timo Knuutila, « Re-describing an algorithm by Hopcroft », Theoretical Computer Science, vol. 250, nos 1–2,‎ , p. 333–363 (ISSN 0304-3975, DOI 10.1016/S0304-3975(99)00150-4).
  6. (en) John Hopcroft, « An n log n algorithm for minimizing states in a finite automaton », dans Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York, Academic Press, (Math Reviews 0403320), p. 189–196.
  7. (en) Ravi Sethi, « Scheduling graphs on two processors », SIAM Journal on Computing, vol. 5, no 1,‎ , p. 73–82 (DOI 10.1137/0205005, Math Reviews 0398156).
  8. (en) D.J.Rose, R.E.Tarjan et G.S.Lueker, « Algorithmic aspects of vertex elimination on graphs », SIAM Journal on Computing, vol. 5, no 2,‎ , p. 266–283 (DOI 10.1137/0205021).
  9. (en) Derek G.Corneil, « Lexicographic breadth first search – a survey », Proceedings of the 30th International Workshop on Graph-Theoretic Methods in Computer Science (WG 2004), Bad Honnef, Allemagne, Springer-Verlag, Lecture Notes in Computer Science, vol. 3353,‎ , p. 1–19 (DOI 10.1007/978-3-540-30559-0_1).
  • Portail des bases de données
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.