EN

Modul

Komplexitätstheorie, mit Anwendungen in der Kryptographie [M-INFO-101575]

Leistungspunkte
6
Turnus
Unregelmäßig
Dauer
1 Semester
Sprache
Deutsch
Level
4
Version
1

Verantwortung

Einrichtung

  • KIT-Fakultät für Informatik

Bestandteil von

Teilleistungen

Identifier Name LP
T-INFO-103014 Komplexitätstheorie, mit Anwendungen in der Kryptographie 6

Erfolgskontrolle(n)

Siehe Teilleistung

Qualifikationsziele

Der /die Studierende

  • kennt die theoretischen Grundlagen der Komplexitätsanalyse eines Problems oder Algorithmus,
  • versteht und erklärt die Struktur gängiger Komplexitätsklassen wie P, NP, oder BPP,
  • kann die asymptotische Komplexität eines gegebenen Problems einschätzen.

Voraussetzungen

Siehe Teilleistung

Inhalt

Was ist ein "effizienter" Algorithmus? Kann jede algorithmische Aufgabe effizient gelöst werden? Oder gibt es inhärent schwierige Probleme? Die Komplexitätstheorie stellt eine streng mathematische Grundlage für die Diskussion dieser Fragen bereit. In dieser Vorlesung behandelte Themen sind

  • Maschinenmodell, Laufzeit- und Speicherkomplexität, Separationen,
  • Nichtdeterminismus, Reduktionen, Vollständigkeit,
  • die polynomiale Hierarchie,
  • Probabilismus, Einwegfunktionen,
  • Alternierung, interaktive Beweise, Zero-Knowledge.

Diese Themen werden mit praktischen Beispielen illustriert. Die Vorlesung gibt einen Ausblick auf Anwendungen der Komplexitätstheorie, insbesondere auf dem Gebiet der Kryptographie.

Empfehlungen

Siehe Teilleistung

Arbeitsaufwand

  1. Präsenzzeit in Vorlesungen: 48 h
  2. Vor-/Nachbereitung derselbigen: 48 h
  3. Prüfungsvorbereitung und Präsenz in selbiger: 84 h