Résumé : On étudie en combinatoire les objets munis d'une taille (la taille dans le cadre informatique peut se traduire par exemple par la mémoire occupée par l'objet). On appelle classe combinatoire un ensemble d'objets qui pour toute taille possède un nombre fini d'éléments. On peut par exemple considérer les textes régis par une certaine grammaire, dans ce cas la taille est le nombre de caractères, ou des arbres avec comme taille le nombre de nœuds. Une méthode naturelle pour décrire les classes, la méthode symbolique, consiste à décomposer les objets en sous-objets plus élémentaires à l'aide d'opérateurs (tels que l'union disjointe, le produit cartésien,...). On peut ensuite traduire ces décompositions sur des séries formelles. Le premier volet de résultats présentés dans cette thèse traite de la méthode symbolique et de son utilisation. On y présente des résultats asymptotiques sur des modèles d'arbres croissants issus de la théorie de la concurrence, puis une discussion sur comment décomposer certains opérateurs en réplications élémentaires. Le deuxième volet de résultats s'intéresse au sujet de la génération aléatoire uniforme d'objets dans une classe donnée. On montre tout d'abord comment générer des structures croissantes en adaptant les méthodes de génération récursive classiques aux opérateurs de produit croissant. On présente ensuite des résultats sur la génération de Boltzmann, avec une comparaison quantitative de deux méthodes, puis une extension permettant de conserver les propriétés d'uniformité de la génération en utilisant des approximations.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr