Technische Universität Ilmenau

Complexity Theory - Modultafeln of TU Ilmenau

The module lists provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the electronic university catalogue.

Information and guidance on the maintenance of module descriptions by the module officers are provided at Module maintenance.

Please send information on missing or incorrect module descriptions directly to modulkatalog@tu-ilmenau.de.

module properties Complexity Theory in degree program Master Informatik 2009
module number227
examination number2200223
departmentDepartment of Computer Science and Automation
ID of group 2242 (Complexity Theory and Efficient Algorithms)
module leaderProf. Dr. Martin Dietzfelbinger
term winter term only
languageDeutsch
credit points4
on-campus program (h)34
self-study (h)86
obligationelective module
examoral examination performance, 20 minutes
details of the certificate

Findet statt im: WS 2013/2014, SS 2015

alternative examination performance due to COVID-19 regulations incl. technical requirements
signup details for alternative examinations
maximum number of participants
previous knowledge and experience

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

learning outcome

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.

content

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

media of instruction and technical requirements for education and examination in case of online participation

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

 

Moodle: https://moodle2.tu-ilmenau.de/enrol/index.php?id=3181

literature / references

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.

evaluation of teaching

Pflichtevaluation:

SS 2019 (Qualitatives Verfahren)

Freiwillige Evaluation:

Hospitation: