|
Dozenten:
Prof. Dr. Ernst W. Mayr
Prof. Dr. Angelika Steger
|
|
|
Bereich:
2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Sonstige prüfbare Vorlesung
|
|
|
Zeit und Ort:
Mi 16:00 - 17:30, Hörsaal S2229
Beginn: 6. November
|
|
|
Übung:
keine Übung
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende im Hauptstudium der Mathematik mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Solide Grundkenntnisse der Theoretischen Informatik
|
|
|
Empfehlenswert für:
Vertiefung im Bereich Algorithmen
|
|
|
Inhalt:
Die Verwendung tiefliegender Resultate aus der Kombinatorik
hat in den letzten Jahren zu einigen
schönen und verblüffenden Ergebnissen
in der theoretischen Informatik geführt.
Typische Beispiele hierfür sind
Lovász Local Lemma und Szemerédi's Regularity Lemma.
In ihrer ursprünglichen Form waren beide reine
Existenzaussagen, mit entsprechend geringer Bedeutung für die
Informatik. Dies änderte sich mit der Veröffentlichung
einer algorithmischen Version durch Beck (1991) bzw.
Alon, Duke, Lefmann, Rödl, Yuster (1992).
In dieser Vorlesung wollen wir uns Aussage, Bedeutung und Anwendungen
dieser beiden Lemmata erarbeiten.
|
|
|
Skript:
Kein Skript, die Vorlesung hält sich eng an Originalarbeiten.
|
|
|
Literatur:
Originalarbeiten. Genauer Referenzen werden in der Vorlesung
bekannt gegeben.
|
|
|
Sprechstunde:
siehe hier
|
