Posets et Extensions Linéaires

Tran - Ozyonum - Okutucu

Introduction

En informatique comme en mathématiques, les structures ordonnées existent sans être manifesté explicitement. Que ce soit lors d'un calcul d'une expression mathématique, lors de l'installation de packages, certaines tâches ne peuvent être effectuées avant d'autres et doivent être éxécutées selon un ordre de priorité qui n'est pas total. On peut modéliser cette dernière par un arbre : chaque tâche est représentée par un sommet tandis qu'un arc représente une contrainte. De plus chaque ordonnancement valide des taches correspond à une extension linéaire.

Plan

Définitions

Le corps de ce chapitre fixera les notions à connaitre pour ensuite les appliquer afin de résoudre les problématiques liées à ces derniers.

Un poset est un ensemble P muni d'une relation d'ordre ≤ vérifiant les conditions suivantes. Le poset doit être : - réflexif : ∀x ∈ P, x ≤ x - antisymétrique : ∀x, y ∈ P, si x ≤ y et y ≤ x alors x = y - transitif : ∀x, y, z ∈ P, si x ≤ y et y ≤ z alors x ≤ z

Si la relation d’ordre est telle que pour tout x, y ∈ P, alors soit x ≤ y , soit y ≤ x , on dit que l’ordre est total ou linéaire. Si la relation d'ordre n'est valable que pour certains éléments de l'ensemble, alors on dit que l'ordre est partiel, d'où le nom de poset (qui signifie en anglais partially ordered set). Prenons un ensemble de tâche à traiter par une machine, certaines tâches ne peuvent être exécutées avant d'autres. Trouver un ordonnancement compatible de ces tâches, c'est trouver une extension linéaire de l'ensemble ordonné induit par les contraintes entre tâches.

Exemple d'extensions linéaires d'un poset

Toute relation d'ordre partielle admet une extension linéaire (relation d'ordre total). Effectuer un tri topologique sur un graphe sans circuit consiste à trouver une extension linéaire.

Application

Ce chapitre consiste à appliquer ce que l'on a vu précédemment. Prenons par exemple l'expression mathématique :

(1 + 3) ∗ 5 − (16/4)

Les calculs des éléments à gauche et à droite de la différence peuvent s’effectuer de manière indépendante alors que l’on a besoin du résultat de ses deux calculs pour effectuer la différence finale. On se retrouve avec un ensemble partiellement ordonné ou poset (partially ordered set).

Problème : Comment définir un ordre total ?

La notation de l'expression précédente est appelée notation infixée, car les symboles sont placés en infixe par rapport aux opérandes. Une notation plus intéressante consiste à placer l'opérateur en suffixe (postfix en anglais) car elle a l'avantage de dispenser complètement des parenthèses. Voici notre expression en notation postfix :

1 3 + 5 * 16 4 / -

Et voici une implémentation de l'algorithme qui permet cela :

Cependant cette étape ne répond toujours pas à notre problématique de départ mais maintenant que notre expression est simplifiée, nous pouvons l'utiliser plus aisément pour construire notre poset qui va représenter l'ordre partiel des opérations à effectuer. Et la voici :

Et voici une implémentation de l'algorithme qui permet cela :

Nous avons vu dans le premier chapitre que toute relation d'ordre partielle admet une relation d'ordre total et qu'effectuer un tri topologique sur un graphe sans circuit (d'où le fait d'avoir transformé notre expression en poset) consiste à trouver une extension linéaire, c'est-à-dire un ordre total. Voici donc une extension linéaire après avoir effectué le tri topologique sur le sommet "diviser".

(-) : 1 ; (*) : 2; (+):4; (/):3

On part de 1, ordre de visite : 1 3 2 4

ordre total (extension linéaire) : 3 < 4 < 2 < 1

Et voici une implémentation de l'algorithme de tri topologique :

Nous venons, à partir d'un ensemble partiellement ordonné, d'obtenir un ordre total de ses éléments.

Problème : comment obtenir le nombre d'extensions linéaires ?

Soit P(S,R), un poset avec S représentant l'ensemble {s1,…,sn} et R un ensemble de relations d'ordre réflexive, antisymétrique et transitive. R représente les relations de couvertures, c'est-à-dire que s2 couvre s1 si on a s1 < s2. Un poset P' est un sous-poset de P si en tant qu’ensemble, P' ⊂ P et si la relation d’ordre de P' est identique à celle de P mais restreinte aux éléments de P'. Une chaîne C est un ensemble {c1,...,cn} où C ⊆ P  tel que pour tout élément appartenant à C ,  c1 <= c2 <=... <= cn ; c'est-à-dire que l'ensemble suit bien les relations de R . Si la cardinalité de C est maximum, alors la valeur de |C| indique la hauteur de P.

