This site is available only in German.

Komplexitätstheorie – SoSe20

Im Logbuch und im Skript finden Sie Informationen zum Inhalt der einzelnen Vorlesungswochen. Pro Woche werden die Videos im Umfang leicht variieren, aber sie sollten im Mittel insgesamt etwa 180 Minuten lang sein.

Aktuelles

Der Vorlesungs- und Übungsbetrieb findet als E-Learning-Angebot statt. Videos mit den Vorlesungsinhalten finden Sie im Logbuch.
  • 10.07.
    Das Material für Woche 13 ist im Logbuch verfügbar. Die Fragestunde zu dieser Woche findet am 22. Juli um 10 Uhr statt.

Inhalt der Veranstaltung

Im ersten Teil der Veranstaltung versuchen wir zu verstehen, welche Eigenschaften ein algorithmisches Problem schwierig machen. Beispielsweise haben wir bereits in der Theoretischen Informatik 1 die Klasse der NP-harten Probleme kennengelernt, zu deren deterministischer Lösung ein polynomieller Aufwand der Ressource "Laufzeit" vermutlich nicht ausreichend ist.

Aber es gibt wichtige Probleme, die noch schwieriger als NP-vollständige Probleme sind. Hierzu gehören etwa die Berechnung von Gewinnstrategien für Zwei-Personen-Spiele oder die Frage, ob zwei NFAs äquivalent sind. Wir führen deshalb die Klasse PSPACE aller in polynomiellem Speicherplatz lösbaren Probleme sowie die Klasse der PSPACE-vollständigen Probleme ein. Desweiteren stellen wir einen allgemeinen Zusammenhang zwischen Parallelisierbarkeit und Speicherplatzkomplexität her.

Im zweiten Teil behandeln wir Themen der Kryptographie, wobei One-Way-Funktionen -- mit den Anwendungen der Pseudo-Random-Generatoren und kollisionsresistenten Hashfunktionen -- und Trapdoor-Funktionen mit der Anwendung der Public-Key-Kryptographie eine große Rolle spielen. "Konventionelle" zahlentheoretische Ansätze können leider von Quantenattacken geknackt werden; deshalb beschreiben wir auch Methoden der Gitter-Kryptographie, die vermutlich Quantenattacken widerstehen. Warum ist bisher ein Nachweis nicht gelungen, dass P eine echte Teilklasse von NP ist? Wir nutzen die Kraft kryptographischer Verfahren aus, um zu zeigen, dass P von NP nicht auf "natürliche Weise" getrennt werden kann.

Im dritten und letzten Teil behandeln wir Quantenalgorithmen. Wir beschreiben das Quanten-Algorithmen zugrunde liegende mathematische Modell und führen Quanten-Schaltkreise ein. Dann wird gezeigt, dass die unstrukturierte Suche mit Grover's Algorithmus quadratisch beschleunigt werden kann. Schließlich wird Shor's Algorithmus für die Faktorisierung besprochen.

Veranstaltungsform

Vorlesung + Übung (SWS: 4+2)

Literaturhinweise

  • S. Aaronson, Quantum Computing since Democritus, Cambridge University Press, 2013.
  • S. Arora und B. Barak, Computational Complexity, a Modern Approach, Cambridge University Press, 2009. [Link]
  • M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.
  • A. Wigderson, Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019. [Link]

Blogs

Termine

Vorlesung:
  • Bis auf Weiteres werden die Videos der aktuellen Vorlesungswoche spätestens am jeweiligen Montag im Logbuch verfügbar sein.
Übung:
  • Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen. Beginnend mit der zweiten Vorlesungswoche erscheinen wöchentlich Übungsblätter, das erste am 27. April.
    Die Abgabe bearbeiteter Übungen erfolgt per E-Mail als PDF-Datei (am liebsten in LaTeX gesetzt) bei Mario Holldack oder Hannes Seiwert. Sie erhalten zeitnah Ihre bewerteten Abgaben mit (handschriftlichen) Korrekturkommentaren per E-Mail zurück. Die Lösungen zu den Aufgaben werden in Form von PDF-Dokumenten oder Videos "vorgerechnet". Die Gestaltung einer Sprechstunde (o.ä.) erfolgt in Absprache mit Ihnen.

Material

Kontakt

Bei Fragen helfen Mario Holldack und Hannes Seiwert gerne weiter.

Prüfung

Studiengänge

Für den Master Informatik (PO 2015) gliedert sich die Veranstaltung auf in
  • Komplexitätstheorie 1 (5 CP, die Veranstaltung nimmt die erste Hälfte der Vorlesungszeit ein) und
  • Komplexitätstheorie 2 (5 CP, die Veranstaltung nimmt die zweite Hälfte der Vorlesungszeit ein).
Für den alten Master Informatik (PO 2007) und den Master Wirtschaftsinformatik können nur beide Veranstaltungen zusammen geprüft werden (im Umfang von 10 CP).

Mündliche Prüfungen/Klausur

Abhängig von der Teilnehmerzahl finden mündliche Prüfungen oder eine Klausur nach Vorlesungsende statt. Mündliche Prüfungen werden nach Vereinbarung abgehalten. Übungspunkte werden bonifiziert: bei Erreichen von 50 % bzw. 70 % der möglichen Übungspunkte kann die Prüfungsnote um einen bzw. zwei Notenschritte verbessert werden, falls die Prüfung bestanden ist.