Komplexitätstheorie - Interaktive Studienpläne der TU Ilmenau
Die Interaktiven Studienpläne
sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.
Die rechtsverbindlichen Studienpläne
entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).
Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im
elektronischen Vorlesungsverzeichnis.
Bitte beachten Sie, dass auf dieser Seite keine Aktualisierungen mehr vorgenommen werden. Alle Module und Studienpläne
ab der PO-Version 2021 (Bachelor- und Master-Studiengänge) sind ab sofort im
Campus-Portal erreichbar.
Modulinformationen zu Komplexitätstheorie
im Studiengang Master Informatik 2013
ACHTUNG: wird nicht mehr angeboten! |
| Modulnummer | 200073 |
| Prüfungsnummer | 2200726 |
| Fakultät | Fakultät für Informatik und Automatisierung |
| Fachgebietsnummer |
2242 (Algorithmik)
|
| Modulverantwortliche(r) | Prof. Dr. Martin Dietzfelbinger |
| Turnus | ganzjährig |
| Sprache | Deutsch |
| Leistungspunkte | 5 |
| Präsenzstudium (h) | 67 |
| Selbststudium (h) | 83 |
| Verpflichtung | Wahlmodul |
| Abschluss | mündliche Prüfungsleistung, 30 Minuten |
| Details zum Abschluss | |
| Link zum Moodle-Kurs |
|
| Lehrende | Dietzfelbinger |
| Anmeldemodalitäten für alternative PL oder SL | |
| max. Teilnehmerzahl | |
| Vorkenntnisse | Berechenbarkeit und Komplexitätstheorie Effiziente Algorithmen |
| Lernergebnisse und erworbene Kompetenzen | 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. Sozialkompetenz: Selbst in der Vorlesung ist Interaktion stets möglich, ja erwünscht, darin sind die Studierenden geübt.
Die Studierenden konnten die Erfahrung machen, dass Fragen unmittelbar geklärt
werden, dass Diskussionen auf Augenhöhe stattfinden und Beiträge
wertschätzend aufgenommen werden. In der Übung waren die Studierenden zu
Präsentationen aufgerufen. Sie konnten wertvolle Erfahrung in der Rolle
des Präsentierenden sammeln. Die Teilnahme erforderte und trainierte ein hohes Maß an Selbstorganisation.
|
|
| Inhalt | Theorie der NP-Vollständigkeit, polynomielle Hierarchie, randomisierte Komplexitätsklassen, Grundzüge der PCP-Theorie und Nicht-Approximierbarkeit
|
| Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form | 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 | |
