Research activities Publications: Others: Master thesis PhD thesis Uniform random generation is a central issue in combinatorics. Under the Boltzmann model, combinatorial structures are generated with a randomly varying size, which allows for the design of particularly efficient samplers. The aim of this thesis is to make this sampling method effective for a large number of decomposable combinatorial classes via an automatization of all the treatments involved in the design of the samplers. The first part is dedicated to the study of sampling algorithms. We complete the initial dictionary of Boltzmann samplers in order to support unlabelled classes. Those generic algorithms are fully detailed, proved and illustrated by classical examples coming from combinatorics. Experimental data are given to emphasize the efficiency of those samplers. An application to the random generation of plane partitions concludes this study. In the framework of Boltzmann method, the samplers are parametrized with a numerical value that controls the expected size of the generated structures. The samplers uniformity relies on an oracle function that returns, for any combinatorial class, the value of its generating function at a given point. The second part of this thesis introduces a method to automatically and efficiently compute this oracle, using a numerical Newton iteration. The validity of this approach is based on the convergence of Newton iteration on combinatorial structures. This iteration is then lifted to the level of generating series and finally to numerical values. In addition, the iteration on series leads to a quasi-optimal algorithm to compute the first terms of the counting series. Slides Software: NewtonGF package for Maple (new!) Tools for generating functions based on the combinatorial Newton iteration: Fast enumeration of random structures Boltzmann sampler's oracle Numerical radius of convergence. Maple worksheets for some simple Boltzmann samplers (new!) Contains: Boltzmann_BinaryTrees.mw Boltzmann_CayleyTrees.mw Boltzmann_SetPartitions.mw Boltzmann_Surjections.mw Talks: Algorithms Project's Seminar, INRIA - november 14, 2005 SPIRAL's Team Seminar, LIP6 - november 18, 2005 Journées Arbres et Cartes, Bordeaux - december 2, 2005 Algorithms and combinatorics' seminar, LIAFA - february 14, 2006 ALEA06, Luminy - march 6, 2006 Summer school on Algorithmics and Computer Algebra, Bordeaux - may 15, 2006 GASCOM06, Dijon - september 14, 2006 ALEA07, Luminy - march 23, 2007 Algorithms Project's Seminar, INRIA - december 10, 2007 (long version) ANR GAMMA, LIP6 - october 3, 2007 ForTesSE team's seminar, LRI (Univ. Orsay) - january 9, 2008 Seminar of the Gaspard-Monge Institute (Univ. Marne-la-Vallée) - march 25, 2008 International Workshop on Applied Probability, University of Compiegne (France) - july 10, 2008 (short version) Seminar of the OCAD team, LIPN (Univ. Paris XIII) - march 3, 2009 TIFR, Mumbai, India - december 13, 2010 (new version) Demo: Random sampling of RANs and plane partitions (french) with A. Darrasse and M. Soria LIP6 evaluation - january 17, 2008 ALEA08, Luminy - march 14, 2008 Algorithms Project's Seminar, INRIA - june 2, 2008 (long version, english) Fifth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Blaubeuren, Germany - september 22-26, 2008 (short version, english) Groupe de travail de l'équipe combinatoire, LIX - january 14, 2009 (another long version) Journées de Combinatoire de Bordeaux - february 4, 2009 ANR GAMMA, LIP6 - december 11, 2008 (Maple worksheets) FSTTCS 2010, Chennai, India - december 17, 2010 LIGM, Université Paris-Est Marne-la-Vallée - december 2011

Back to main page