Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2010/11 / Komplexitätstheorie


Inhaltsbereich

Komplexitätstheorie

 

 


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. Interaktive und probabilistische Algorithmen
  8. Kommunikationskomplexität

Organisation

  • Umfang:  3+1 Semesterwochenstunden
  • Voraussetzung:  Grundstudiumsvorlesungen der Informatik
  • Vorlesung und Übungen:  Dr. Jan Johannsen

Die Vorlesung wird anerkannt:

  • für Studierende im Studiengang Informatik Diplom im Prüfungsfach Programmierung und Grundlagen, Teilbereich Theoretische Informatik
  • 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

Veranstaltung Zeit Ort Beginn
Vorlesung Di, 14 - 16 Uhr Hörsaal A 022 (Hauptgebäude) 19.10.2010
Vorlesung Do, 16 - 18 Uhr Hörsaal D Z001 (Hauptgebäude) 21.10.2010
Übung 14-tägig zum Vorlesungstermin

28.10.2010

 


Übungen

Blatt 1 vom 28.10.2010
Blatt 2 vom 11.11.2010
Blatt 3 vom 25.11.2010
Blatt 4
vom 09.12.2010,  Lösung zu Aufgabe P-11 Teil 2
Blatt 5 vom 23.12.2010  In der Definition von "dünn" muss statt der Vereinigung der Durchschnitt stehen, d.h. dünne Mengen enthalten für jedes n nur polynomiell viele Wörter der Länge n.
Blatt 6 vom 20.01.2011

Klausur

 tba


Weiterführende Informationen

Manuskripte

Literatur

  • Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York.1994.
    Dieses Buch liegt ab sofort zur kurzzeitigen Ausleihe in Raum Z1.05, dem Sekretariat des Lehrstuhls Theoretische Informatik, bereit. Wer es ausleiht sollte es spätestens zur Vorlesung wieder mitbringen und bei Bedarf an seine Mitstudenten abgeben. Die Bibliothek hat inzwischen ebenfalls ein Exemplar angeschafft.
  • 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.
  • S. Arora und B. Barak. Complexity Theory: A Modern Approach (fast fertige Vorabversion hier). In diesem Buch sind fast alle Themen der Vorlesung abgedeckt.

  • 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