Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...
- Algorithmen zu entwerfen, die mithilfe von Parametern wie Treewidth, Clique-Width, und Hypertree-Width und den entsprechenden Zerlegungen Probleme effizient lösen.
- Probleme aus Künstlicher Intelligenz und Datenbanktheorie auf verschiedene Weisen grafisch zu modellieren (Primalgraph, Inzidenzgraph, Hypergraph).
- in einfachen Fällen obere und untere Schranken für diese Parameter anzugeben.
Zahlreiche kombinatorische Probleme können auf Bäumen effizient gelöst werden. Mithilfe von Width-Parametern, die die "Baumartigkeit" von Strukturen quantitativ fassen, können Algorithmen für Bäume auf beliebige Eingaben verallgemeinert werden. Diese Algorithmen sind effizient, solange der zugehörige Width-Parameter klein ist.
Diese Lehrveranstaltungen soll einen Überblick über gängige Width-Parametern für Graphen und Hypergraphen und deren Anwendungen in Künstlicher Intelligenz und Datenbanktheorie geben. Zunächst werden Graphenparameter wie Baumweite und Verallgemeinerungen wie Clique-Width und Rank-Width vorgestellt. In weiterer Folge werden wir uns Parametern für Hypergraphen widmen, inbesondere Hypertree-Width und fractional Hypertree-Width.
Zudem werden wir auf Anwendungen von Width-Parametern für verschiedene Probleme eingehen, wie etwas das Zählen aussagenlogischer Modelle, die Auswertung von Conjunctive Queries, und probabilistisches Schließen in Bayes’sches Netzen.
Auf der Basis des Vorlesungsinhalts lösen Studierende Übungsaufgaben zu einzelnen Themenblöcken. Die Lösungen werden in Übungseinheiten präsentiert und diskutiert.
ECTS Breakdown:
20 h Vorlesungen (bzw. Lernvideos) und Lektüre von ergänzender Literatur45 h Ausarbeitung von Übungsblättern10 h Präsentation von Übungsbeispielen-------------------------------------75 h insgesamt
Die Note ergibt sich aus der Anzahl der gelösten Übungsbeispiele und deren Präsentation.
- Jörg Flum, Martin Grohe: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer 2006.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015.
Die Kenntnis grundlegender Begriffe der Graphentheorie sowie Grundkenntnisse in Algorithmik und Komplexitätstheorie werden vorausgesetzt. Vertrautheit mit den in der VU "Algorithmics" behandelten Themen ist von Vorteil.
