# 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$^,$$^,$.

## Structure de données

Un algorithme de raffinement de partition permet de tenir à jour une famille d'ensembles disjoints S$_i$. À 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 S$_i$ de la famille qui contient un élément de X est séparé en deux ensembles : l'intersection S$_i$ ∩ X et la différence S$_i$ \ X.
Un tel algorihme peut être réalisé en maintenant à jour des structures de données représentant les informations suivantes $^,$:
* La suite ordonnée des ensembles S$_i$ 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.
* Chaque ensemble S$_i$ 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.
* 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 S$_i$ 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 S$_i$ qui contient x, et on vérifie qu'aucun autre ensemble n'a été créé pour représenter S$_i$ ∩ X. Si ce n'est pas le cas, on crée un second ensemble et on ajoute S$_i$ à 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 S$_i$ et on l'ajoute à S$_i$ ∩ 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 S$_i$, puis en décrémentant l'indice de fin de S$_i$ et l'indice de début du nouvel ensemble S$_i$ ∩ 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 S$_i$ (qui devient S$_i$ \ X) de l'ensemble S$_i$ ∩ 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). 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 S$_i$ 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 à S$_i$ et les états pour lesquels la transition étiquetée x mènent ailleurs. Lorsqu'un ensemble S$_i$ 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.

### Séquençage de tâches

Sethi (1976) 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.

### 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$^,$.