(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Analytic Combinatorics

Markus Nebel
Faculty of Technology / AG Algorithmik und Bioinformatik
University of Bielefeld

Tuesday, 21 February, 2017 at 14:15
IMADA's Seminar Room

ABSTRACT

Analytic combinatorics is one of the many techniques of counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions by so-called symbolic method. Here close ties to formal language theory exist since the structure of combinatorial objects is described using a special kind of grammar. Techniques from complex analysis are then used to get precise asymptotics. Applications beyond enumeration are the quantitative study of parameters like path-length and height of trees (and many more motivated, e.g., by the average-case analysis of algorithms) where expectations and limiting distributions can be derived. Last but not least, analytic combinatorics allows for the random generation of combinatorial objects. In this course we will cover the most important aspects of analytic combinatorics. Starting with the symbolic method we will discuss various examples of how to find generating functions for non-trivial objects. Afterwards we will see, how precise asymptotics for their coefficients can be derived, even in the case where no close-form representation of the generating functions is known. We will continue by discussing the analysis of parameters and the random generation of objects like RNA structures and other types of molecules. The focus of the course will be on the application of the methods not on proving their correctness. A detailed treatment can be found at http://algo.inria.fr/flajolet/Publications/book.pdf [algo.inria.fr]

Host:


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle