Stochastische Analyse von Algorithmen (WS 2017/18)

Zeit: Di 12:15 - 14:00
Ort: SR 711 groß (Robert-Mayer-Str. 10)
Dozent: Prof. Dr. R. Neininger

Übung:
Di 8-10, SR 711 groß (Frau Straub)

Die Übungen beginnen am 24. Oktober, die weiteren Termin sind 14. November, 28. November, 12. Dezember, 16. Januar, 30. Januar.

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 6. Februar 2018, 10:15 Uhr im Hörsaal H IV (Jügelhaus.) Die Zweitklausur am 5. April 2018, 10:15 Uhr im Hörsaal H IV (Jügelhaus). Als Hilfsmittel ist ein beidseitig handbeschriebenes Blatt Din A4 zugelassen.

Zulassungsvoraussetzung

keine

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)


Impressum, Datenschutzerklärung