| Zeit: | Do 12-14 |
| Ort: | 05-136 |
| Beginn: | 21.04.2022 |
In der Vorlesung Stochastische Algorithmen wird die Wirkungsweise von Algorithmen, die mit Hilfe eines Zufallsmechanismus arbeiten, erläutert und mathematisch fundiert. Dabei geht es um Probleme wie das Mischen bzw. Sortieren von Spielkarten, das Heraussuchen eines optimalen Wertes aus einer sehr großen Menge (z. B. das Problem des Handlungsreisenden), die Konstruktion zufälliger Objekte mit einer gegebenen Verteilung (Zufallszahlen, Propp-Wilson-Algorithmus) und so weiter.
Eines der stochastischen Konzepte, die behandelt werden sollen, sind Markovketten und die Geschwindigkeit ihrer Konvergenz in ihr Gleichgewicht, die man mit Hilfe von Frobenius-Eigenwerten und Spektrallücken abschätzen kann.
Voraussetzung für den Besuch dieser Vorlesung sind Kenntnisse in der elementaren Wahrscheinlichkeitstheorie, wie sie etwa im Modul Grundlagen der Stochastik vermittelt werden. Literatur David Aldous, Persi Diaconis, Joel Spencer, and J. Michael Steele, editors Discrete probability and algorithms, Springer-Verlag, New York, 1995 David Aldous and James Propp, editors. Microsurveys in discrete probability, American Mathematical Society, Providence, RI, 1998. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms Cambridge University Press, Cambridge, 1995.