Zeit: Di 14:15 - 16:00
Ort: 711 (groß)
Dozent: Prof. Dr. R. Neininger
Übungen: 14 tägig (T. Baumgratz):
Di 16-18, SR 711 (klein), Beginn: 15. April
Fr 16-18, SR 901, Beginn: 18. April
Thema
Aufbauend auf der Elementaren Stochastik werden wir das Verhalten einiger
diskreter Strukturen, Algorithmen und Optimierungsprobleme stochastisch
untersucht. Die Probleme (z.B. Algorithmen) werden sehr einfach sein, allerdings
werden wir annehmen, dass ihre Eingaben, auf denen sie operieren, 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 liefert.
Geplante Themen sind: Einfache Irrfahren mit Anwendungen auf bin packing und
Catalan-Bäumen, 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-Zip Kodierung, sowie die Analyse
einiger randomisierter Algorithmen.
Scheinerwerb
Termine für mündliche Prüfungen sind 11. Juli und 6. August. Zur Terminvereinbarung schicken Sie bitte eine Email an mich mit Cc an Frau Götting.
Je nach Studiengang:
Mathematik Diplom, Mathematik-Lehramt L3 (alt), Informatik (Diplom): mündliche Prüfung
Mathematik-Bachelor (Vertiefungsbereich, BaM-SB-2): mündliche Prüfung
Mathematik-Bachelor (Wahlpflicht, BaM-WP): mündliche Prüfung (zusammen mit
der Veranstaltung Stochastische Prozesse)
Skript zur Vorlesung
Es wird ein in LaTeX gesetztes Skipt zur Vorlesung gedruckt ausgegeben.
Ralph Neininger