Soutenance de thèse d'Alexis Darrasse

Bonjour à tous,

J'ai le plaisir de vous annoncer la soutenance de ma thèse intitulée

« Structures arborescentes complexes :
analyse combinatoire, génération aléatoire et applications. »

qui aura lieu le 26 janvier 2010 à 10h30 en salle 203-205 du bâtiment 41
au campus Jussieu.

Vous êtes également invités au pot qui suivra (même salle).

Cordialement,
Alexis Darrasse

--------------------------------------------------------------------------------

Résumé de la thèse :

Ce travail a pour but l'application des techniques d'analyse et de
génération aléatoire de la combinatoire analytique à des problèmes issus
de domaines variés où apparaissent des structures arborescentes.

Dans un premier temps, nous étudions les propriétés des k-arbres, une
famille de graphes qui généralise celle des arbres. Les k-arbres jouent
un rôle central en algorithmique des graphes et apparaissent aussi (sous
le nom de réseaux apolloniens aléatoires ou triangulations en pile)
comme modèle pour les graphes de terrain. Notre contribution consiste en
une bijection entre k-arbres et une famille simple d'arbres et son
utilisation pour analyser certaines propriétés des k-arbres sous la
distribution uniforme: distribution des degrés en loi de puissance avec
chute exponentielle, distance moyenne en racine carrée de la taille et
profil qui suit une loi de Rayleigh.

La seconde partie a pour objet la génération aléatoire de structures
arborescentes avec la méthode de Boltzmann. Nous avons mis en place un
cadre générique et efficace que nous avons appliqué à la génération de
données issues de plusieurs domaines logiciels : instances de types de
données algébriques, instances de méta-modèles et de documents XML selon
une grammaire. La complexité linéaire des algorithmes de génération rend
ces outils bien adaptés aux tests de robustesse et de performance.

--------------------------------------------------------------------------------

Rapporteurs :

Hsien-Kuei Hwang
Gilles Schaeffer

--------------------------------------------------------------------------------

Jury :

Frédéric Chyzak
Philippe Duchon
Philippe Flajolet
Mihyun Kang
Matthieu Latapy
Christian Queinnec
Gilles Schaeffer
Michèle Soria, directrice