Abstract FR:

Dans ce mémoire, nous étudions quelques propriétés algorithmiques des ensembles ordonnés. En particulier, nous étudions les treillis et les treillis distributifs. Dans la première partie, nous utilisons un théorème de représentation du a Birkhoff 1933 et étudié par Avann 1958 et Monjardet 1974. Nous énonçons un théorème qui donne une partition d'un treillis distributif en sous-treillis distributifs. A partir de cette partition, nous obtenons un algorithme linéaire de reconnaissance, et un algorithme optimal du calcul de la fermeture transitive d'un treillis distributif. En plus, nous en déduisons un algorithme incrémental de génération du treillis des idéaux d'un ordre. Cette partition peut être utilisée pour représenter un treillis distributif par une arborescence appelée arborescence de partition. Cette arborescence de partition occupe un espace linéaire qui est inférieur à celui de la réduction transitive. Elle permet aussi de calculer efficacement les opérations de borne supérieure, borne inférieure, le test de comparabilité et de retrouver d'autres codages d'ordres basés sur la fermeture transitive. Dans la seconde partie, nous considérons le treillis des anti chaînes maximales d'un ensemble ordonné. Nous utilisons une représentation des treillis par des ordres bipartis due à Markowsky 1973 et Reuter 1991. Nous donnons un algorithme polynomial de réduction d'un ordre. Nous donnons ensuite une caractérisation des ordres dont le treillis des anti chaînes maximales est distributif par des ordres admettant une élimination simplicielle. Comme conséquence, le nombre de sauts est polynomial sur cette classe. Le problème de plongement d'un treillis dans un treillis distributif minimal (inclusion) peut se ramener au problème de plongement d'un ordre biparti en un ordre admettant une élimination simplicielle. Nous mettons aussi en évidence quelques objets combinatoires reliés au treillis des anti chaînes maximales tel que l'ordre d'inclusion des ensembles de prédécesseurs et le treillis de Galois