Stochastische Analyse von Algorithmen (WS 2019/20)
Zeit: Di 10:15 - 12:00
Ort: SR 711 groß (Robert-Mayer-Str. 10)
Dozent: R. Neininger
NEU
Die Zweitklausur findet am 25.06.2020 um 9:00 Uhr (bis 10:30 Uhr) im Seminarraum HZ 15 (Campus Westend) statt. Falls Sie sich bei Frau Straub noch
nicht vorab für die Teilnahme gemeldet haben,
holen Sie das bitte nach, da die maximale Teilnehmendenzahl beschränkt ist.
Übung:
Zeit: Fr 8:15 - 10:00 (Start: 25.10.19)
Ort: SR 903 (Robert-Mayer-Str. 10)
Dozentin: J. Straub
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
Klausur am 11. Februar 2020, 10:15 Uhr im Hörsaal H IV (Jügelhaus.) Zweitklausur am 25.06.2020 um 9:00 Uhr im Seminarraum HZ 15 (Campus Westend).
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)