Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

Bruno Salvy

Résumé

In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic Combinatorics, as described in the book by Flajolet & Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial defini- tions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation. The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2018-1.pdf (402.32 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01926094 , version 1 (19-11-2018)

Identifiants

Citer

Bruno Salvy. Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation. STACS 2018 - 35th Symposium on Theoretical Aspects of Computer Science, Feb 2018, Caen, France. ⟨10.4230/LIPIcs.STACS.2018.1⟩. ⟨hal-01926094⟩
65 Consultations
120 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More