Komplexitätstheorie

(3 Std. Vorlesung, 1 Std. Übung)


Vorlesung:Montag14-16 Uhrin Raum  -1319 WA
Dienstag10-11 Uhrin Raum   1332 WA
Übung:Dienstag11-12 Uhrin Raum   1332 WA
Beginn:Montag,den 20.10.2014, 14.15 Uhr

Aktuelles zur

Inhalt:

Viele Konzepte der strukturellen Komplexitätstheorie stammen ursprünglich aus der Rekursionstheorie. Dort befasste man sich mit der Frage, welche Probleme überhaupt algorithmisch lösbar sind. Außerdem bemühte man sich, die unlösbaren Probleme zu klassifizieren. In der Komplexitätstheorie fragt man nun danach, welche Probleme mit vertretbarem Aufwand gelöst werden können. Dabei hat sich inzwischen die Übereinstimmung ergeben, dass ein Problem mit vertretbarem Aufwand gelöst werden kann, wenn es in polynomialer Rechenzeit gelöst werden kann. Dies führte zur Klasse P. Man bemühte sich nun, die Probleme zu klassifizieren, die nicht in P zu liegen scheinen. Bei diesen Untersuchungen hat man viele Konzepte aus der Rekursionstheorie auf den subrekursiven Bereich übertragen. Die dabei aufgetretenen Fragen und Probleme zählen vielfach zu den bedeutendsten der (theoretischen) Informatik. Sie berühren unmittelbar unser Verständnis von dem, was algorithmisch mit vertretbarem Aufwand gelöst werden kann.

Die Vorlesung ist wie folgt aufgebaut:

Literatur:

J.L. Balcazar, J. Diaz, J. Gabborro:
Structural Complexity, I und II
EATCS Monographs on Theoretical Computer Science, Vol. 11 und 22, Springer, 1988.
M.R. Garey, D.S. Johnson:
Computers and Intractability - A Guide to the Theory of NP-Completeness
Freeman, San Francisco, 1979.
J.E. Hopcraft, J.D. Ullman:
Introduction to Automata Theory, Languages and Computation
Addison-Wesley, 1979.
K.R. Reischuk:
Komplexitätstheorie, Band I: Grundlagen
Teubner, Stuttgart, 1999.

Angesprochener Hörerkreis:

Vorkenntnisse:

Grundvorlesungen der Theoretischen Informatik

Leistungsnachweis:

Mündliche Prüfung am Ende des Semesters. Aktive Teilnahme an den Übungen sowie erfolgreiche Bearbeitung der wöchentlichen Übungsaufgaben sind Voraussetzungen für die Zulassung zur Abschlussprüfung.