Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation - Archive ouverte HAL Access content directly
Conference Papers Year :

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

(1)
1
Bruno Salvy

Abstract

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
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
57 View
87 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More