Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Logik, Spiele und Automaten (HK) (32 222)

Thema der Vorlesung sind die theoretischen Grundlagen des Entwurfs und der Verifikation reaktiver Systeme, wie beispielsweise Kontrollsysteme oder Kommunikationsprotokolle. Methodisch stützt sich die Theorie auf eine Kombination von Automatentheorie, logischen Systemen zur Beschreibung von Berechnungen, und unendlichen Zwei-Personenspielen. Die Vorlesung gibt eine Einführung in die einzelnen Methoden und vor allem in die Zusammenhänge zwischen den Methoden. Besonderes Augenmerk wird dabei auf algorithmische Anwendungen im Bereich des Systementwurfs und der Verifikation gerichtet.

Parametrische Algorithmen und Komplexitätstheorie (HK) (32 223)

Viele in der Praxis relevante Probleme sind NP-schwer, so dass für sie keine schnellen Lösungen zu erwarten sind. Das entbindet natürlich nicht von dem Wunsch oder der Notwendigkeit, sie trotzdem zu lösen. Einen Ansatzpunkt hierfür bilden parametrische Algorithmen: Die kombinatorische Explosion wird auf einen Teil der Eingabe, den Parameter, beschränkt. Bei kleinem Parameter ist die Laufzeit dann womöglich akzeptabel.
Das gelingt jedoch nicht für alle Probleme. Die parametrische Komplexitätstheorie bietet einen Rahmen, in dem manche parametrisierte Probleme, analog zur NP-Schwere, als parametrisch schwer ausgewiesen werden können.
In der Vorlesung werden wir uns mit beiden Seiten befassen.

Zeit und Petrinetze (HK) (32 224)

Die Petrinetze haben sich als wichtiges Hilfsmittel zur Beherrschung des Entwurfs großer Systeme erwiesen. Als Hauptvorteil der Anwendung von Petrinetzen beim Systementwurf werden gewöhnlich ihre Anschaulichkeit und Analysierbarkeit genannt. Die Anschaulichkeit erleichtert den Übergang von einer verbalen Systembeschreibung zu einer formalen Systemspezifikation als Petrinetz-Modell. Die Analysierbarkeit des Petrinetz-Modells gewährleistet seine Verifizierbarkeit, nämlich die Möglichkeit, die Erfülltheit der Spezifikationen nicht durch Simulation des Modells, sondern durch Analyse zu beweisen. In den klassischen Petrinetzen ist die Zeit nur implizit als kausaler Zusammenhang zwischen Ereignissen modellierbar. In dieser Vorlesung werden wir verschiedene Erweiterungen der klassischen Petrinetze kennen lernen, die eine explizite Modellierung der Zeit ermöglichen, und Möglichkeiten der Analyse für diese zeitabhängigen Netze studieren.

Graphen und Algorithmen 2 (HK) (32 225)

Die Veranstaltung behandelt fortgeschrittene Fragestellungen aus der Graphentheorie. Die ausgewählten Themen führen die Vorlesung auf möglichst einfachem Weg zu aktuellen Forschungsfragen und berühmten offenen Problemen in den jeweiligen Gebieten.

Kryptologie 2 (HK) (32 226)

Die moderne Kryptografie bietet neben Verfahren zur sicheren Übertragung von Nachrichten auch Lösungen für eine ganze Palette weiterer Aufgaben an. Beispielsweise können kryptografische Hashfunktionen die Integrität von Nachrichten und Daten sicherstellen, und digitale Signaturen erlauben es, die Urheberschaft eines Dokuments zu verifizieren.