Prof. Dr. Achim Klenke
Institut für Mathematik
Fachbereich Physik, Mathematik und Informatik
Johannes Gutenberg-Universität
Staudingerweg 9
55099 Mainz
Tel. 06131 39-22829
Fax 06131 39-20916
E-Mail: 
Vorlesung: Stochastische Algorithmen
Sommer 2010
|
Zeit: |
Do 14-16 |
|
Ort: |
05-136 |
|
Beginn: |
15. April 2010 |
|
Übungen: |
keine |
Die Vorlesung wendet sich an Studierende der Fachrichtung Mathematik, die
mindestens eine Vorlesung über Stochastik gehört haben.
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,
- David Aldous and
James Propp, editors.
Microsurveys in discrete probability,
American Mathematical Society, - Rajeev Motwani
and Prabhakar Raghavan.
Randomized algorithms
Cambridge University Press,
a.k. 05.02.2010