Random generation of combinatorial structures: Boltzmann samplers and beyond
Résumé
The Boltzmann model for the random generation of ''decomposable'' combinatorial structures is a set of techniques that allows for efficient random sampling algorithms for a large class of families of discrete objects. The usual requirement of sampling uniformly from the set of objects of a given size is somehow relaxed, though uniformity among objects of each size is still ensured. Generating functions, rather than the enumeration sequences they are based on, are the crucial ingredient. We give a brief description of the general theory, as well as a number of newer developments.
Le modèle de Boltzmann pour la génération aléatoire de structures "décomposables" est un ensemble de techniques qui fournissent des algorithmes de tirage aléatoire pour une grande famille de classes d'objets discrets. L'exigence classique de génération uniforme parmi les objets d'une taille donnée est quelque peu relaxée, bien que l'équiprobabilité des objets de chaque taille soit préservée. Les séries génératrices, plutôt que les suites d'énumération sur lesquelles elles sont basées, sont l'ingrédient crucial. Nous donnons une brève description de la théorie générale, ainsi que quelques développements plus récents.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...