Une classe d'ordres partiels : les treillis.

Les relations d'ordres partiels (càd. réflexive, transitives et anti-symétriques) sont étudiées en mathématiques depuis un certain temps (notamment les structures d'ordres infinis), mais leur étude a connu un vrai essor récemment, en particulier à cause de leurs applications en informatique. Ils interviennent en bases de données, fouille de données (data mining), langages orientés-objets, calcul distribué, ordonnancement ...

Les ordres totaux (pour toute paire d'éléments, l'un d'eux est plus petit que l'autre), comme l'ordre usuel sur N, Z ou R, ne sont qu'un cas très particulier d'ordres. Une des classes d'ordres les plus intéressantes par ses propriétés et ses applications est la classe des treillis : les ordres tels que toute paire d'éléments admet une borne supérieure et une borne inférieure.

L'objectif ici est de présenter la classe des treillis (et éventuellement caractériser des sous-classes comme les treillis distributifs), ainsi que des applications. Les points qui suivent sont des suggestions :

• Présenter les notions de bases sur les ordres partiels (définitions, relation de couverture, diagramme de Hasse, applications croissantes = order-preserving, plongements = order-embedding) et sur les treillis (définitions, treillis complets). Donner des exemples de treillis.
• Un exemple de théorème sur les treillis : le théorème de Knaster-Tarski sur les treillis complets.
  
• Un exemple d'application pratique des treillis est l'analyse de concepts en data-mining. A partir d'un ensemble de données, il s'agit de factoriser les informations sous forme de "concepts" qui sont ensuite organisés selon un ordre partiel et il s'avère que c'est un treillis. Présenter cette problématique d'analyse de concepts, ainsi que la structure de treillis qui va avec (treillis de concepts, parfois aussi appelé treillis de Galois).
• Présenter un algorithme de génération de treillis, comme celui de Nourine et Raynaud qui s'applique en particulier aux treillis de concepts.
  

Quelques références (pas exhaustif).

• Introduction to Lattices and Order, livre de B. Davey et H. Priestley, Cambridge University Press (1990). Bon livre d'introduction aux ordres et treillis, avec toutes les définitions de base. Le chapître 11 traite des treillis de concepts.
• A fast algorithm for building lattices, article de L. Nourine et O. Raynaud dans le journal Information Processing Letters (1999). Un algorithme de construction de treillis, qui s'applique à différents types de treillis dont les treillis de concepts.
  

Retour à la page des sujets.