LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Expander:
Konstruktion und Anwendungen (SS96)


* 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


steger@informatik.tu-muenchen.de