Posets et extensions linéaires

Introduction :

­Un poset ou ensemble partiellement ordonné contient un ensemble d’éléments et une relation d’ordre. Nous pouvons ainsi modéliser les différentes parties indépendantes d'un calcul, ou différents problèmes mathématiques.
Nous commencerons par définir ce qu'est un poset et les différentes opérations qu'on peut effectuer dessus. Puis nous parlerons des utilisations du poset avec l'exemple du plus court chemin et de Salesman. Pour finir, nous illustrerons notre sujet avec différentes pistes de développement comme le battage de cartes et le tri topologique.

1 - Définitions :

Quelques notions nécessaires à la compréhension des posets, avec A un ensemble et R une relation :

Une relation est dite :

    • réflexive : si un élément est en relation avec lui même (aRa).
    • antisymétrique : si deux éléments sont en relation l’un avec l’autre alors les deux éléments sont égaux (aRb ^ bRa ⇒ a = b).
    • transitive : si trois éléments sont en relation de la manière suivante (aRb ^ bRc ⇒ aRc).
Définition du poset :

Le poset ou ensemble partiellement ordonné est une structure mathématique définie par un ensemble et une relation de comparaison qui est réflexive, antisymétrique et transitive.

Exemple :
Avec un ensemble E = {1, 2, 3, 4, 5} et la relation de comparaison ≤ on peut définir un poset (E, ≤).

Définition d'une chaine :

Si pour un poset (A,R) , R est une relation d’ordre total alors (A,R) est une chaine.
R est une relation d’ordre total si pour tout a et b appartenant à A, a et b sont toujours comparables.

Exemple :
Pour tout a et b inclus dans A, on peut utiliser le comparateur ≤. La relation d’ordre est une chaine.
Au contraire la relation ⊆ ne s’applique pas à X et Y car il est possible que X et Y soient deux ensembles disjoints.

Définition d'un poset ordonné :

On dit que le poset (A,R) est bien ordonné si chaque sous ensemble de A possède un plus petit élément. Le plus petit élément valide toujours la relation avec tous les autres éléments de l’ensemble.
(Il existe un a tel que pour tout b inclu dans A, aRb)

Exemple :
Avec un ensemble E = {1, 4, 6, 8}, (E, ≤) est un poset bien ordonné.
A contrario le poset (Z, ≤ ) n’est pas un poset bien ordonné car Z ne possède pas de plus petit élément.

Définition d'une relation inductive :

On appelle relation inductive une relation composée de plusieurs sous relations.
Si il existe des posets (A1, R1) et (A2, R2), on peut construire une relation inductive R qui s’applique sur le produit cartésien de A1 et A2.

La relation s’exprime de la manière suivante :
<x1, y1>R<x2,y2>
si et seulement si :
x1 R1 x2 ou x1 = x2 et y1 R2 y2

Exemple :
100 ≤ 101
On crée deux posets qui représentent ce problème :
⇔ A1 = {1,0,0} < A2 = {1,0,1}
On a :
A1[0] = A2[0]
A1[1] = A2[1]
A1[2] < A2[2]
Donc A1 < A1, la relation est vraie.

Définition d'une extension linéaire :

Une extension linéaire d'un ordre partiel est un ordre total qui est compatible avec l'ordre partiel.

2 − Utilisation des posets :

Le plus court chemin :

Le problème du plus court chemin est un problème connu dans la théorie des graphes. Prenons un graphe dans lequel nous avons associé un poids à chaque arête, le problème est de savoir le chemin de poids le plus faible afin d’accéder à tous les sommets du graphe en partant d’un point A.

Ce problème est solvable par plusieurs algorithmes (Bellman-Ford, Djikstra…). Nous allons nous attarder sur Djikstra qui ne marche qu’avec des poids positifs.
L’algorithme de Djikstra effectue un parcours et génère un arbre d’où nous tirerons la notion de père et de fils.

On effectue Djikstra sur un point A :

Algorithme :

Initialisation :

