Soutenance de thèse d'Alban Linard

Bonjour,

j'ai le plaisir de vous inviter à la soutenance de ma thèse, ainsi
qu'au pot ardéchois qui suivra.

=====
Titre
=====
«Sémantique paramétrable des Diagrammes de Décision : une démarche
vers l'unification»

====
Lieu
====
La soutenance aura lieu le mardi 29 septembre à 14h au LIP6 (Site
Passy-Kennedy), en salle 847. Les indications pour se rendre au LIP6
se trouvent à cette adresse : http://www.lip6.fr/informations/comment.php

====
Jury
====
La thèse sera soutenue devant le jury composé de :

M. Didier Buchs (Université de Genève) - Rapporteur
M. Jean-Michel Couvreur (Université d'Orléans) - Rapporteur
Mme Béatrice Bérard (Université Pierre et Marie Curie) -
Examinateur
M. Olivier H. Roux (IUT de Nantes) -
Examinateur
M. Alexandre Duret-Lutz (EPITA) -
Examinateur
M. Fabrice Kordon (Université Pierre et Marie Curie) - Directeur
M. Emmanuel Paviot-Adet (Université Paris Descartes) - Encadrant

======
Résumé
======
Les Diagrammes de Décision sont des structures de données compactes,
qui représentent efficacement des ensembles de données de taille
importante sous forme d'un graphe, dont les parties communes sont
partagées. Cette efficacité se traduit, lors de la manipulation de ces
structures, aussi bien dans la mémoire consommée que dans le temps
d'exécution. Elle est toutefois dépendante des données représentées :
le gain peut varier en pratique de très faible à exponentiel. Ainsi,
des techniques récentes ont permis d'atteindre plus de 10^2500 états
différents dans 1 Go de mémoire en environ une minute.

De nombreuses variantes ont été définies depuis le début des années 90
à partir des Diagrammes de Décision Binaire (BDD), à l'origine de ces
structures de données. Les évolutions sont très variées, allant
d'optimisations de la structure à l'extension hiérarchique des
Diagrammes de Décision.
Il existe ainsi actuellement plusieurs dizaines de variantes. Malgré
leur utilisation dans de nombreux domaines, les Diagrammes de Décision
sont à ce jour différentes structures, qui évoluent indépendamment les
unes des autres. Il n'existe pas de théorie unifiée, ce qui a certes
permis des évolutions rapides de ces structures, mais est un frein à
la réutilisation des résultats obtenus dans le domaine.

Nous proposons un cadre unifiant la majeure partie des Diagrammes de
Décision existants à l'heure actuelle, le grand nombre de variantes ne
permettant pas d'espérer tous les couvrir. Nous montrons que cette
généralisation se fait sans perte d'efficacité, en fournissant un
moyen de récupérer les optimisations de structure définies dans
certains évolutions. De plus, en important ces optimisations dans le
cadre unifié, nous permettons leur application pour certains
Diagrammes de Décision pour lesquels elles n'étaient jusqu'à présent
pas définies. L'unification réalisée permet de mélanger, au sein d'un
même Diagramme de Décision, les spécificités de variantes jusque là
séparées.

========
Abstract
========
Decision Diagrams are compact data structures. They represent
efficiently huge data sets as graphs, where common parts are shared.
Gains in efficiency occur on both memory and time used for
computations using these structures. However, it depends on the data
represented, and varies from almost no gain to an exponential one.
With modern techniques, state spaces containing more than 10^2500
different states have been generated in one minute, using only 1 Gbyte
of memory.

A great number of Decision Diagrams, deriving from Binary Decision
Diagrams (BDDs), have been defined during the last 20 years. Their
differences vary from cover optimizations of the structure to its
hierarchical extension. Nowadays, dozens of Decision Diagram kinds
exist. They are used in many domains, but each one is a different data
structure, that evolves unrelated to the others. No unified theory
exists. Its lack helped creating a lot of new Decision Diagrams, but
prevents reuse of results in this domain.

We propose a unifying framework, that covers most of existing Decision
Diagrams. However, we do not cover all the variations, beause of their
great number. We show that this generalization does not imply a loss
in efficiency, by extending the structural optimizations of the
Decision Diagrams. This generalization brings these optimizations to
kinds that did not define them. Moreover, the unified framework
enables mixing several disjoint kinds of Decision Diagrams in one
structure.

Cordialement,
Alban Linard

--
Université Pierre et Marie Curie - UMR CNRS 7606
Laboratoire d'Informatique de Paris 6 / MoVe
Bureau 818
Tél: + 33 1 44 27 31 92
104 Avenue du Président Kennedy
75016 Paris - France