Am 30. Juli 2024 wird es aufgrund einer wichtigen Datenbankaktualisierung zwischen 8 und 11 Uhr zu Serviceunterbrechungen im Bereich Student-Self-Service und Personalbedarf kommen. Vielen Dank für Ihr Verständnis.

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.

2024S, VU, 2.0h, 3.0EC
TUWELLectureTube

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • LectureTube Lehrveranstaltung
  • Format der Abhaltung: Präsenz

Lernergebnisse

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.

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.

Methoden

Studierende führen ein kurzes Projekt durch, bei dem es sich um eine Implementation oder eine kurze schriftliche Ausarbeitung handeln kann.

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Vorbesprechung ZOOM link (oder Präsenz in FAV 01 B)

https://tuwien.zoom.us/j/66275772564?pwd=eElGUHBraGpSWHJKZ3FNQmhGYkJhdz09

ECTS Breakdown:

20 h Vorlesungen (bzw. Lernvideos) und Lektüre von ergänzender Literatur
45 h Projekt oder Ausarbeitung von Übungsblättern
10 h Präsentation von Projekt / Übungsbeispielen
-------------------------------------
75 h insgesamt 

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mi.10:00 - 11:0006.03.2024Seminarraum FAV 01 B (Seminarraum 187/2) Vorbesprechung
Mo.10:00 - 13:0008.04.2024 - 29.04.2024Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Do.11:00 - 14:0011.04.2024 - 25.04.2024Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Structural Decompositions and Algorithms - Einzeltermine
TagDatumZeitOrtBeschreibung
Mi.06.03.202410:00 - 11:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorbesprechung
Mo.08.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Do.11.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Mo.15.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Do.18.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Mo.22.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Do.25.04.202411:00 - 14:00Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Mo.29.04.202410:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung

Leistungsnachweis

Die Note basiert auf einer informellen mündlichen Präsentation des Projekts. Weitere Möglichkeiten werden in der Vorlesung besprochen.

LVA-Anmeldung

Von Bis Abmeldung bis
26.02.2024 00:00 30.04.2024 00:00 30.04.2024 00:00

Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
066 645 Data Science Keine Angabe
066 646 Computational Science and Engineering Keine Angabe
066 926 Business Informatics Keine Angabe
066 931 Logic and Computation Keine Angabe
066 937 Software Engineering & Internet Computing Keine Angabe
066 938 Technische Informatik Gebundenes Wahlfach

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