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

Komplexitätstheorie (SS96)


* 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

mayr@informatik.tu-muenchen.de