PIVOTEAU Carine

PhD graduated
Team : APR
Departure date : 08/31/2009
https://lip6.fr/Carine.Pivoteau

Supervision : Michèle SORIA

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

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.

Defence : 12/03/2008

Jury members :

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

Departure date : 08/31/2009

2006-2012 Publications

Mentions légales
Site map