Vorlesung: Einführung in die Komplexitätstheorie
Dozent: Prof. Johannes Köbler
Beginn der Übungen: 23.10.
Eintragen über: Agnes
Moodle-Kurs (Kennwort in der Vorlesung)
| Termine: |
VL Di 15-17 (RUD 26, 1'307) |
| Zuordnung: |
Bachelor-Monostudiengang (B.Sc.): Wahlpflichtmodul (forschungsorientiert) |
Inhalte und Lernziele
Welcher Aufwand ist nötig, um ein algorithmisches Problem (man denke etwa an das Traveling Salesman Problem) auf einem Computer zu lösen? Sobald man einen korrekt arbeitenden Algorithmus gefunden hat, stellt sich die Frage, ob die von diesem Algorithmus beanspruchten Ressourcen - in erster Linie Rechenzeit und Speicherplatz - auch tatsächlich nötig sind. Hierzu muss man nachweisen, dass es keinen wesentlich effizienteren Algorithmus für dieses Problem gibt. Für die weitaus meisten Problemstellungen (das Traveling Salesman Problem bildet hierbei keine Ausnahme) ist diese Frage trotz intensiver Forschung bis heute offen.
Um derartige Fragestellungen präzise formulieren (und nach einer Antwort suchen) zu können, werden reale Rechenmaschinen durch mathematische Modelle nachgebildet. Dabei ist man nicht nur an gegenwärtigen sondern auch an zukünftigen Technologien (etwa zur Parallelverarbeitung) interessiert. Auf der Basis dieser Modelle lassen sich durch eine Beschränkung der zur Verfügung stehenden Ressourcen so genannte Komplexitätsklassen bilden, in die die bekannten algorithmischen Problemstellungen nach ihrem Bedarf an Rechenressourcen eingeordnet werden können (die Komplexität des Traveling Salesman Problems ist beispielsweise durch die Klasse NP charakterisiert).
Für die meisten in der Praxis relevanten Problemstellungen lässt sich die Frage, ob es wesentlich effizientere Algorithmen als die bisher bekannten gibt, darauf zurückführen, ob bestimmte Komplexitätsklassen wie etwa P und NP gleich sind oder nicht (P-NP-Problem). Welche Beziehungen zwischen den unterschiedlichen Komplexitätsklassen bestehen, ist daher ein zentrales Forschungsthema der Theoretischen Informatik. Aus dem Inhalt der VL:
- Berechnungsmodelle, Platz- und Zeitkomplexität
- Probabilistische Algorithmen, Beziehungen zwischen verschiedenen Komplexitätsklassen
- Reduktionen, NP-Vollständigkeit und das P-NP-Problem
- Klassifikation konkreter Entscheidungs-, Such-, Optimierungs- und Anzahlprobleme
- Bewältigung harter Probleme (approximative und heuristische Lösungsansätze)
- Logische Charakterisierung von Komplexitätsklassen
- Interaktive Beweissysteme
- Kombinatorische Schaltkreise und parallele Komplexitätsklassen
Empfohlene Literatur
- S. Arora, B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Online unter http://www.cs.princeton.edu/theory/complexity
- J. Balcázar, J. Diaz, J. Gabarró. Structural Complexity I+II. Springer, 1995.
- M.R. Garey, D.S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979.
- L.A. Hemaspaandra, M. Ogihara. The Complexity Theory Companion. Springer, 2002.
- S. Homer, A.L. Selman. Computability and Complexity Theory. Springer, 2001.
- J.E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.
- H.R. Lewis, C.H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1998.
- R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
- C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- K.R. Reischuk. Komplexitätstheorie, Band I: Grundlagen. Teubner, 1999.
- U. Schöning. Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
- U. Schöning. Theoretische Informatik, kurz gefaßt. Spektrum Akademischer Verlag, 2008.
- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 2013.
- K.W. Wagner. Einführung in die Theoretische Informatik. Springer, 1994.
- G. Wechsung. Vorlesungen zur Komplexitätstheorie. Teubner, 2000.
- I. Wegener. Theoretische Informatik. Teubner, 1993.
- I. Wegener. Kompendium Theoretische Informatik. Eine Ideensammlung. Teubner, 1996.
- J. E. Savage. Exploring the Power of Computing. Addison-Wesley, 1998. Online unter http://www.modelsofcomputation.org
Aufgabenblätter
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13