Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Salvy, Bruno http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-85352
URL:

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

pdf-format:


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 and Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions 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.

BibTeX - Entry

@InProceedings{salvy:LIPIcs:2018:8535,
  author =	{Bruno Salvy},
  title =	{{Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{1:1--1:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8535},
  URN =		{urn:nbn:de:0030-drops-85352},
  doi =		{10.4230/LIPIcs.STACS.2018.1},
  annote =	{Keywords: Analytic Combinatorics, Generating Functions, Random Generation}
}

Keywords: Analytic Combinatorics, Generating Functions, Random Generation
Seminar: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint Published by LZI