http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Komplexitätstheorie und Approximationsalgorithmen (Univ-Prof. M. Dietzfelbinger)

Material

Vorlesungsmaterial:

  1. Notizen zum Algorithmus von Christofides [pdf]
  2. Notizen zum 2-Approximationsalgorithmus für das Rucksackproblem [pdf]
  3. Notizen zu Approximationsschemata für Makespan und Rucksack [pdf]

Übungsblätter KT:

  1. Übung (12.10.) [pdf]
  2. Übung (19.10.) [pdf]
  3. Übung (26.10.) [pdf]
  4. Übung (02.11.) [pdf]
  5. Übung (09.11.) [pdf]
  6. Übung (16.11.) [pdf]
  7. Übung (23.11.) [pdf]
  8. Übung (30.11.) [pdf

Übungsblätter AA:

  1. Übung (07.12.) [pdf]
  2. Übung (14.12.) [pdf]
  3. Übung (21.12.) [pdf]
  4. Übung (11.01.) [pdf]
  5. Übung (18.01.) [pdf]
  6. Übung (25.01.) [pdf
  7. Übung (01.02.) [pdf] (Übung beginnt erst 15:00 im Raum SR HU 202.)

Termine

Die Termine für die mündlichen Prüfungen finden Sie hier.

Vorlesung:

  • Montag, 9:00-10:30, Sr K 2026 (ab 49. KW: Sr H 1520a)
  • Donnerstag, 9:00-10:30, Sr HU 210

Übung:

Inhalt

Komplexitätstheorie:

  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.

Approximationsalgorithmen

  1. Absolute Approximation (Knoten- und Kantenfärbungen in Graphen)
  2. Relative Approximation (Packungs- und Schedulingprobleme, TSP-Varianten)
  3. Approximationsschemata
  4. Weitere Techniken (LP-Relaxierung, Semidefinite Programmierung)

Literatur

Komplexitätstheorie:

  • 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.

Approximationsalgorithmen:

  • K. Jansen, M. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit,
    de Gruyter Verlag, 2008.
  • Rolf Wanka: Approximationsalgorithmen - Eine Einführung, Leitfäden der Informatik, B.G. Teubner Verlag, 2006.
  • Vijay V. Vazirani: Approximation Algorithms, Springer Verlag, 2001.