Nous abordons, par une modélisation à base de graphes, deux problèmes de structuration de données. Phylogénie: Nous utilisons la famille de graphes associée à une dissimilarité pour définir la notion nouvelle de distance triangulée, plus générale qu'une distance additive d'arbre. Nous proposons un algorithme d'ajustement de données à une distance triangulée par triangulation des graphes associés. Nous introduisons pour cela le concept nouveau de sous-triangulation maximale, afin de prendre en compte la sous-évaluation intrinsèque des données phylogénétiques. Nous procédons ensuite à une étude théorique complémentaire. Analyse Formelle de Concepts: Nous codons une relation binaire R et son treillis des concepts L(R) par un graphe non orienté co-biparti G(R). Nous montrons que les éléments de L(R) sont en bijection avec les séparateurs minimaux de G(R), et que les chaînes maximales de L(R) sont en bijection avec les triangulations minimales de G(R). Des procédés algorithmiques appliqués à G(R) trouvent ainsi leurs correspondants dans L(R). En particulier, des treillis de taille polynomiale peuvent être obtenus à partir de L(R), par plongement de G(R) dans un graphe faiblement triangulé. Nous mettons ensuite en évidence un ordre de domination sur les modules complets maximaux de G(R), domination qui s'hérite quand on parcourt une chaîne maximale de L(R). Une structure de données, la table de domination, gère dynamiquement les relations de domination. Nous utilisons cette table pour deux applications algorithmiques: - Mise à jour d'une sous-hiérarchie de Galois matérialisant une hiérarchie d'héritage orienté-objet; - Génération efficace d'un treillis des concepts.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00521946 |
| Date | 20 December 2002 |
| Creators | Sigayret, Alain |
| Publisher | Université Blaise Pascal - Clermont-Ferrand II |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0043 seconds