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

Approximations- und Online-Algorithmen

Inhalt der Vorlesung

Diese Lerneinheit behandelt approximative Verfahren für schwere Optimierungsprobleme und algorithmische Ansätze zur Lösung von Online-Problemen sowie die Grenzen dieser Ansätze.

Termine

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

Vorlesung Mittwoch 13–15 CAB G 59 Beginn: 19. Februar 2020
Übungen Mittwoch 15–16 CAB G 59 Beginn: 26. Februar 2020

Vorlesungsinhalt

Die Quellenangaben im Vorlesungsteil über Approximationsalgorithmen beziehen sich auf das unten angegebene Buch Algorithmics for Hard Problems von J. Hromkovič.

Die Quellenangaben im Vorlesungsteil über Online-Algorithmen beziehen sich auf das unten angegebene Buch An Introduction to Online Computation von D. Komm sowie das unten angegebene Skript von D. Komm.

Prüfungsstoff

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

Skripte

Hier gibt es Links zu Skripten für Themen der Vorlesung, die in dieser Form nicht in der angegebenen Literatur enthalten sind.

Übungen

Datum Übung Lösung
19.02.2020 Übungsblatt 1 Lösung 1
26.02.2020 Übungsblatt 2 Lösung 2
04.03.2020 Übungsblatt 3 Lösung 3
11.03.2020 Übungsblatt 4 Lösung 4
18.03.2020 Übungsblatt 5 Lösung 5
25.03.2020 Übungsblatt 6 Lösung 6
01.04.2020 Übungsblatt 7 Lösung 7
08.04.2020 Übungsblatt 8 Lösung 8
22.04.2020 Übungsblatt 9 Lösung 9
29.04.2020 Übungsblatt 10 Lösung 10
06.05.2020 Übungsblatt 11 Lösung 11
13.05.2020 Übungsblatt 12 Lösung 12
20.05.2020 Übungsblatt 13 Lösung 13

Literatur

Kontakt: Dr. Dennis Komm, , Haftungsausschluss, letzte Änderung: 28.05.2020 13:50.