Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2017/18 / Komplexitätstheorie


Inhaltsbereich

Komplexitätstheorie

Vorlesung, 3-std., Di 16-18, Do 16-18, Johannsen

Aktuelles

  •  Anmeldung zur Vorlesung über UniWorx ist jetzt möglich.

Inhalt

Die Komplexitätstheorie beschäftigt sich mit der Klassifikation von Algorithmen und Berechnungsproblemen nach ihrem Ressourcenverbrauch, z.B. Rechenzeit oder benötigtem Speicherplatz. Probleme mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit deterministisch bzw. nicht-deterministisch lösbaren Probleme umfassen.

P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen ergeben sich etwa bei der Untersuchung der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte oder interaktive Algorithmen, der approximativen Lösung von Problemen, um nur einige Beispiele zu nennen.

Übersicht

  1. Motivation und Einführung
  2. Turingmaschinen, Berechenbarkeit, Komplexitätsklassen
  3. Die Klassen P und NP
  4. Platzkomplexität
  5. Alternierung und Hierarchien
  6. Komplexität von Schaltkreisen
  7. Weiterführende Themen

Logbuch

17.10. Organisatorisches, Motivation, Einführung.
19.10. Erinnerung Turing-Maschine. Definition Komplexitätsklassen P, E, EXP. Hierarchiesatz: P echt enthalten in E.
24.10. Nichtdeterministische Maschinen, Klassen NP, NE, NEXP. Problem P vs NP. NP enthalten in EXP. Padding: P=NP impliziert E = NE.
26.10. Einige Probleme in P und NP. Charakterisierung von NP mittels existenzieller Quantifizierung.Erinnerung: NP-Vollständigkeit, einige NP-vollständige Probleme.
31.10. Feiertag
02.11. Erinnerung: NP-Vollständigkeit. Existenz von Problemen in NP \ P, die nicht NP-vollständig sind.
07.11. Orakelturingmaschinen, Relativierung, Existenz von Orakeln A und B mit P^A = NP^A und P^B != NP^B.
09.11. Übung
14.11. Platzkomplexität, Klassen L, NL, PSPACE, NPSPACE. Satz von Savitch: NL in deterministichem Platz O((log n)^2), PSPACE = NPSPACE. Logspace-berechenbare Funktionen unter Komposition abgeschlossen.
16.11. Logspace-reduktion, vollständige Probleme in NL, P, PSPACE.
21.11. Satz von Immerman-Szelepcsényi: NL abgeschlossen unter Komplementierung.
23.11. Übung


Organisation

  • Umfang:  3+1 Semesterwochenstunden
  • Voraussetzung:  Grundvorlesungen der Informatik. Insbesondere werden solide Kenntnisse der Inhalte von Formale Sprachen und Komplexität oder Theoretische Informatik für Medieninformatiker sowie Algorithmen und Datenstrukturen vorausgesetzt.
  • Vorlesung und Übungen:  Dr. Jan Johannsen

Die Vorlesung wird anerkannt:

  • für Studierende im Studiengang Informatik Master für das Modul Algorithmik und Komplexität
  • für Studierende im Studiengang Medieninformatik Master für das Modul Vertiefende Themen der Informatik für Master
  • für Studierende in den Studiengängen Informatik und Medieninformatik Bachelor für das Modul Vertiefende Themen der (Medien-) Informatik
  • für Studierende mit Nebenfach Informatik nach Vereinbarung

Zeit und Ort

VeranstaltungZeitOrtBeginn
Vorlesung Di, 16 - 18 Uhr Hörsaal S 006 (Schellingstr. 3) 17.10.2017
Vorlesung Do, 16 - 18 Uhr Hörsaal C 113 (Theresienstr. 41) 19.10.2017
Übung 14-tägig zum Vorlesungstermin 02.11.2017

 


Übungen

Materialien

Klausur

 tba


Weiterführende Informationen

Literatur

  • Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York, 1994.
    Dieses Buch ist frei auf der Webseite der Autoren verfügbar als PDF.
  • S. Arora und B. Barak. Complexity Theory: A Modern Approach, Cambridge University Press, 2009. (Fast fertige Vorabversion hier). In diesem Buch sind fast alle Themen der Vorlesung abgedeckt.
  • C. Papadimitriou. Computational Complexity. Addison-Wesley. Reading, 1995.
  • I. Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
  • Ein hervorragendes Vorlesungsskript von Oded Goldreich, das weit mehr, aber auch nicht alles abdeckt, als wir in der Vorlesung behandeln werden.
  • Zur Motivation: Heribert Vollmer, Was leistet die Komplexitätstheorie für die Praxis?, Informatik Spektrum 22 Heft 5, 1999.
  • Noch etwas zur Motivation: Stephen Cook (ja, der Cook) schreibt in der Jubiläumsausgabe des Journal of the ACM (Vol. 50 No. 1) über The Importance of the P versus NP Question.

 

Artikelaktionen


Funktionsleiste