 |
Komplexitätstheorie
| Dozenten |
Rolf Wanka |
Modulbeschreibung
|
Komplexitätstheorie |
| Umfang |
V2 + Ü2,
Studenten der Informatik und des
Computational Engineering,
Interessenten anderer
Fächer |
Ort
und Zeit der Vorlesung
|
Fr. 10:00-11:30, E 1.11, E-Technik-Gebäude
|
Ort
und Zeit der Übung
|
Mi. 10:15-11:45, E 1.11
|
Beschreibung:
In der Vorlesung Komplexitätstheorie
untersuchen wir die Zusammenhänge zwischen Rechenzeit und
Speicherplatz, die Grenzen der Berechenbarkeit und die
Beziehungen zwischen verschiedenen algorithmischen Modellen.
Inhalte:
- Band- und Zeithierarchiesätze
- Untere Schranken für 1-Band-Turingmaschinen
(Kolmogorov-Komplexität)
- Nichtdeterministische Maschinen (Satz von Savitch,
Satz von Immerman/Szelepcsenyi)
- Nichtentscheidbarkeit, rekursive Aufzählbarkeit
- Vergleich von Zeit- und Platzbedarf (Time vs. Space)
- Die polynomielle Hierarchie
Übungsblätter:
Skript:
Die Vorlesung orientiert sich stark an einer entsprechenden
Vorlesung von
Prof. Dr. Friedhelm
Meyer auf der Heide der
Universität Paderborn.
Ein Vorlesungsskipt im pdf-Format gibt es
>hier<.
Literatur:
-
Wolfgang J. Paul. Komplexitätstheorie, Teubner 1978.
-
K. Rüdiger Reischuk. Einführung in die Komplexitätstheorie, Bd. 1,
Teubner, 2. Aufl. 1999.
- Gerd Wechsung. Vorlesungen zur Komplexitätstheorie,
Teubner 2000.
- Ingo Wegener. Komplexitätstheorie, Springer 2003
|
|