Pour chaque sommet du graphe, nous allons associer une distance ainsi qu’un sommet qui correspondra au père.
Nous allons associer à tous les sommets la distance "infinie" et "nil" en père (dans ce cas, la distance infinie signifie que le sommet en question n’est pas encore atteignable par A et nil signifie qu’il n’a pas encore de père).
Cependant le sommet A a une distance de 0 (c’est le point de départ) et un père à nil (il n’en a pas).

Explication de l'algorithme pas à pas :

    1. On prend dans notre liste le sommet u de poids minimal qui n’a pas encore été traité (lors de la première itération c’est A) et pour toutes ses arêtes (u,v,W) (v le sommet vers qui u pointe, W = weight = poids).
    2. Si la distance de u plus W est inférieure à la distance de v, cela signifie que nous venons de découvrir un chemin plus court pour accéder à v. v prendra donc cette nouvelle distance (distance de u plus W) et aura comme père u.
    3. Une fois que toutes les arêtes de u ont été traitées, nous en avons fini avec u et nous pouvons revenir à l’étape 1 (s’il reste des sommets à traiter).

La complexité de cet algorithme s’évalue en O(n²).

Problème du SalesMan :

Imaginons un homme d’affaire voulant parcourir toutes les villes d’une région sans passer deux fois par une même ville et en sachant que toutes les villes sont reliées entre elles. Ce problème peut se modéliser à l’aide d’un graphe valué non-orienté complet et consiste à rechercher le circuit hamiltoniens de poids le plus faible. La méthode la plus directe est de détecter tous les circuits hamiltoniens et d’en extraire le plus ‘petit’.

Avec un graphe à n sommets, on choisit un point de départ. Il existe alors n-1 circuit hamiltoniens disponible pour le sommet d’après, il en existe n-2 et ainsi de suite jusqu’au dernier sommet. Nous avons donc (n-1) ! circuit hamiltoniens, mais le graphe étant non-orienté, il en existe en réalité (n-1)!/2. Malgré tout, la complexité de cet algorithme est très élevée : pour seulement 25 sommets, cela prendrait 10 millions d’années si on prenait une nanoseconde à examiner un circuit.

3 - Pistes de développement :

Battage des cartes :

Pour poser les bases, nous allons parler durant toute cette partie d’un jeu de 52 cartes, et chaque carte sera nommée 1, 2, 3, …, 52.

Pour la coupe, on va couper un paquet en deux sous paquets de taille j et j-n, avec j entre 0 et n (52 dans notre cas).
Pour le mélange, on le définira de la manière suivante : on coupe le paquet en deux (a1 et a2), et on en créé un troisième en prenant une carte dans l’un puis dans l’autre avec la probabilité suivante :
P(a1) = a1/(a1+a2) ou P(a2) = a2/(a1+a2). Et on continue jusqu’à ce que l’on est plus de carte dans aucun de nos paquets. Pour la plupart du temps, cela ne fonctionne pas car les deux paquets n’ont pas le même nombre de carte.

On peut interpréter un battage de cartes comme une permutation qui va se représenter de la manière suivante :

( 1 2 3 4 5 6 7 8 9 )
( 5 6 7 1 2 8 4 3 9)

La première ligne va représenter l’ordre des cartes avec le battage, et la seconde ligne l’ordre après le battage des cartes.

Pour un jeu de n cartes, il y a n! permutation possible, donc nous avons pour la première carte possible 52 possibilités, pour la seconde 51, donc 52 * 51 * 50 *… * 1 = 52 ! soit :

80658175170943878571660636856403766975289505440883277824000000000000

C’est un nombre qui dépasse tout ce que l’on connaît. Si on voulait écrire toutes les permutations d’un jeu de carte, cela nous prendrait probablement plusieurs milliards d’années, et on ne pourrait probablement pas tout écrire par manque de matière dans l’univers.
Donc, on pourrait se poser des questions sur le fonctionnement d'un jeu de carte, par exemple : comment les tours de magie peuvent donner toujours un résultat correct ?

