Humboldt-Universität
zu
Berlin,
Institut
für Informatik
Lehrstuhl
für Komplexität und Kryptografie
Vorlesung: Komplexitätstheorie
Dozent: Olaf Beyersdorff
Termine: |
VL Mo 11-13 (RUD 25, 4.101) O. Beyersdorff |
|
VL Mi 15-17 (RUD 25, 4.101) O. Beyersdorff
UE Mo 13-15 (RUD 25, 4.101) L. Weizsaecker |
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
Literatur
-
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.
Aufgabenblätter
Ben Bäßler