|
Stand: 24. März 1998 »Komplexitätstheorie«Vorlesung im SS 98Vorlesungsplan
Erste Vorlesung: 14. April Erste Übungsstunde: 23. April Dozent:
Übungsgruppenleiter:
InhaltsverzeichnisÜbungsblätterKurzbeschreibung der VorlesungDie Komplexitätstheorie klassifiziert algorithmische Problemstellungen nach ihrem Bedarf an Rechenressourcen (wie zum Beispiel Zeit oder Speicherplatz). Der Idealfall für eine Problemstellung ist, daß man (bzgl. einem festen Rechenmodell) einen Algorithmus A hat, der das Problem löst (obere Schranke), und man außerdem zeigen kann, daß A optimal ist: kein Algorithmus löst das Problem schneller als A (untere Schranke). Dieser Idealfall ist bis heute bei fast keiner Problemstellung erreicht. Ein drastisches Beispiel sind die sogenannten NP-vollständigen Probleme, wie etwa das Traveling Salesman Problem. Mit den bekannten Algorithmen würden auch die schnellsten Rechner für praktisch relevante Eingabegrößen Jahre zur Lösung benötigen. Andererseits kennt man dafür nur triviale untere Schranken (P-NP-Problem). Die Beziehungen zwischen den Komplexitätsklassen sind ein zentrales Thema der Forschung. Die Vorlesung gibt dazu einen Überblick über die wichtigsten Resultate und Techniken der letzten Jahre.Übrigens ...gibt es im Wintersemester 98/99 folgende interessanten Vorlesungen zu diesem Thema:
Literatur
Ein Teil der Vorlesung findet man im Skript der letzten Vorlesung Berechenbarkeit. Christian Scheideler (email: chrsch@uni-paderborn.de) |