1 Search Results for "Salvy, Bruno"

Document
DOI: 10.4230/LIPIcs.STACS.2018.1
Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

Authors: Bruno Salvy

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

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.
Cite as

Bruno Salvy. Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{salvy:LIPIcs.STACS.2018.1,
  author =	{Salvy, Bruno},
  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 =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.1},
  URN =		{urn:nbn:de:0030-drops-85352},
  doi =		{10.4230/LIPIcs.STACS.2018.1},
  annote =	{Keywords: Analytic Combinatorics, Generating Functions, Random Generation}
}
  • Refine by Author
  • 1 Salvy, Bruno

  • Refine by Classification

  • Refine by Keyword
  • 1 Analytic Combinatorics
  • 1 Generating Functions
  • 1 Random Generation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact