Lehrveranstaltungen der Gruppe Komplexitätstheorie

Das regelmäßige Lehrangebot umfasst folgende Veranstaltungen:

• Theoretische Informatik (I-TI)
• Kryptographie und Datensicherheit (I-KD)
• Komplexitätstheorie (I-KT)
• Komplexitätstheorie II (I-KT2)
• Automatentheorie (I-AUT)
• Berechenbarkeitstheorie (I-BER)
• Mathematische Logik (I-ML)
• Seminar (I-SEM)

Die Tabelle zeigt die geplanten Lehrveranstaltungen. Wir bemühen uns diesen Zeitplan zu realisieren, einzelne Abweichungen sind jedoch möglich.

Theoretische Informatik (I-TI, 10 ECTS, 4V+2Ü, Bachelor)
Diese Vorlesung vermittelt grundlegende Begriffe, Ideen, und Vorgehensweisen der gesamten Informatik. Dabei geht es um prinzipielle Möglichkeiten und Beschränkungen des algorithmisch Lösbaren. Dies umfasst Fragen wie: Was ist algorithmische Lösbarkeit? Welche Aufgaben sind durch Maschinen lösbar? Wie schnell können bestimmte Aufgaben gelöst werden? Die Vorlesung gibt eine Einführung in die Gebiete Berechenbarkeit, endliche Automaten, formale Sprachen sowie Komplexität.

Komplexitätstheorie (I-KT, 5 ECTS, 2V+2Ü, Bachelor/Master¹)
Komplexitätstheorie II (I-KT2, 5 ECTS, 2V+2Ü, Master-Vorlesung)
Die Komplexitätstheorie betrachtet algorithmisch lösbare Probleme und fragt, wie schwierig sie zu lösen sind. Beispielsweise untersucht man, welche Probleme innerhalb einer bestimmten Rechenzeit gelöst werden können. Solche Beschränkungen führen zur Definition von Komplexitätsklassen, die diejenigen Probleme zusammenfassen, die sich innerhalb einer bestimmten Rechenzeit lösen lassen. Bekannte Komplexitätsklassen sind beispielsweise P und NP. Die Vorlesung I-KT bietet eine umfassende Einführung in die Komplexitätstheorie, während die Vorlesung I-KT2 weiterführende Fragen betrachtet.  Die behandelten Themen umfassen Beziehungen zwischen Komplexitätsklassen, vollständige Probleme, Relativierbarkeit, Isomorphievermutung, Polynomialzeit-Hierarchie sowie probabilistische Berechnungen.

Kryptographie und Datensicherheit (I-KD, 5 ECTS, 2V+2Ü, Bachelor/Master¹)
Die Vorlesung skizziert die Entwicklung von der klassischen zur modernen Kryptographie. Neben Verschlüsselungsverfahren werden auch interessante, kryptographische Protokolle vorgestellt. Die behandelten Themen umfassen symmetrische Kryptosysteme wie AES, perfekte Sicherheit, asymmetrische Kryptosysteme wie RSA, digitale Signaturen, Identifikation und Secure Multiparty Computation.

Automatentheorie (I-AUT, 5 ECTS, 2V+2Ü, Master)
Die Vorlesung untersucht die Klassen der Chomsky-Hierarchie, vor allem die regulären Sprachen und die sternfreien Sprachen. Neben den aus der Vorlesung Theoretische Informatik bekannten Konzepten wie endliche Automaten, reguläre Ausdrücke und Typ-3-Grammatiken betrachtet man weitere Begriffe wie endliche Monoide und Formeln der Logik erster Stufe über Wörtern. Die Vorlesung zeigt, dass sich die regulären Sprachen und die sternfreien Sprachen durch jedes dieser Konzepte charakterisieren lassen und stellt bis heute ungelöste Entscheidbarkeitsfragen im Zusammenhang mit regulären Sprachen vor.

Berechenbarkeitstheorie (I-BER, 5 ECTS, 2V+2Ü, Master)
Die Vorlesung untersucht verschiedene Formen der algorithmischen Beherrschbarkeit von Mengen, wobei es vor allem um die Frage geht, wie viel Berechenbarkeit in unentscheidbaren Mengen steckt. Die behandelten Themen umfassen berechenbare Funktionen, entscheidbare und aufzählbare Mengen, Reduzierbarkeit, relativierte Berechenbarkeit sowie die arithmetische Hierarchie.

Mathematische Logik (I-ML, 5 ECTS, 2V+2Ü, Master)
Die Vorlesung behandelt die Prädikatenlogik erster Stufe. Zunächst wird gezeigt, dass der Begriff des Folgerns mit dem Begriff des Beweisens übereinstimmt (Gödelscher Vollständigkeitssatz). Überdies geht die Vorlesung der Frage nach, welche mathematischen Theorien entscheidbar, axiomatisierbar bzw. vollständig sind. Wichtige Aussagen sind hier der Gödelsche Unvollständigkeitssatz und die Unentscheidbarkeit der Arithmetik.

Seminar (I-SEM, 5 ECTS, Bachelor/Master)
Das Seminar behandelt in der Regel das Thema Kryptographie.

_{¹ Die beiden Bachelor/Master-Vorlesungen können wahlweise im Informatik-Bachelor oder Informatik-Master eingebracht werden.}