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 2026/2027 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: Dienstag, 09:45 - 11:15, IZ 161. Übung: Mittwoch, 09:45 - 11:15, IZ 161.
Beginn	27.10.
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). Übungen Hausaufgaben Hier werden die Hausaufgabenblätter veröffentlicht. Klausurinformationen Die Klausur findet voraussichtlich am XX.XX.XX ab YY Uhr 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. Altklausur Klausur [WS2526]