Dr. H.-J. Böckenhauer, Dr. D. Komm — Departement Informatik — FS 2021

Algorithmik für schwere Probleme

Inhalt der Vorlesung

Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit parametrisierten Algorithmen und exakten Exponentialzeitalgorithmen.

Termine

Die Vorlesung und die Übungen finden bis auf Weiteres als Videokonferenz mit Zoom statt. Die für die Vorlesung eingeschriebenen Studierenden erhalten jeweils eine Einladung mit der Meeting-Nummer per E-Mail.

Vorlesung Dienstag 9–11 CAB G 57 Beginn: 23. Februar 2021
Übungen Dienstag 11–12 CAB G 57 Beginn: 2. März 2021

Vorlesungsinhalt

Prüfungsstoff

Der Prüfungsstoff umfasst alles, was in der Vorlesung behandelt wurde, sowie den Stoff der Übungsblätter und Lösungen.

Skripte

Unter Algorithmics for Hard Problems stehen Entwürfe von Skripten zu folgenden Vorlesungsteilen zur Verfügung:

Der ebenfalls verfügbare Artikel “Improved Approximations for Hard Optimization Problems via Problem Instance Classification” umfasst in Abschnitt 5 den Stoff der letzten Vorlesung vom 01.06.2021.

Das Passwort für den Zugriff wird den Teilnehmenden per E-Mail mitgeteilt.

Vorlesungsaufzeichnung

Die Videos der Vorlesung stehen ebenfalls unter Algorithmics for Hard Problems zur Verfügung.

Übungen

Die Übungen werden von Martin Raszyk betreut. Die Abgaben der Lösungen können per E-Mail an ihn gesendet werden, er steht auch für Fragen zum Inhalt und zur Organisation der Übungen zur Verfügung.

Hinweis zu Aufgabe 7: Bei der Definition eines Brambles in der Vorlesung wurde vergessen zu erwähnen, dass die einzelnen Knotenmengen Bi zusammenhängend sein müssen.

Datum Übung Lösung
23.02.2021 Blatt 1 Lösung 1
02.03.2021 Blatt 2 Lösung 2
09.03.2021 Blatt 3 Lösung 3
16.03.2021 Blatt 4 Lösung 4
23.03.2021 Blatt 5 Lösung 5
30.03.2021 Blatt 6 Lösung 6
13.04.2021 Blatt 7 Lösung 7
20.04.2021 Blatt 8 Lösung 8
27.04.2021 Blatt 9 Lösung 9
04.05.2021 Blatt 10 Lösung 10
11.05.2021 Blatt 11 Lösung 11
18.05.2021 Blatt 12 Lösung 12
25.05.2021 Blatt 13

Literatur