392170 Algorithmic stochastics (V) (WiSe 2026/2027)

Several complex problems arising from biology and computer science (e.g., sequence alignment, gene finding, inference for population sequence data) cannot be solved efficiently and optimally at the same time using deterministic methods. In such cases stochastic methods can be used to make computations feasible and still provide good results.

Building on the foundations of probability theory and statistics, this course lays the basis for stochastic computing (i.e., representation of distributions in the computer, computations with small probabilities, efficient generation of random numbers with given distribution, test of the quality of random number generators). As an important tool, Markov chain Monte Carlo (MCMC) methods are presented via examples (Metropolis-Hastings, Gibbs sampling). Importance sampling methods and simulation of rare events are discussed as well.

Lecture notes for the full course are available via the Moodle page of the course. Additional comments can be found in the course syllabus that is also available via Moodle.

Requirements for participation, required level

Basic knowledge of probability theory (stochastics) on the level taught in the Computer Science Bachelor's probability theory and statistics lecture (24-M-INF4 Mathematik für Informatik 4) is strongly recommended. This includes (discrete and continuous probability) distributions, random variables, independence, expectations, variance, joint and conditional distributions.

A longer list of topics (along with material [in German] and literature recommendations [in English and German]) is available on the Moodle page of the course. A primer on the basic probability theory topics [in English] is contained in the appendix of the lecture notes (also available via Moodle).

Bibliography

The main texts can be found in the syllabus (available via Moodle). A longer list can be found in the lecture notes.