186.856 Structural Decompositions and Algorithms
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VU, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

Nach dem erfolgreichen Abschluss der LVA sollten Studierende mit gängigen Width-Parametern vertraut sein und über deren Anwendungen in KI und Datenbanktheorie Bescheid wissen. Außerdem sollten sie dynamische Programmierung auf den zugehörigen Zerlegungen beherrschen.

Inhalt der Lehrveranstaltung

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.

Weitere Informationen

ECTS Breakdown

18 h Vorlesungen
37 h Vorbereitung der Präsentation
20 h Prüfungsvorbereitung
-------------------------------------
75 h insgesamt

 

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.12:00 - 14:0019.03.2019 - 25.06.2019Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.12:15 - 13:4519.03.2019Seminarraum FAV 01 A (Seminarraum 183/2) Vorbesprechung
Structural Decompositions and Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.19.03.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.19.03.201912:15 - 13:45Seminarraum FAV 01 A (Seminarraum 183/2) Vorbesprechung
Di.26.03.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.02.04.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.09.04.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.30.04.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.07.05.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.14.05.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.21.05.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.28.05.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.04.06.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.18.06.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms
Di.25.06.201912:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) VU: Structural Decompositions and Algorithms

Leistungsnachweis

Die Gesamtnote setzt sich zusammen aus der Note für die Präsentation einer Forschungsarbeit (65%) sowie der Note für eine mündliche Prüfung  (35%).

LVA-Anmeldung

Von Bis Abmeldung bis
06.02.2019 00:00 27.04.2019 00:00 27.04.2019 00:00

Curricula

Literatur

- 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.

Vorkenntnisse

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.

Vorausgehende Lehrveranstaltungen

Sprache

Englisch