Autour de la génération aléatoire sous modèle de Boltzmann
This dissertation's main topic is analytic combinatorics and its underlying algorithmic. It focuses on uniformly sampling random combinatoric structures, in particular through the Boltzmann model. With this model, the size of combinatoric structures is distributed according to a law well-known in statistical physics for describing the free energy of systems, but the usual constraint, that the generated objects be of a given size, is relaxed. This allows for very efficient samplers. This dissertation presents random sampling through the Boltzmann model as introduced by P. Duchon, P. Flajolet, G. Louchard and G. Schaeffer in 2004, and the several possible extensions and additions to this model. We have chosen to mention the addition of colored classes, of multi-parameterized classes, of Dirichlet classes with a multiplicative size, of differential classes, and of construction of the Hadamard product. The last part details a number of application of these extensions in different domains spanning statistical physics (see the generation of plane partitions), random sampling of tilings, random sampling of ordered structures.
Phd defence : 12/03/2010
Jury members :
François Bergeron, Professeur, Université du Québec, Montréal, Canada [rapporteur]Philippe Duchon, Professeur, Université Bordeaux 1, Bordeaux
Philippe Flajolet, DR INRIA, INRIA Rocquencourt, Le Chesnay [rapporteur]
Pierre Fraigniaud, DR CNRS, Université Paris Diderot, Paris
Bernhard Gittenberger, Institut für Diskrete Mathematik und Geometrie, Wien, Austria
Nicolas Schabanel, DR CNRS, Université Paris Diderot, Paris
Gilles Schaeffer, DR CNRS, École Polytechnique, Palaiseau [rapporteur]
Michèle Soria, Professeur, UPMC, Paris
Departure date : 12/03/2010