Combinatorics of trees under increasing labellings : asymptotics, bijections and algorithms

Source abstract

Combinatoire des arbres sous étiquetages croissants : Asymptotiques, bijections et algorithmes Dans cette thèse nous étudions des classes d’arbres étiquetés selon différents modèles d’étiquetages croissants. Ces arbres sont utiles dans la modélisation de nombreux processus. Nous adoptons dans nos recherches différents points de vues complémentaires (combinatoire, probabiliste ou informatique) afin d’enrichir les résultats connus sur les arbres croissants classiques et de proposer de nouvelles classes d’arbres moins contraints que les modèles existants dans la littérature. Nous proposons plusieurs nouveaux modèles d’arbres, dans l’idée de pouvoir représenter un processus d’évolution où l’historique des évolutions est enregistré. Pour ces nouvelles classes d’arbres nous montrons leur liens étroits avec des objets classiques en combinatoire comme les permutations, les partitions d’ensemble, ainsi que les graphes. Nous les étudions également de façon plus détaillée en terme probabiliste pour mieux comprendre la forme typique des grandes structures. Ainsi, nous définissons un processus d’évolution paramétrable qui recouvre ces nouvelles classes d’arbres ainsi que d’autres classes encore plus générales. Cela nous mène à définir plusieurs nouveaux modèles d’étiquetages croissants sur les arbres. Nous réussissons aussi à avoir des formes universelles pour l’énumération asymptotique des classes d’arbres issues de ce processus d’évolution en utilisant notamment des idées empruntées aux sommations de Borel. Du côté algorithmique l’étude des structures arborescentes nécessite la génération et la mémorisation d’arbres de grandes taille ce qui nous mène à élaborer des algorithmes degénération aléatoire uniforme efficaces qui nous permettent de faire des simulations non biaisées sur des arbres de grandes taille. Du fait que nous sommes en mesure d’engendrer des arbres grands, une autre problématique apparaît. Celle-ci concerne leur représentation en mémoire. En particulier, nous nous sommes aperçus qu’une compression efficace serait intéressante afin de manipuler et étudier expérimentalement ces structures arborescentes. Notre étude porte alors sur le taux compression moyen des arbres croissants classiques et elle nous permet de définir une nouvelle structure de données compactifiée pour les arbres binaires de recherche