Prenons un exemple :
Un magicien présente un paquet de cartes à un observateur. Sans que le magicien n’ait le droit de regarder, il demande à ce que l’on batte le paquet trois fois et que l’on prenne la carte du dessus. Alors, l’observateur doit retenir la carte et la remettre où il veut dans le jeu.
Le magicien étale ensuite les cartes et retrouve la carte choisie par l’observateur.

Comment fonctionne ce tour ? Normalement, en ayant battu les cartes, le magicien ne peut pas connaître l’ordre des cartes dans le paquet, et donc si la personne bat une fois les cartes en plus, impossible de savoir où se trouve la carte remise dans le paquet.
Et pourtant à l’aide d’une simulation sur ordinateur sur un million d’essai ce tour à 84 % de réussite.

Quelques explications pour s’y retrouver : Qu’est ce qu’une suite montante ?
Avec la suite suivante :

( 1 2 3 4 5 6 7 8 9 10 11 12 )
( 4 5 6 7 1 2 3 10 11 12 8 9 )

On a les sous suites montantes suivantes : (4, 5, 6, 7), (1, 2, 3), (10, 11, 12), (8, 9).

C’est à dire que quand les cartes sont dans triées, 1, 2, 3, …, n, et qu’on bat une première fois les cartes, on se retrouve avec deux suites montantes : (1, 2, 3, …, k) et (k + 1, k + 2, …, n), où k est le numéro de la carte où il y a eu la coupe.
Lorsqu’on refait plusieurs fois cette opération, on double le nombre de suite montante, sauf le cas (un peu improbable) où l'on remet le paquet exactement dans la même position qu’à la coupe précédente, et dans ce cas là, on se retrouve qu’avec une seule suite montante. Autrement, on se retrouve avec toujours deux fois plus de suite montante à chaque coupe. Par exemple, au bout de trois battages, on se retrouve avec huit suites montantes, ce qui donne pour un paquet de cartes une moyenne de 6,5 cartes par suite environ.

Or, l’observateur va remettre la carte dans le paquet, ce qui va créer une neuvième suite montante, car elle n’est pas remise à sa position d’origine, l’observateur cherchant la plupart du temps à la remettre à un autre endroit pour embrouiller le magicien. Ainsi le magicien n’a plus qu’à regarder toutes les cartes et trouver une suite montante à une carte.

Représentations des extensions linéaires :

Afin d'afficher une extension linéaire d'un Poset, nous avons développé  un programme en java contenant une structure de donnée Poset et un ensemble de fonctions pour afficher l'extension linéaire correspondante.

La structure de données se présente sous la forme d'une classe générique "Poset<T>" qui implémente l'interface Iterable qui permet de rendre les données accessibles.
La classe possède un tableau qui représente l'ensemble du Poset et un objet de la classe BiFunction<T,T,Boolean> représentant la relation d'ordre du Poset. La classe possède aussi un itérateur et un arbre représentatif.

Le constructeur de Poset génère un arbre représentatif du Poset qui peut être itéré. Cet arbre prend en compte les relations transitives et utilise une sous classe "Node" représentant les noeuds de l'arbre.

Sachant que le parcours en largeur d'un arbre représentatif de Poset donne une extension linéaire, on effectue un parcours en largeur récursif en partant des éléments minimaux de notre Poset et on génère un String représentatif de notre extension linéaire:

Pour le Poset p = ({{}, {a}, {b}, {c}, {a,b}, {b,c}, {c,a}, {a,b,c}}, ⊆) on obtient avec notre programme:


Auteurs :
- Arnaud Bihan
- Nathan Caracciolo
- Léa Dupuy
- Aladdin Guillemot


Bibliographie :

    • https://www.cs.rutgers.edu/~elgammal/classes/cs205/chapt76.pdf
    •  Rosen, Discrete Mathematics and its applications (section 9.6)
    •  (**) Stanley, Enumerative combinatorics vol. 1 (Proposition 3.5.2 p257 et suivant,définitionJ(P)p 246)
    • http://igm.univ-mlv.fr/~biane/cartes.pdf
    • Wikipédia

0 Cliquer pour recommander cet article