La soutenance de thèse de Cyril Banderier aura lieu à Paris, à Jussieu, le lundi 25 juin 2001, dans le bâtiment 41 (voir plan ci-dessus, welcome into the matrix!), au deuxième étage, salle 203-205, à 17h30.
J'ai le plaisir de vous y convier, ainsi qu'à la collation qui devrait suivre !
Si vous pensez venir ou si vous souhaitez un renseignement complémentaire, envoyez-moi un petit mail.
Résumé de la thèse : Combinatoire analytique des chemins et des cartes
Directeur de thèse : Philippe Flajolet
Jury : Mireille Bousquet-Mélou, Brigitte Chauvin, Dominique Gouyou-Beauchamps, Guy
Louchard, Renzo Pinzani, Michèle Soria, Brigitte Vallée.
Cette thèse, à cheval entre mathématiques et informatique théorique, étudie, d'une part, divers modèles combinatoires et probabilistes de marches sur les entiers et, d'autre part, la multi-connectivité dans les cartes planaires. Nous montrons comment expliciter les séries génératrices sous-jacentes et comment en déduire l'asymptotique des dénombrements ainsi que les lois limites de divers paramètres.
Les marches aléatoires que nous considérons sont de trois types :
(i) des marches sur les entiers homogènes en temps et en espace (une
généralisation des chemins de Dyck),
(ii) des marches sur les entiers non homogènes en espace (un
ensemble infini de règles de récriture sur les entiers qui
correspond à une classe d'arbres étiquetés utilisée pour faire
de la génération aléatoire uniforme),
(iii) des marches colorant aléatoirement les sommets d'un graphe fini (généralisation du problème du collectionneur de coupons).
L'asymptotique du dénombrement et de différents paramètres (e.g. altitude finale, passages par zéro) sont alors établies pour ces classes de marches.
Les cartes planaires sont une projection dans le plan de graphes dessinés sur la sphère. Nous montrerons en quoi des méthodes de cols coalescents permettent de préciser le phénomène de ``transition de phase'' qui survient lorsque l'on s'intéresse à la taille de la plus grande composante multi-connexe d'une carte aléatoire.
Au-delà de ces perspectives mathématiques, la quantification de l'aléa dans ces deux structures combinatoires de base (que sont les chemins et les cartes) joue un rôle clef en informatique théorique soit pour l'étude et/ou la représentation de structures de données, soit comme modèles pertinents de la complexité de nombreux algorithmes. Ce travail dégage aussi l'intérêt intrinsèque d'une méthode de résolution de certaines équations fonctionnelles (la méthode du noyau) et d'une méthode de cols coalescents aboutissant à des lois limites non gaussiennes (e.g. la loi d'Airy des cartes), susceptibles de nombreuses applications.