Übungsseite Komplexitätstheorie

Übungsseite zur Vorlesung

Komplexitätstheorie - WS 2007/08

Ingo Wegener, Martin Sauerhoff, Marcel Marquardt

Die Einteilung der Teilnehmenden in die Übungsgruppen können Sie hier finden.

Folgende Bücher wurden noch ergänzend in den Übungen vorgestellt:

Papadimitriou, Computational Complexity - Hier werden, oft in eher intuitiver Manier, viele Resultate aus der Komplexitätstheorie dargestellt und an Beispielen erläutert. Empfehlenswert sind die Übungsaufgaben und weiterführenden Hinweise am Ende jedes Kapitels.
Hromkovic, Theoretische Informatik - Eher ein Buch für die GTI, in dem aber auch weiterführende Themen der Komplexitätstheorie behandelt werden.
Schöning - Perlen der Theoretischen Informatik - Eine Sammlung von "schönen" Beweisen aus der Informatik. Leicht und anschaulich zu lesen.
Hemaspaandra und Ogihara, The Complexity Theory Companion - Anhand neun durchbrechender Ergebnisse der letzten Jahre werden verschiedene Gebiete der Komplexitätstheorie beleuchtet. Insbesondere führt das Buch zu aktuellen offenen Fragen in den jeweiligen Bereichen hin. Am Ende des Buches findet sich eine Gallerie von Komplexitätsklassen mit den wichtigsten sie betreffenden Ergebnissen