Uni Dortmund, Informatik 2: Vorlesung KT

Komplexitätstheorie

Stammvorlesung 4V + 2 Ü, Wintersemester 2000/01

Ingo Wegener

[Termine] [Zusammenfassung] [Skript] [Übungen]

Termine

	Wann?	Wo?	Wer?
Vorlesungen:	Mo 12 - 14	HG I, HS 2	Ingo Wegener
	Di 10 - 12	HG I, HS 2	Ingo Wegener
Übungen:	Do 10 - 12	GB V, Raum 420	Beate Bollig
	Do 16 - 18	GB IV, Raum 318	Stefan Droste

Nachdem man einen Algorithmus für ein Problem entworfen hat, von dem man glaubt, dass er (fast) optimal ist, würde man diese Vermutung gerne beweisen. Derartige Beweise lassen sich bis heute nur in wenigen einfachen Fällen führen, z.B. für Sortieralgorithmen (s. Vorlesung Datenstrukturen). Wenn man es für ein Problem nicht schafft, einen effizienten Algorithmus zu entwerfen, möchte man (zur Rechtfertigung) gerne beweisen, dass es keinen effizienten Algorithmus gibt. Auch dies ist nur in wenigen Fällen möglich.

Die Komplexitätstheorie bietet jedoch Methoden, um Probleme bezüglich ihrer Schwierigkeit zu klassifizieren. Im Mittelpunkt steht dabei die bereits in der Vorlesung Grundbegriffe der Theoretischen Informatik angesprochene NP-Vollständigkeitstheorie. Mit ihr lassen sich inzwischen Tausende von Problemen (darunter das Traveling Salesman Problem, Stundenplanprobleme, Datenbankprobleme, Schedulingprobleme, VLSI-Designprobleme) im folgendem Sinn als gleich schwer klassifizieren. Entweder gibt es für alle diese Probleme polynomielle Algorithmen oder für keines. Die zweite Möglichkeit gilt heute als die weitaus wahrscheinlichere und wird als NP ungleich P-Hypothese bezeichnet.

Nach einer kurzen Wiederholung der NP-Vollständigkeitstheorie wird diese Theorie auf weitere Probleme angewendet und erweitert. Mit der Komplexitätsanalyse eines Problems wird entschieden, welche Teilprobleme eines schwierigen Problems effizient lösbar sind. Dazu gehört auch die Untersuchung, welche schwierigen Probleme dann einfach werden, wenn alle in der Eingabe vorkommenden Zahlen klein sind. Die Beziehungen zwischen Entscheidungsproblemen und Optimierungsproblemen, allgemeiner Suchproblemen, werden untersucht. Einen Schwerpunkt bildet die Komplexitätstheorie für Approximationsprobleme, dies sind Optimierungsprobleme, bei denen wir mit fast optimalen Lösungen zufrieden sind. Erst die relativ neue PCP-Theorie erlaubt es, für viele Approximationsprobleme zu entscheiden, ob sie schwierig sind. Die strukturelle Komplexitätstheorie wird nur kurz gestreift. Danach wird die Komplexität von der Ressource Rechenzeit auf die Ressource Speicherplatz erweitert.

Große Teile der Komplexitätstheorie sind softwareorientiert. Am Ende der Vorlesung werden Einblicke in die hardwareorientierte Komplexitätstheorie präsentiert.

Allgemein ist es ein Hauptziel, den Bezug der theoretischen Ergebnisse zu praktischen Fragestellungen herzustellen.

Skript

Das die Vorlesung begleitende Skript ist in der Skriptenverkaufsstelle erhältlich.

Wenn Du einen Fehler im Skript findest, informiere uns doch bitte in der Vorlesung bzw. den Übungen oder schicke eine Mail. Eine Liste der bisher gefundenen Fehler ist hier als gezipte Postscript-Datei oder im PDF-Format vorhanden.

Die Folien, die Beate Bollig in den Vorlesungen am 20. und 21. November benutzt hat, sind hier als JPEG-Dateien verfügbar: ZIP-Format (2,6 MB).

Übungen

In der Vorlesung wird jeweils am Montag ein Übungsblatt ausgegeben. Die Bearbeitungen der Übungsaufgaben sind bis zum folgenden Montag, 12 Uhr, abzugeben.