Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Vorlesung: Einführung in die Komplexitätstheorie

Dozent: Prof. Johannes Köbler
Übung: Prof. Johannes Köbler

Termine: VL Di 11-13 (RUD 26, 1'306)
VL Do 11-13 (RUD 26, 1'307)
UE Do 13-15 (RUD 26, 1'307)
Zuordnung: Hauptstudium, Halbkurs

Inhalte und Lernziele


Welcher Aufwand ist nötig, um ein 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, 2001.
  • 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, 1997.
  • M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
  • 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 (mündl. Besprechung: 28.10.2010; schriftl. Abgabe: bis 04.11.2010)
Blatt 2 (mündl. Besprechung: 04.11.2010; schriftl. Abgabe: bis 11.11.2010)
Blatt 3 (mündl. Besprechung: 11.11.2010; schriftl. Abgabe: bis 18.11.2010)
Blatt 4 (mündl. Besprechung: 25.11.2010; schriftl. Abgabe: bis 02.12.2010)
Blatt 5 (mündl. Besprechung: 02.12.2010; schriftl. Abgabe: bis 09.12.2010)
Blatt 6 (mündl. Besprechung: 09.12.2010; schriftl. Abgabe: bis 16.12.2010)
Blatt 7 (mündl. Besprechung: 16.12.2010; schriftl. Abgabe: bis 06.01.2011)
Blatt 8 (mündl. Besprechung: 06.01.2011; schriftl. Abgabe: bis 13.01.2011)
Blatt 9 (mündl. Besprechung: 13.01.2011; schriftl. Abgabe: bis 20.01.2011)
Blatt 10 (mündl. Besprechung: 03.02.2011; schriftl. Abgabe: bis 03.02.2011)
Blatt 11 (mündl. Besprechung: 10.02.2011; schriftl. Abgabe: bis 17.02.2011)

 

Skript (14. Woche)