Zeit: Di 12:15 - 14:00
Ort: 110 (Robert-Mayer-Str. 10)
Dozent: Prof. Dr. R. Neininger
Übungen: 14 tägig (Dipl. Math. M. Knape):
Di 16-18, Raum 901. Erste Übung am 20. Oktober
Thema
Aufbauend auf der Elementaren Stochastik 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
Erfolgt in einem etwa 20 minütigen Gespräch. Es werden 10-15 Fragen vorher bekanntgegeben, von denen 3 zufällig zu Beginn des Gesprächs ausgewählt werden.
Prüfungstermine:
Dienstag, den 9.2.2010, 12-14 Uhr,
Montag, den 1.3.2010, 10-12 Uhr,
Mittwoch, den 7.4.2010, 12-14 Uhr.
Anmeldung erfolgt bei Frau Götting, goetting[at]math[dot]uni-frankfurt[dot]de.
Skript zur Vorlesung
Es wird ein in LaTeX gesetztes Skipt zur Vorlesung gedruckt ausgegeben.
Ralph Neininger