Random generation of combinatorial structures: Boltzmann samplers and beyond

Philippe Duchon 1, 2
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : 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.
Type de document :
Communication dans un congrès
Jain, S. and Creasey, R.R. and Himmelspach, J. and White, K.P. and Fu, M. Winter Simulation Conference, Dec 2011, Phoenix, United States. 2011, 〈http://wintersim.org/program.htm〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00654267
Contributeur : Philippe Duchon <>
Soumis le : mercredi 21 décembre 2011 - 14:21:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 22 mars 2012 - 02:26:49

Fichiers

Boltzmann_WSC11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00654267, version 1
  • ARXIV : 1112.5071

Collections

Citation

Philippe Duchon. Random generation of combinatorial structures: Boltzmann samplers and beyond. Jain, S. and Creasey, R.R. and Himmelspach, J. and White, K.P. and Fu, M. Winter Simulation Conference, Dec 2011, Phoenix, United States. 2011, 〈http://wintersim.org/program.htm〉. 〈hal-00654267〉

Partager

Métriques

Consultations de la notice

241

Téléchargements de fichiers

163