|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Komplexität
|
|
|
Zeit und Ort:
Mo 08:30 - 10:00, Hörsaal S1128
Fr 08:30 - 10:00, Hörsaal 1221
Beginn: 3. Mai
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 08:30 - 10:00, Raum S2229
Übungsleitung:
Hans Stadtherr
Übungsschein: Bearbeiten der Übungsaufgaben,
Klausur
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik-Grundstudiums
Vorlesung Automaten und formale Sprachen vorteilhaft, aber
nicht notwendig.
|
|
|
Empfehlenswert für:
Vertiefung im Bereich Komplexität
|
|
|
Inhalt:
Die Vorlesung behandelt folgende Themen:
- Grundlagen und Maschinenmodelle
- Zeit- und platzbeschränkte Berechnungen
- Wichtige Komplexitätsklassen (u.a. P, NP, PSPACE,
EXPSPACE, ... )
- Zeitbeschränkte Reduktionen
- Schaltkreise, nichtuniforme Komplexität
- Probabilistische Maschinen
- Polynomialhierarchie
|
|
|
Skript:
Kein Skript.
|
|
|
Literatur:
-
Balcázar, Díaz, Gabarró:
-
Structural Complexity I & II
EATCS Monographs, Springer-Verlag, begleitend
-
Rüdiger Reischuk:
-
Einführung in die Komplexitätstheorie
Teubner-Verlag, in Ausschnitten
|
|
|
Sprechstunde:
siehe hier
|
