Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Übersicht
  - Team
  - Lehre
  - Arbeiten & Jobs
  - Forschung
  - Publikationen
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- Forschungsverbünde
  - IST.hub

Parametrisierte Algorithmen

Semester	Wintersemester 2025/2026
Studiengang	Informatik Bachelor
IBR Gruppe	ALG (Prof. Fekete)
Art	Vorlesung & Übung
Dozent	Dr. Arne Schmidt Wissenschaftlicher Mitarbeiter aschmidt[[at]]ibr.cs.tu-bs.de +49 531 3913115 Raum 333
LP	5
SWS	2+1+1
Ort & Zeit	Vorlesung: Mittwoch, 13:15 - 14:45, IZ 305. Übung: Mittwoch, 15:00 - 16:30, IZ 305.
Beginn	29.10.2025
Voraussetzungen	Dringend empfohlen: Algorithmen und Datenstrukturen , sowie Theoretische Informatik 2 (oder Algorithmen und Datenstrukturen 2)
Sprache	Deutsch
Scheinerwerb	Studienleistung: Erreichen von mindestens 50 Prozent der Hausaufgabenpunkte. Prüfungsleistung: Mündliche Prüfung oder Klausur (je nach Teilnehmerzahl).
Inhalt	Das Modul behandelt weiterführende Lösungsansätze für NP-schwere Probleme. Auch wenn Probleme theoretisch nicht effizient lösbar sind, können gewisse Strukturen und Parameter gefunden werden, sodass diese Probleme für fixe Parameter effizient gelöst werden können. Speziell werden folgende Themen behandelt: Einführung in parametrisierte Algorithmen und Komplexitäten FPT-Klasse Grundlegende Techniken (Kernelization, Bounded Tree Search, Iterative Compression) Tree-Width W-Hierarchie
Literatur/Links	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!