Online-Algorithmen

Termine

Art Wann Wo Beginn Dozent(in)
V4 Montag 12:15 - 13:45
Mittwoch 12:15 - 13:45
CP1-HSZ / Hörsaal 3 9. April 2018 Heiko Röglin
Ü2 Montag 10:00 - 11:30
Freitag 10:15 - 11:45
INF / B-IT / Seminarraum 2.050, Informatik V 16. April 2018 Anna Großwendt

Inhalt

Bei der Lösung von Optimierungsproblemen sind wir in den einführenden Vorlesungen stets davon ausgegangen, dass die konkrete Eingabe dem Algorithmus von Anfang an komplett bekannt ist. In manchen Anwendungen ist das aber nicht der Fall und die Eingabe wird erst Schritt für Schritt aufgedeckt. Probleme mit dieser Eigenschaft nennt man Online-Probleme. Die Speicherverwaltung eines Rechners muss beispielsweise bei dem Ausführen eines Programms, ohne dessen zukünftiges Verhalten zu kennen, entscheiden, welche Seiten im CPU-Cache gehalten und welche in den Hauptspeicher ausgelagert werden. Auch im Wirtschaftsleben sind Online-Probleme keine Seltenheit. Autofahrer stehen beispielsweise oft vor der Entscheidung, wann sie eine Tankstelle anfahren, ohne die Entwicklung der Spritpreise in den nächsten Tagen zu kennen.

Man könnte meinen, dass man bei solchen Online-Problemen algorithmisch wenig ausrichten kann. Weiß man nicht, auf welche Seiten ein Programm als nächstes zugreifen wird, so kann man scheinbar keine sinnvolle Entscheidung treffen, welche Seiten in den Hauptspeicher ausgelagert werden sollten. Tatsächlich ist dies aber nicht der Fall und man kann durch geschicktes Verhalten bei Online-Problemen besser abschneiden als bei beliebigem Verhalten. Wir werden uns in der Vorlesung mit dem Entwurf und der Analyse von solchen Online-Algorithmen beschäftigen.

Datum Inhalt
9. April 1 Einleitung
2 Paging
2.1 Deterministische Algorithmen
2.1.1 Markierungsalgorithmen
11. April 2.1.1 Markierungsalgorithmen (Fortsetzung)
2.1.2 Untere Schranken
2.1.3 Optimaler Offline-Algorithmus
16. April 2.1.3 Optimaler Offline-Algorithmus (Fortsetzung)
2.1.4 Zusammenfassung der Ergebnisse
2.2 Randomisierte Algorithmen
2.2.1 Potentialfunktionen
18. April2.2.2 Analyse von RANDOM
25. April2.2.3 Analyse von MARK
30. April2.2.4 Untere Schranke für randomisierte Online-Algorithmen
3 Das k-Server-Problem
3.1 Einführende Bemerkungen
3.1.1 Der Greedy-Algorithmus
3.1.2 Die k-Server-Vermutung
2. Mai3.1.3 Optimale Offline-Algorithmen
3.2 Untere Schranke für deterministische Algorithmen
7. Mai3.3 Das k-Server-Problem auf Linien und Bäumen
3.3.1 Analyse des DC-Algorithmus auf der Linie
9. Mai3.3.2 Analyse des DC-Algorithmus auf Bäumen
3.3.3 Anwendungen des DC-Algorithmus
14. Mai4 Approximation von Metriken
4.1 Approximation durch Baummetriken
4.1.1 Hierarchische Partitionen und Baummetriken
28. Mai4.1.1 Hierarchische Partitionen und Baummetriken
4.1.2 Erzeugung von hierarchischen Partitionen
4.1.3 Analyse des Streckungsfaktors
30. Mai 4.1.3 Analyse des Streckungsfaktors (Fortsetzung)
4.2 Anwendung auf das k-Server-Problem
4. Juni 5 Online-Probleme beim Handel
5.1 Online-Suche und One-Way-Trading
5.1.1 Zusammenhang der beiden Problemvarianten
5.1.2 Algorithmen für Online-Suche
6. Juni 5.1.3 Optimaler Online-Algorithmus für One-Way-Trading
11. Juni 5.2 Economical Caching
5.2.1 Ein Reservationspreisalgorithmus
5.2.2 Untere Schranken
13. Juni 5.2.2 Untere Schranken (Fortsetzung)
5.2.3 Algorithmen mit fester Lagerfunktion
18. Juni 6 Scheduling
6.1 Identische Maschinen
6.2 Maschinen mit Geschwindigkeiten
20. Juni 6.2 Maschinen mit Geschwindigkeiten (Fortsetzung)
7 Das Online-Matching-Problem
7.1 Deterministische Algorithmen

Übungsblätter

Prüfungen

Die mündlichen Prüfungen werden zwischen dem 23. und 25. Juli 2018 stattfinden. Bitte wenden Sie sich an Frau Andrade zur Vereinbarung eines Prüfungstermins.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.

Weitere empfohlene Literatur:

  • [BE05] Allan Borodin und Ran El-Yaniv. Online Computation and Competitive Analysis. ISBN: 978-0521619462, Cambridge University Press, 2005.
  • [Bl09] Norbert Blum. Skript zur Vorlesung Online-Algorithmen. Universität Bonn, Sommersemester 2009.

Page Tools