Par opposition, l'ensemble A{a1,...,an} est une antichaîne si tout élément appartenant à A sont incomparables. Si la cardinalité de A est maximum, alors la valeur de |A| indique la largeur de P. On considère que tous les ensembles singletons sont des chaînes et des antichaînes.

Un élément s ∈ S est minimal s'il n'existe pas d'élément s' ∈ S , tel que s' ≤ s.

Exemple :Soit le poset P tel que S = ({1, . . . , 6} et la relation d’ordre R = {(1, 2),(4, 2), (4, 3),(4, 5),(4, 6),(6, 2),(6, 5)}.

Une extension linéaire de P est 4−3−6−1−5−2. L’ensemble C = {4, 6, 5} est une chaîne et est de taille maximum. La hauteur de P est h = |C| = 3. L’ensemble A = {1, 6, 3} est une antichaîne et est de taille maximum. La largeur de P est k = |A| = 3.

Pour calculer le nombre d'extensions linéaires, on va utiliser la stratégie du diviser pour régner afin de calculer des sous-posets récursivement. On procède à l'élimination de l'élément minimum de chaque sous-poset car d'après la définition dite précédemment, cet élément n'a pas d'autre élément où il est supérieur à cet autre élément. De plus, il n'y aura pas d'impact sur le nombre d'extensions linéaires.

On répète cette opération jusqu'à l'obtention d'un sous-poset qui forme une chaîne ou une antichaîne. Ainsi, on calcule la somme des sous-posets afin d'obtenir le nombre d'extensions linéaires.

Si nous reprenons le dernier exemple cité, on a le poset P tel que MIN(P) = {4}. Ainsi, le retrait de l’élément {4} n’aura pas d’impact sur le nombre des extensions linéaires de P. En retirant cet élément, le poset se décompose en un élément isolé {3} et un sous-poset P' dont les éléments sont {1, 2, 5, 6}. Le nombre d’extensions linéaires de P est donc #P(S) = (|{1, 2, 5, 6}| + 1) × #P({1, 2, 5, 6}) où le premier terme correspond aux insertions possibles de l’élément {3} dans une permutation du reste.

On a une autre possibilité où MIN(P) = {1}. Dans ce cas, en retirant l'élément {1}, le poset se décompose en un sous-poset P' dont les éléments, sont {2, 3, 4, 5, 6}. Si on continue la récursion avec MIN(P') = {4}, on obtient un élément isolé {3} et un sous-poset P'' dont les éléments sont {2, 5, 6}, et donc, si on continue ainsi, on obtiendra une première antichaîne {2, 5} après retrait du seul élément minimal {6}. Le nombre d’extensions linéaires de P est donc #P(S) = (|{1, 2, 5, 6}| + 1) × #P({1, 2, 5, 6})   + (|{2, 5, 6}| + 1) × #P({2, 5, 6}) = 5 x #P({1, 2, 5, 6}) + 4 x #P({2, 5, 6}) = 33.

Reprenons le poset de l'opération (1 + 3) ∗ 5 − (16/4) avec les éléments S = { (-) : 1 ; (*) : 2; (/):3; (+):4 }.

L'élément {1} est le minimum donc on se retrouve avec un sous-poset {2, 4} et un élément isolé {3}.

Dans ce cas, #P(S) = (|{2, 4}| + 1) × #P({2, 4})   = 3 x 1 = 3.

Donc on retrouve bien le nombre de 3 extensions linéaires.

Les voici :


Bibliographie :

http://igm.univ-mlv.fr/~gchatel/these_gchatel.pdf

https://tel.archives-ouvertes.fr/tel-00817371/file/1987_Bouchitte_Vincent.pdf

https://www.irif.fr/~hf//verif/ens/IF2/coursIF2/C11.htm

http://www.f-legrand.fr/scidoc/srcdoc/algorithmes/syntaxe/expmath/expmath-pdf.pdf

http://www.enseignement.polytechnique.fr/informatique/profs/Jean-Eric.Pin/PDF/XC9.pdf

0 Cliquer pour recommander cet article