Première partie
5
Cadre conceptuel et théorique
6
Chapitre 2
Généralités sur la théorie
des treillis
C
E chapitre a pour but d'introduire les éléments
de base de la théorie des treillis, et s'organise de la manière
suivante : La section 2.1 présente un bref historique de la
théorie de treillis. La section 2.2 pose les définitions
algébrique et ordinale d'un treillis qui introduisent toutes deux la
notion de borne superieure et borne inferieure (section 2.2.1). La
théorie des treillis repose en partie sur l'existence
d'éléments particuliers d'un treillis que sont ses
éléments irréductibles qui décrivent la structure
même du treillis, et servent à en définir ses
générateurs minimaux (section 2.2.2). C'est sur la base des
éléments irréductibles que se définissent des
représentations d'un treillis qui contiennent l'information
nécessaire à sa reconstruction. Il sera introduit
également, dans cette section, la table d'un treillis ainsi que son
graphe de dépendance (section 2.2.3)
La section 2.3 introduit la représentation d'un
treillis sous forme ensembliste par une famille de parties d'un ensemble S,
stable par intersection et contenant S lui-même. Cette
représentation permet ainsi de manipuler de façon
équivalente un treillis sous sa forme algébrique, ordinale ou
ensembliste, car tout treillis est représentable par un treillis de
fermés (section 2.3.1). Un treillis de fermés est classiquement
associé à un système de fermeture, ensemble muni d'un
opérateur de fermeture, et l'apport principal de cette
représentation ensembliste reside dans le lien unissant treillis et
système de fermeture (section 2.3.2). En effet, tout treillis
étant représentable par un treillis de fermés, il l'est
également par un système de fermeture.
Le système de fermeture étant un ensemble muni
d'un opérateur de fermeture est utilisé, non seulement dans le
treillis des concepts (section 2.4.1) mais aussi dans le treillis de Galois
(section 2.4.2) qui est présenté comme une
généralisation du treillis des concepts à des
données plus complexes pour lesquelles il existe une connexion de
Galois. Ce deux notions réunit feront l'objet de la section 2.4.
2.1 Origine de la théorie des treillis
La notion de treillis définie comme une structure
algébrique munie de deux opérateurs appelés borne
inférieur et borne supérieur a été introduit par
Dedekind et Ernest Schöder, puis oubliée. Elle a été
redécouverte et développée au 20e siècle
sous diverses formes et terminologies entre 1928 et 1936 dans les travaux de
Merger, Klein, Stone, Garrett Birkhoff, Oystein Öre ou encore Von Newman.
L'introduction d'un treillis sous forme ordinale, structure ordonnée
définie par l'existence d'élé-
7
ments particuliers appelés bornes superieures et
inferieures, trouve son origine dans les axiomatiques des treillis
booléens dues à Pierce en 1880 ou à Huntington. Le terme
de treillis a, quant à lui, été proposé
par Birkhoff lors du premier symposium sur la structure de treillis en 1938,
pour être finalement repris dans son ouvrage de référence
« G. Birkhoff. Lattice theory. American Mathematical society,
1st edition, 1967 ». De nombreux ouvrages sur la
théorie de treillis portent sur la définition ordinale, en
particulier celui de Davey et Priestley ou encore de Grätzer.[2]
Un resultat fondamental de la théorie des treillis se
constitue, selon Karell Ber-tet[1], autour d'un résultat principal qui
établit que tout treillis fini est isomorphe au treillis de Galois ou
treillis de concepts de sa table. Barbut et Monjardet introduisent ainsi le
terme de treillis de Galois, alors que le terme de correspondance de Galois a
quant à lui été introduit par Öre en 1944. Plusieurs
travaux font apparaître la notion d'éléments
irréductibles d'un treillis qui permettent par exemple de
caractériser certaines classes de treillis, ou encore d'en concevoir des
représentations compactes du treillis.
Le treillis des concepts a été introduit dans
les années 1980 par Wille dans le cadre de l'Analyse Formelle des
Concepts( AFC) avec un ouvrage de référence dantant de 1999,
« Formal Concept Analysis, Mathematical foundations. Spriger Verlag,
Berlin, 1999 ». L'AFC est une approche à la représentation
des connaissances en pleine emérgence dans les années 90 qui
définit le treillis des concepts à partir de données
binaires de types Objet x attributs. L'émergence du treillis des
concepts ces dernieres années 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 recente 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.[1]
| 
