Skip to Main content Skip to Navigation
Conference papers

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

Bruno Salvy 1
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01926094
Contributor : Bruno Salvy <>
Submitted on : Monday, November 19, 2018 - 8:45:58 PM
Last modification on : Thursday, November 21, 2019 - 3:22:02 PM
Long-term archiving on: : Wednesday, February 20, 2019 - 4:35:20 PM

File

LIPIcs-STACS-2018-1.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

80

Files downloads

45