|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Sonstige prüfbare Vorlesung
|
|
|
Zeit und Ort:
Do 10:15 - 11:45, Hörsaal S2229
Beginn: 2. Mai
|
|
|
Übung:
keine Übung
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Solide Grundkenntnisse der Theoretischen Informatik
|
|
|
Empfehlenswert für:
Vertiefung im Bereich Algorithmen/Komplexität
|
|
|
Inhalt:
Die Verwendung von Expandern hat in der Theoretischen Informatik in den
letzten Jahren zu einer Reihe von spektakulären Resultaten
geführt.
Ziel dieser Vorlesung ist es, diese und die dazu gehörende Theorie
in einem geschlossenen Rahmen darzustellen.
Expander sind spezielle Graphen, die in einem gewissen Sinne besonders
regulär sind. Die Existenz von Expandern ist nicht besonders
schwer zu zeigen. Für die meisten Anwendungen benötigt man
jedoch explizite Konstruktionen von Expandern, deren Beweis sehr
viel aufwendiger ist. Im ersten Teil der Vorlesung wollen wir solche
Konstruktionen vorstellen und spezielle Eigenschaften von Expandern
zusammentragen. Im zweiten Teil werden wir dann exemplarisch einige
Anwendungsbeispiele für Expander detailliert besprechen.
|
|
|
Skript:
kein Skript
|
|
|
Literatur:
Originalarbeiten. Genaue Referenzen werden in der Vorlesung bekannt
gegeben.
|
|
|
Sprechstunde:
siehe hier
|
