Treillis : structures, algorithmes et quelques usages
From 05/06/2012 at 10:30 to 12:00. Amphi Claude Chappe, INSA de Lyon
URL : https://liris.cnrs.fr/seminaire/seminaires-mensuels/seminaires-mensuels
Informations contact : S. Servigne et G. Damiand. guillaume.damiand@liris.cnrs.fr. +33 (0)4.72.43.26.62.
Le premier ouvrage de référence de la théorie des treillis est la première édition du livre de Birkhoff en 1940. Cependant, la notion de treillis a été introduite dès la fin du 19ème siècle comme une structure algébrique munie de deux opérateurs appelés borne inférieure et borne supérieure.Depuis les années 2000, l'émergence de l'analyse de concepts formels (FCA) dans divers domaines de l'informatique, que ce soit en extraction et représentation des connaissances, dans les domaines des ontologies ou encore des bases de données, a mis en avant les structures de treillis des concepts et de treillis de fermés. L'émergence de cette structure de treillis s'explique à la fois par la part grandissante de l'informatique dans la plupart des champs disciplinaires, ce qui conduit à la production de données en quantité de plus en plus importante ; mais également par la montée en puissance des ordinateurs qui, bien que la taille du treillis puisse être exponentielle en fonction des données dans le pire des cas, rend possible le développement d'un grand nombre d'applications le concernant. La taille du treillis reste cependant raisonnable en pratique, et la nécessité d'algorithmes efficaces pour manipuler ces structures est un défi majeur.
Dans un cadre applicatif, une exploitation efficace du jeu algorithmique existant pour manipuler ces structures nécessite cependant une bonne connaissance du formalisme et des propriétés structurelles de la théorie des treillis afin d'identifier les outils algorithmiques adaptés pour un problème donné. Ce séminaire a pour objectif de présenter les concepts de base de la théorie des treillis, ainsi que les principaux algorithmes de génération des objets qui la composent. Quelques exemples d'utilisation en classification et représentation des connaissances seront également présentés.