[ Institut für Mathematische Logik und Grundlagenforschung ] [ Fachbereich Mathematik und Informatik ] [ Westfälische Wilhelms-Universität Münster ]

Vorlesung: Komplexitätstheorie (SoSe 03)

Aktuelles, Inhalt, Voraussetzungen, Termine, Unterlagen,

Aktuelles

Inhalt

Ein Schwerpunkt dieser Vorlesung werden grundlegende Themen der Komplexitätstheorie sein:

Deterministische und Nichtdeterministische Turingmaschinen
Zeit- und Platzkomplexität, Hierarchietheoreme
Sätze von Savitch und Immermann-Szelepcsenyi
Komplexitätsklassen
NP-Vollständigkeit

Darüberhinaus wollen wir fortgeschrittene Themen behandeln:

Die polynomiale Hierarchie und Orakel-Separationen
Nichtuniforme Komplexitätsklassen und untere Schranken

Voraussetzungen

Die Vorlesung ist voraussetzungsfrei. Kenntnisse aus der Berechenbarkeitstheorie (z.B. der Begriff der Turingmaschine) erleichtern jedoch das Verständnis.

Vorlesungs- und Übungstermine

Vorlesung: (Veranstaltungsnummer 10.361.4)

Dienstag, 17 - 19, M5
Donnerstag, 17 - 19, M4
Beginn: Dienstag, 22.04.03

Übungen: (Veranstaltungsnummer 10.362.9)

Donnerstag, 15 - 17, SR8

Unterlagen

Fri Jul 18 10:50:26 MEST 2003 Übungsbogen 8
Wed Jul 2 22:02:34 MEST 2003 Übungsbogen 7
Wed Jun 25 09:44:36 MEST 2003 Übungsbogen 6
Tue Jun 3 15:02:14 MEST 2003 Übungsbogen 5
Thu May 22 13:18:41 MEST 2003 Übungsbogen 3
Tue May 13 19:36:27 MEST 2003 Übungsbogen 2
Tue May 13 14:43:30 MEST 2003 Folien der Sitzung vom 8.5.
Tue May 13 14:41:45 MEST 2003 Übungsbogen 1

Arnold Beckmann

Last modified: Wed Jul 30 13:40:29 MEST 2003