Albert-Ludwigs-Universität Freiburg
	Institut für mathematische Logik und Grundlagen der Mathematik

Vorlesung Komplexitätstheorie

Wintersemester 2000/2001
Mo 16-17, Mi 16-18,
Übungen dazu: Mo 17-18
beides SR 404 Eckerstraße 1

Zu den Übungsblättern:

Die Theorie der Berechenbarkeit ist zunächst als eine Theorie
der prinzipiellen Berechenbarkeit begründet worden. In den
letzten Jahrzehnten hat man begonnen, sich systematisch
Fragen des Rechenaufwandes zuzuwenden. Die betreffenden
Untersuchungen haben zu einer reichhaltigen Theorie geführt,
eben der Komplexitätstheorie. Die Vorlesung gibt einen Einblick
in verschiedene Teilgebiete. Behandelt werden sollen z.B.
folgende Themen:

Berechnungsmodelle und Komplexitätsmaße;
nachweisbar aufwendige Berechnungsprobleme;
Modelle der praktischen Berechenbarkeit;
probabilistische Algorithmen;
Approximationsalgorithmen.

Die Vorlesung wendet sich an Studierende der Mathematik und
der Informatik im Hauptstudium. Nützlich, wenn auch nicht
unabdingbar, sind Vorkenntnisse über Algorithmen und
Berechenbarkeit, wie man sie z.B. in der theoretischen
Einführungsvorlesung der Informatik oder in der Vorlesung
über mathematische Logik für Studierende der Mathematik
erwerben kann.

Mit geeigneten Erweiterungen kann sie als eines der Gebiete
für das Staatsexamen oder für Teil I der mündlichen Diplom-
prüfung in Mathematik gewählt werden.

Zur Orientierung seien bereits hier folgende Bücher genannt:

J.E. Hopcroft, J. Ullman: Introduction to Automata Theory,
Languages, and Computation;
C.H. Papadimitriou: Computational Complexity;
J.L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I, II.