Komplexitätstheorie, mit Anwendungen in der Kryptographie

  • Typ: Vorlesung (V)
  • Semester: WS 19/20
  • Zeit: 15.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    17.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    22.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    24.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    29.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    31.10.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    05.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    07.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    12.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    19.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    21.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    26.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    28.11.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    03.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    05.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    10.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    12.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    17.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    19.12.2019
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    07.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    09.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    16.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    21.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    23.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    28.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    30.01.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    04.02.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    06.02.2020
    09:45 - 11:15 wöchentlich
    50.34 Raum 301
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
  • Dozent: Prof. Dr. Dennis Hofheinz
  • SWS: 4
  • LVNr.: 2400063
BeschreibungWas 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.

Arbeitsbelastung1. Präsenzzeit in Vorlesungen, Übungen: 46h
2. Vor-/Nachbereitung der selbigen: 64h
3. Klausurvorbereitung und Präsenz in selbiger: 70 h
ZielDer /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.