Random generation of combinatorial structures: Boltzmann samplers and beyond

Abstract

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.