Graphzerlegungen und algorithmische Anwendungen

 

Vorlesung im Wintersemester 2018/2019

 

Inhalt

Graphzerlegungen sind ein nützliches Hilfsmittel um effiziente Algorithmen für viele verschiedene Anwendungsbereiche zu entwickeln. Dazu gehören kombinatorische Optimierungsprobleme sowie probabilistische Inferenz in dem Bereich der künstlichen Intelligenz. Zerlegungen und auch Unzerlegbarkeit von Graphen können außerdem sehr hilfreich dabei sein, die Stuktur von Graphen und Netzwerken zu verstehen.

Diese Vorlesung bietet eine Einführung in Zusammenhänge und Zerlegungen von Graphen und anderen Strukturen. Hier gibt es ein elegantes mathematisches Framework, welches so genannte connectivity systems verwendet. Im Zentrum dieser Theorie steht die Dualität von Zerlegungen und stark zusammenhängenden Bereichen, die durch Objekte mit dem Namen 'Tangle' beschrieben werden können.

Dieser Kurs legt einen besonderen Fokus auf die algorithmischen Aspekte dieser Theorie. Wir werden effiziente Algorithmen zur Berechnung von Zerlegungen vorstellen, sowie Algorithmen, welche Zerlegungen verwenden um andere Probleme effizient zu lösen. In diesem Zusammenhang untersuchen wir die allgemeinen Techniken 'dynamic programming' und 'divide-and-conquer'.

Voraussetzungen

Diese Veranstaltung ist an Studierende im Masterstudium gerichtet, die ein klares Interesse an Theoretischer Informatik haben.

 

Organisation

Vortragssprache ist Englisch.

Dozent

Martin Grohe

Mündliche Prüfung

Zum erfolgreichen Absolvieren dieser Veranstaltung gehört das Bestehen einer mündlichen Prüfung.
Die genauen Details zur Prüfung können den Ankündigungen im L2P entnommen werden.
Die Prüfungstermine sind nach Vereinbarung.