soutenance de thèse de Carine Pivoteau / le 3 décembre à 14h30

Bonsoir à tous,

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

"Génération aléatoire de structures combinatoires :
méthode de Boltzmann effective."

qui aura lieu le 3 décembre 2008 à 14h30 en salle 549, au cinquième
étage du LIP6, situé au 104 Av. du Pdt Kennedy, 75016 Paris.

Vous êtes également invités au traditionnel pot qui suivra (même
bâtiment, salle 847, 8ème étage).

---------------------------------------------------------------------------------
Composition du jury:

François Bergeron, Lacim, UQAM (rapporteur)
Alain Denise, LRI, Université de Paris Sud (rapporteur)
Philippe Flajolet, INRIA Rocquencourt (examinateur)
Patrick Gallinari, LIP6, UPMC (examinateur)
Jacques Malenfant, LIP6, UPMC (examinateur)
Conrado Martínez, Université Polytechnique de Catalogne (examinateur)
Bruno Salvy, INRIA Rocquencourt (examinateur)
Michèle Soria, LIP6, UPMC (directrice)

---------------------------------------------------------------------------------
Résumé de la thèse:

La génération aléatoire uniforme est un problème central en combinatoire
algorithmique.Dans le modèle de Boltzmann, les structures combinatoires
sont engendrées avec une taille variable ce qui permet de concevoir des
générateurs efficaces.

Cette thèse vise à rendre effective cette méthode de génération
aléatoire pour un grand nombre de classes combinatoires décomposables,
en automatisant l'ensemble des traitements intervenant dans la
conception des générateurs de Boltzmann.

La première partie est consacrée à l'étude des algorithmes de
génération. Nous commençons par compléter le dictionnaire initial des
générateurs de Boltzmann afin de pouvoir traiter les classes
combinatoires non étiquetées. Ces algorithmes génériques sont présentés
en détails, validés par des preuves et illustrés sur des exemples
classiques en combinatoire. Des données expérimentales viennent
également souligner les performances de ces générateurs; une application
à la génération aléatoire de partitions planes complète cette étude.

Dans la méthode de Boltzmann, les générateurs sont paramétrés par une
valeur numérique x qui contrôle l'espérance de la taille des
structures engendrées. L'uniformité de la génération repose sur une
fonction d'oracle qui associe à toute classe combinatoire la valeur de
sa série génératrice en x.
La seconde partie de ce mémoire présente une méthode de calcul
automatique et efficace de cet oracle, par itération de Newton
numérique. La validité de cette méthode repose sur la convergence de
l'itération de Newton pour les structures combinatoires. Cette itération
est ensuite relevée au niveau des séries formelles puis au niveau des
valeurs numériques.
L'itération sur les séries conduit par ailleurs à un algorithme de
complexité quasi-optimale pour calculer les premiers coefficients des
séries de dénombrement.
---------------------------------------------------------------------------------

Cordialement,

Carine Pivoteau.

======================
Informations pratiques
======================
Adresse :
Site Passy-Kennedy
LIP6
104 avenue du Président Kennedy
75016 Paris

Comment venir au LIP6 (site de Kennedy) :
http://www.lip6.fr/fr/informations/comment.php

Pour les personnes extérieures, vous devrez vous présenter à l'accueil
afin de pouvoir accéder à la salle de soutenance. Si vous avez le
moindre problème d'accès, vous pourrez me contacter au : 01 44 27 88 25.