Description
Date depot: 1 janvier 1900
Titre: Génération aléatoire de structures ordonnées
Directrice de thèse:
Michèle SORIA (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
La génération aléatoire de structures combinatoires - mots et langages, arbres, graphes, et plus généralement objets construits à partir d'un système de règles-, est un domaine très riche de la combinatoire algorithmique. Le modèle de Boltzmann, dans lequel on attribue
à chaque objet un poids exponentiel (proportionel à x^n
pour un objet de taille n), s'est révélé très efficace pour la génération de structures définies par des systèmes de spécifications récursives qui couvrent une grande variété de types combinatoires classiques. La complexité linéaire des générateurs de Boltzmann permet de traiter des applications à très large échelle pour le test ou l'adéquation de modèles.
Les travaux actuels ont développé le modèle de Boltzmann et une algorithmique générique pour les constructions Suite, Ensemble, Cycle, Composition, dans les cas 'étiqueté' et 'non étiqueté', pour lesquels les spécifications se traduisent en systèmes algébriques avec opérateurs de Polya.
L'objectif de cette thèse est de travailler sur des constructions combinatoires
donnant lieu à des systèmes différentiels: c'est le cas par exemple des constructions
permettant de traiter des structures ordonnées, ou de constructions permettant de passer du cas étiqueté au cas non étiqueté. Il s'agit donc de développer la théorie de la génération aléatoire par modèle de Boltzmann dans ce cadre, et d'en explorer la puissance algorithmique avec différents modèles de calcul: calculs sur les réels exacts ou en multiprécision, calculs en binaire. Ce travail théorique s'accompagnera de développements logiciels : implantation d'une bibliothèque générique dans un système de calcul formel comme Maple, ainsi que d'optimisations spécifiques dans le cas d'applications particulières.
Doctorant.e: Roussel Olivier