Stochastische Analyse von Algorithmen (WS 2022/23)
Zeit: Mo 12:15 - 14:00
Ort: SR 711 groß (Robert-Mayer-Str. 10)
Dozent: Prof. Dr. R. Neininger
Am Ende dieser Seite finden Sie eine Probeklausur.
Übungen (14 tägig): J. Ischebeck
Mo 10-12, SR 311 (Robert-Mayer Str. 10)
Mo 12-14, SR 903 (Robert-Mayer Str. 10)
Start der Übungen: 14.11.2022
Module:
BaM-STO-k
BaM-STO-gks, d.h. Spezialisierung in Stochastik (zusammen mit der Vorlesung Stochastische Prozesse und einem entsprechenden Seminar)
MaM-STO-k
M-MSAA (Master Informatik)
Thema
Aufbauend auf der Elementaren Stochastik (und z.T. den Stochastischen Prozessen) werden wir das Verhalten einiger
diskreter Strukturen, Algorithmen und Optimierungsprobleme stochastisch
untersucht. Die Probleme (z.B. Algorithmen) werden grundlegender Natur sein und
wir werden annehmen, dass ihre Eingaben zufällig sind.
Wir interessieren und für charakteristische Größen (z.B. Laufzeit), die
dann Zufallsvariable sind, deren Verteilung Information über das typische
Verhalten des Problems bzw. des Algorithmus liefert.
Geplante Themen sind: Einfache Irrfahren mit Anwendungen auf bin packing und
Catalan-Bäume, Heuristiken für das traveling salesman Problem, zufällige
Permutationen mit Anwendungen auf Binärsuchbäume, die Probabilistische Methode
mit Anwendungen auf zufällige Graphen, Galton-Watson-Prozesse mit Anwendungen auf
heuristische Suche, Entropie mit Anwendungen auf Lempel-Ziv Kodierung, sowie die Analyse
einiger randomisierter Algorithmen.
Prüfung
Bitte melden Sie sich im OLAT Kurs an, falls Sie an der Prüfung teilnehmen wollen: OLAT Kurs
Klausur am 6. Februar 2023, 12:15 Uhr im Hörsaal H IV (Jügelhaus). Die Zweitklausur am 27. März 2023, 10:15 Uhr im Hörsaal H IV (Jügelhaus).
Notenskala für die Klausur und Nachklausur
| Klausurpunkte |
Note Ba/Ma |
Note Lehramt |
| 0-3.5 |
5.0 |
0 |
| 4-5.5 |
5.0 |
1 |
| 6-7.5 |
5.0 |
2 |
| 8-9.5 |
5.0 |
3 |
| 10-11.5 |
5.0 |
4 |
| 12-12.5 |
4.0 |
5 |
| 13-13.5 |
3.7 |
6 |
| 14-14.5 |
3.3 |
7 |
| 15-15.5 |
3.0 |
8 |
| 16-17.5 |
2.7 |
9 |
| 18-19.5 |
2.3 |
10 |
| 20-21.5 |
2.0 |
11 |
| 22-23.5 |
1.7 |
12 |
| 24-25.5 |
1.3 |
13 |
| 26-27.5 |
1.0 |
14 |
| 28-32 |
1.0 |
15 |
Skript zur Vorlesung
Es wird ein Skipt zur Vorlesung gedruckt ausgegeben.
Übungen zur Vorlesung
Skript Elementare Stochastik (PDF)
Blatt 1 (PDF)
Blatt 2 (PDF)
Blatt 3 (PDF)
Blatt 4 (PDF)
Blatt 5 (PDF)
Probeklausur (PDF)