Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

« Arbres booléens aléatoires et urnes de Pólya : approches combinatoire et probabiliste » par Cécile Mailler

Présentée par : Cécile Mailler Discipline : mathématiques appliquées et applications des mathématiques Laboratoire : LMV

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.
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. Nous étudions dans la seconde partie de ce mémoire des urnes de Pólya équilibrées, irréductibles et coefficients positifs. Le comportement asymptomatique d’une telle 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 les urnes à d couleurs.

Abstract :
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.
Informations complémentaires
Svante JANSON, Professeur des Universités, à l’Université d’Uppsala/Département de Mathématiques - Uppsala (Suède) - Rapporteur
Conrado MARTINEZ, Professeur des Universités, à l’Université Polytechnique de Catalunya/Département des Langues et Systèmes Informatiques - Girona (Espagne) - Rapporteur
Brigitte CHAUVIN, Professeure des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire de Mathématiques de Versailles (LMV) - Versailles - Directrice de thèse
Danièle GARDY, Professeure des Universités, à l’Université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système, Modélisation (PRISM) - Versailles - Directrice de thèse
Dominique BARTH, Professeur des Universités, à l’université de Versailles Saint-Quentin-en-Yvelines/Laboratoire Parallélisme, Réseaux, Système, Modélisation (PRISM) - Versailles - Examinateur
Philippe CHASSAING, Professeur des Universités, à l’Université Henri Poincaré - Vandœuvre-lès-Nancy - Examinateur
Julien CLEMENT, Chargé de Recherche, Habilité à Diriger des Recherches, à l’Université de Caen/Département d’Informatique - Caen - Examinateur
Alain ROUAULT, Professeur des Universités, à l’université de Versailles Saint-Quentin-en-Yvelines/Laboratoire de Mathématiques de Versailles (LMV) - Versailles - Examinateur
Contact :
dredval service FED :