http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Komplexitätstheorie (Prof. Dr. Martin Dietzfelbinger)

Vorlesungsmaterial

Vorlesungsmaterial:

  1. Reduktionsbaum [pdf]
  2. Notizen zur starken NP-Vollständigkeit von BinPacking [pdf]

Übungsblätter:

Übungsblatt 1 

Übungsblatt 2

Übungsblatt 3

Übungsblatt 4

Übungsblatt 5

Übungsblatt 6

Übungsblatt 7

Übungsblatt 8

Übungsblatt 9

Bonuspunkte:  1/3 oder 2/3 oder 1/1 einer Notenstufe durch Vortragen von Übungsaufgaben. Keine automatische Verbesserung von 5.0 auf 4.0.

Termine

Prüfungstermine:

Die mündlichen Prüfungen finden vom 8. - 9. März 2012 statt. Zur Terminvergabe tragen Sie sich bitte bis zum 3. Februar 2012 im Sekretariat bei Frau Kopp, Zusebau, Raum 1046, in die Terminliste ein. 

 

Vorlesung:

  • Montag, 09:00-10:30, Sr K 2026
  • Donnerstag, 09:00-10:30, Sr HU 210

Übung (Martin Aumüller):

  • Freitag, 11:00-12:30, Sr H 1520a

Inhalt

  1. Die NP-Vollständigkeits-Theorie, in der Vorlesung "Berechenbarkeit und Komplexität" begonnen, wird vertiefend behandelt: Der Satz von Cook/Levin wird bewiesen: SAT ist NP-vollständig. Viele weitere Probleme werden als NP-vollständig bzw. NP-schwer klassifiziert. Zentrales Thema: Reduktionen zwischen Problemen. Die Grenze zwischen P (effizient lösbar) und NP (wahrscheinlich nicht effizient lösbar) wird beleuchtet.
  2. Randomisierte Algorithmen und ihre Komplexitätsklassen: Man betrachtet Algorithmen (und Turingmaschinen), die Zufallsexperimente ausführen. Diese Modellerweiterung führt zu weiteren Komplexitätsklassen. Auch realistischerweise muss man schnelle randomisierte Algorithmen als "effizient" ansehen und kommt damit (eventuell) über P hinaus.
  3. „Interaktive Beweise“ – Ein Blick auf die PCP-Theorie und Nicht-Approximierbarkeit.
  4. Polynomielle Hierarchie: Schwierige Probleme jenseits von NP.
  5. Platzkomplexität, PSPACE-vollständige Probleme, Logspace-Reduzierbarkeit, P-Vollständigkeit.

Literatur

  • I. Wegener, Komplexitätstheorie – Grenzen der Effizienz von Algorithmen, Springer, 2003.
  • G. Ausiello et al., Complexity and Approximation, Springer, 1999.
  • M. Garey, D. Johnson, Computers and Intractability, W.H. Freeman and Co., 1979.
  • C. Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
  • S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  • O. Goldreich, Computational complexity - a conceptual perspective, Cambridge University Press, 2008.