Cécile Mailler soutient sa thèse intituée « Arbres booléens aléatoires et urnes de Pólya : approches combinatoire et probabiliste » le jeudi 17 octobre 2013.
Résumé : Cette thèse étudie deux objets aléatoires discrets : les arbres booléens aléatoires et les urnes de Pólya. Ces deux objets, tous deux en lien avec l’informatique fondamentale, sont étudiés dans ce mémoire via des méthodes de combinatoire analytique et de probabilités.
Les arbres booléens sont des arbres étiquetés de façon à représenter des expressions booléennes. Chaque arbre booléen représente donc une fonction booléenne. Dans la première partie de cette thèse, nous définirons et comparerons plusieurs distributions de probabilité sur l’ensemble des fonctions booléennes via leur représentation par des arbres booléens. Nous verrons que toutes ces distributions chargent préférentiellement les fonctions booléennes de faible complexité, et que certaines d’entre elles sont dégénérées au sens où elles ne chargent qu’un petit nombre de fonctions booléennes. L’étude de ces modèles se fait principalement via des outils de combinatoire analytique, mais nous utilisons aussi des méthodes probabilistes, comme le plongement en temps continu, ou poissonisation, pour certaines de ces distributions.
Une urne de Pólya est un processus discret aléatoire qui modélise, en particulier, de nombreux objets issus de l’informatique comme les arbres m-aires de recherche, les arbres 2-3, les AVL, entre autres. Nous étudions dans la seconde partie de ce mémoire des urnes de Pólya équilibrées, irréductibles et à coefficients positifs. Le comportement asymptotique d’une urne, ainsi que celui de son plongement en temps continu, font intervenir des variables aléatoires W assez méconnues à ce jour. Nous étudions ces variables aléatoires W via la structure arborescente de l’urne et montrons qu’elles sont solution de systèmes d’équations en loi, ce qui nous permet notamment d’établir que ces variables aléatoires sont déterminées par leurs moments, et surtout d’aborder cette étude aussi bien pour des urnes à deux couleurs que pour des urnes à d couleurs.