Zum Inhalt

Komplexitätstheorie

Veranstaltungsnummer 041241
Modulnummer INF-MA-242
Titel Komplexitätstheorie
Veranstalter Prof. Dr. Thomas Schwentick
Übungsleiter Prof. Dr. Thomas Schwentick
Klassifikation Basismodul im Masterstudiengang
Semester Sommersemester 2022
SWS 6 (4V+2Ü)
Kreditpunkte 8
Ort und Zeit Dienstags, 14:15 - 16:00 Uhr, (tba)

Donnerstags, 16:15 - 18:00 Uhr, (tba)
Querverbindungen Grundbegriffe der Theoretischen Informatik, Logik
Voraussetzungen Kenntnisse aus Grundbegriffe der Theoretischen Informatik
Moodle-Arbeitsraum ja


Zur Kursbeschreibung

Aktuelles

Die Veranstaltung beginnt voraussichtlich am 7.4.2022.

Genauere Informationen zur Durchführung (online/präsenz etc.) werden im Moodle-Arbeitsraum bekanntgegeben.

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.


Im ersten Teil stehen klassische Resultate im Vordergrund: z.B. die Korrespondenz zwischen Spielen und Speicherplatz-Beschränkungen, der Nachweis, dass sich mit mehr Platz oder Zeit auch mehr Probleme lösen lassen, weitere grundlegende Beziehungen zwischen Zeit- und Platzbasierten Klassen, und die Komplexitätswelt zwischen NP und PSPACE. Außerdem wird die Theorie der effizienten Parallelisierbarkeit betrachtet.

Der zweite Teil der Vorlesung widmet sich dem Umgang mit schwierigen Optimierungsproblemen und stellt vor allem komplexitätstheoretische Grundlagen von parametrisierten und Approximationsalgorithmen vor.

Weiterhin wird die Komplexitätstheorie paralleler, zufallsbasierter, parametrisierter und approximativer Algorithmen in Grundzügen vorgestellt.

Der dritte Teil der Vorlesung beschäftigt sich mit fortgeschrittenen Themen: Komplexitätstheorie des interaktiven Rechnens, des probabilistischen Beweisens und der Kryptographie, sowie bedingte Komplexitätsschranken.

 

Literatur

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

  • Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press. Eine Vorabversion ist (immer noch) verfügbar unter: http://theory.cs.princeton.edu/complexity/book.pdf
  • Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
  • 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.

Anfahrt & Lageplan

Der Campus der Technischen Universität Dortmund liegt in der Nähe des Autobahnkreuzes Dortmund West, wo die Sauerlandlinie A45 den Ruhrschnellweg B1/A40 kreuzt. Die Abfahrt Dortmund-Eichlinghofen auf der A45 führt zum Campus Süd, die Abfahrt Dortmund-Dorstfeld auf der A40 zum Campus-Nord. An beiden Ausfahrten ist die Universität ausgeschildert.

Direkt auf dem Campus Nord befindet sich die S-Bahn-Station „Dortmund Universität“. Von dort fährt die S-Bahn-Linie S1 im 15- oder 30-Minuten-Takt zum Hauptbahnhof Dortmund und in der Gegenrichtung zum Hauptbahnhof Düsseldorf über Bochum, Essen und Duisburg. Außerdem ist die Universität mit den Buslinien 445, 447 und 462 zu erreichen. Eine Fahrplanauskunft findet sich auf der Homepage des Verkehrsverbundes Rhein-Ruhr, außerdem bieten die DSW21 einen interaktiven Liniennetzplan an.
 

Zu den Wahrzeichen der TU Dortmund gehört die H-Bahn. Linie 1 verkehrt im 10-Minuten-Takt zwischen Dortmund Eichlinghofen und dem Technologiezentrum über Campus Süd und Dortmund Universität S, Linie 2 pendelt im 5-Minuten-Takt zwischen Campus Nord und Campus Süd. Diese Strecke legt sie in zwei Minuten zurück.

Vom Flughafen Dortmund aus gelangt man mit dem AirportExpress innerhalb von gut 20 Minuten zum Dortmunder Hauptbahnhof und von dort mit der S-Bahn zur Universität. Ein größeres Angebot an internationalen Flugverbindungen bietet der etwa 60 Kilometer entfernte Flughafen Düsseldorf, der direkt mit der S-Bahn vom Bahnhof der Universität zu erreichen ist.