Relatore : Fabrice KORDON

Co-relazione : PAVIOT-ADET Emmanuel

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

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.

Pubblicazioni 2006-2016