Parametrisierte Algorithmen

Vorlesung: Mittwoch, 13:15 - 14:45, IZ 305.

Übung: Mittwoch, 15:00 - 16:30, IZ 305.

Studienleistung: Erreichen von mindestens 50 Prozent der Hausaufgabenpunkte.

Prüfungsleistung: Mündliche Prüfung oder Klausur (je nach Teilnehmerzahl).

• Einführung in parametrisierte Algorithmen und Komplexitäten
• FPT-Klasse
• Grundlegende Techniken (Kernelization, Bounded Tree Search, Iterative Compression)
• Tree-Width
• W-Hierarchie

• Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh: Parameterized Algorithms. [pdf]

Material

Hier werden die Vorlesungsmaterialien veröffentlicht (in der Regel spätestestens einen Tag nach der Vorlesung).

Vorlesung 00: Intro [pdf]

Vorlesung 01: Vertex Cover [pdf]

Vorlesung 02: Kernelization [pdf] [Notizen]

Vorlesung 03: Beispiele [pdf] [Notizen]

Vorlesung 04: Matchings [pdf] [Notizen]

Vorlesung 05: Crown Decomposition [pdf] [Notizen]

Vorlesung 06: Bounded Tree Search [pdf]

Vorlesung 07: Feedback Vertex Set [Notizen]

Vorlesung 08: Iterative Compression [pdf] [Notizen]

Vorlesung 09: Baumweite [Notizen]

Vorlesung 10: Intractability [Notizen]

Vorlesung 11: W-Hierarchie [Notizen]

Vorlesung 12: Zusammenfassung [pdf]

Übungen

Übung 1 + 2: Vertex Cover [pdf]

Übung 3: Kronenzerlegung, Sunflower-Theorem [pdf]

Übung 4: Bounded-Tree-Search, Cluster-Editing [pdf]

Übung 5: Iterative Compression, Baumweite [pdf]

Hausaufgaben

Hier werden die Hausaufgabenblätter veröffentlicht.

Blatt 1: [pdf], Besprechung: 26.11.25

Blatt 2: [pdf], Besprechung: 10.12.25

Blatt 3: [pdf], Besprechung: 07.01.26

Blatt 4: [pdf], Besprechung: 21.01.26

Blatt 5: [pdf], Besprechung: 04.02.26

Evaluationsergebnisse

Die Ergebnisse der Evaluation als [pdf].

Klausurinformationen

Die Klausur findet voraussichtlich am 12.03.26 von 13 bis 15 Uhr im Raum SN 19.1 statt. Bitte seid 15 Minuten eher anwesend. Benötigt wird ein dokumentenechter Stift und der Studierendenausweis. Eigenes Papier, Unterlagen oder andere Hilfsmittel sind nicht erlaubt.

Die Einsicht findet am 19.03. zwischen 09:00 und 09:45 im Raum IZ 313 statt. Bitte bringt euren Studierendenausweis mit.

Eine Statistik mit den Ergebnissen: [pdf]

Musterklausur

Es gibt eine Musterklausur, die hauptsächlich aus Hausaufgaben besteht. Wichtig: Die Aufgaben wurden nicht auf Zeit getestet, noch geben die angegebenen Punkte eine korrekte Punkteverteilung. Das Muster soll lediglich aufzeigen, welche Arten von Aufgabentypen in der Klausur vorkommen können. Das Muster kann hier heruntergeladen werden.

Mailingliste

Bitte meldet Euch mit eurer TU-BS-Adresse auf der Mailingliste an!