Komplexitätstheorie SoSe 14

Allgemeines

Veranstaltungsnummer 041241
Modulnummer INF-MA-242
Titel Komplexitätstheorie
Veranstalter Prof. Dr. Thomas Schwentick
Übungsleiter Nils Vortmeier
Klassifikation

Basismodul im Masterstudiengang
Wahlpflichtveranstaltung im Diplomstudiengang
Spezialvorlesung im Diplomstudiengang (SPG 4)

Semester Sommerersemester 2014
SWS 6 (4V+2Ü)
Kreditpunkte 8
Ort und Zeit dienstags, 14:15-16:00 Uhr, OH 12, 3.013
donnerstags, 16:15-18:00 Uhr, OH 12, 3.013
Querverbindungen Grundbegriffe der Theoretischen Informatik, Logik
Voraussetzungen Kenntnisse aus Grundbegriffe der Theoretischen Informatik
InPUD-Forum

https://inpud.cs.tu-dortmund.de/viewforum.php?f=355

 

Aktuelles

  • Am Mittwoch, 25.6., findet die Übung im Raum OH12/3.010 statt.
  • Ab Juni findet die Donnerstagsvorlesung jeweils schon um 16.00 Uhr (s.t.!) statt.
  • Am 26.6. beginnt die Vorlesung bereits um 15.45 Uhr.

Übungsblätter

Hier finden Sie die Übungsblätter.

Informationen zu den Übungen

Termine und Räume der Übungsgruppen.

Inhalt

Während bei der Untersuchung effizienter Algorithmen, die Untersuchung und Weiterentwicklung einzelner Algorithmen im Vordergrund steht, beschäftigt sich die Komplexitätstheorie mit der Klassifikation von Berechnungsproblemen nach ihrer algorithmischen Schwierigkeit. Sie versucht dabei, den inhärenten Ressourcenverbrauch zu bestimmen, z.B. hinsichtlich Rechenzeit oder Speicherplatz. Probleme mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit lösbaren bzw. verifizierbaren Probleme umfassen. Die Frage ob P und NP verschieden sind, wird als eine der bedeutendsten offenen Fragen der theoretischen Informatik, ja sogar der Mathematik, angesehen.

P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen ergeben sich unter anderem bei der Untersuchung der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte Algorithmen, und der approximativen Lösbarkeit von Problemen. Die Vorlesung hat das Ziel, einen breiten Überblick über die grundlegenden Konzepte und Resultate der Komplexitätstheorie zu geben.

Literatur

Die Vorlesung folgt nicht einem einzelnen Buch. Die folgende Literatur ist zu empfehlen.

  • Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
  • Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press. Eine Vorabversion ist (immer noch) verfügbar unter: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft
  • Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
  • Kozen. Theory of Computation. Springer. 2006.
  • Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York. 1994.

Prüfungen und Studienleistungen

Hier finden Sie alle wichtigen Informationen zu Prüfungen und Studienleistungen.