Technische Universität Ilmenau

Komplexitätstheorie - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Komplexitätstheorie im Studiengang Master Informatik 2013
Fachnummer227
Prüfungsnummer2200223
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusWintersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)90
Selbststudium (h)60
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 20 Minuten
Details zum Abschluss

Findet statt im: WS 2013/2014, SS 2015

Anmeldemodalitäten für alt. Leistungen
max. Teilnehmerzahl
Vorkenntnisse

Bachelor-Veranstaltung "Automaten, Sprachen und Komplexität", Effiziente Algorithmen

Lernergebnisse

Fachkompetenz: Die Studierenden kennen das Konzept von polynomiellen Suchproblemen und polynomiellen Optimierungsproblemen. Sie kennen verschiedene Reduktionskonzepte (Turing, polynomielle Reduktion) sowie den Begriff der NP-Vollständigkeit und den Satz von Cook/Levin. Sie kennen die Implikationen der Eigenschaft „NP-vollständig“. Die Studierenden kennen die 20 wichtigsten NP-vollständigen Probleme sowie das Konzept der starken NP-Vollständigkeit. Sie kennen die wesentlichen randomisierten Komplexitätsklassen, die polynomielle Hierarchie und Beziehungen zwischen beiden. Sie kennen die Grundbegriffe der PCP-Theorie. 

Methodenkompetenz:  Den Studierenden stehen die genannten Grundbegriffe als Basis für Argumentationen zur Verfügung. Sie sind in der Lage, den Satz von Cook/Levin zu beweisen, und auch die NP-Vollständigkeit für die in der Vorlesung behandelten Probleme und abgewandelte Versionen hiervon. Sie können wesentliche Berechnungsprobleme komplexitätstheoretisch einordnen.

Inhalt

Theorie der NP-Vollständigkeit, polynomielle Hierarchie, randomisierte Komplexitätsklassen, Grundzüge der PCP-Theorie und Nicht-Approximierbarkeit.

Medienformen

Tafelvortrag, Folien, teilweise schriftliche Ausarbeitung. Übungsblätter.

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.

Lehrevaluation

Pflichtevaluation:

Freiwillige Evaluation:

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.