Komplexitätstheorie – SoSe19

Im Logbuch finden Sie Informationen zum Inhalt der einzelnen Vorlesungsstunden.

Aktuelles

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.
  • M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.

Blogs

Termine

Vorlesung:
  • Montag, 12 (c.t.) bis 14 Uhr im Magnus-Hörsaal
  • Dienstag, 8:30 bis 10:00 Uhr im Magnus-Hörsaal
Übung:
  • Mittwoch, 8:30 bis 10:00 Uhr in SR 11

Material

Kontakt

Bei Fragen helfen Hannes Seiwert und Mario Holldack gerne weiter.

Übungsbetrieb

Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen. Die Abgabe bearbeiteter Blätter erfolgt

  • montags
  • vor Vorlesungsbeginn
  • im Hörsaal.

Falls ein Erscheinen nicht einzurichten ist, ist eine frühere Abgabe im großen Briefkasten zwischen Raum 312 und 313 (RMS 11-15) ebenfalls zulässig. Dieser Briefkasten wird am Abgabetag vor Vorlesungsbeginn geleert. Später eingeworfene Abgaben werden nicht gewertet.

Damit ein reibungsloser Ablauf gewährleistet werden kann, muss jede Abgabe im Kopf der Titelseite gut leserlich mit Name und Matrikelnummer versehen sein.

Abgaben, die mehrere Blätter umfassen, müssen mittels eines Tackers zusammengefügt sein. An der Ecke zusammengefaltete Blätter, Büroklammern o.ä. ersetzen keine Tackernadel! Für nicht getackerte Abgaben kann nicht gewährleistet werden, dass sie vollständig korrigiert werden.

Übungsgruppen

Beginnend mit der zweiten Vorlesungswoche erscheinen wöchentlich Übungsblätter. Das erste Übungsblatt erscheint am Dienstag, dem 23. April. Die Übungsgruppe trifft sich das erste Mal ausnahmsweise am Dienstag, dem 30. April zur Besprechung des ersten Übungsblattes. In den folgenden Wochen findet das Tutorium mittwochs statt.

Prüfung

Studiengänge

Für den Master Informatik (PO 2015) gliedert sich die Veranstaltung auf in
  • Komplexitätstheorie 1 (5 CP, die Veranstaltung findet vom 15.04. bis zum 31.05. statt) und
  • Komplexitätstheorie 2 (5 CP, die Veranstaltung findet vom 03.06. bis zum 19.07. statt).
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.