Online-Algorithmen

Termine

Art Wann Wo Beginn LP Dozent
V4 Dienstag 08:30 - 10:00
Donnerstag 8:30 - 10:00
AVZ III / HS 1
AVZ III / HS 1
9. April 2013 5,5 Röglin
Ü2 Dienstag 10:15 - 11:45
Donnerstag 10:15 - 11:45
Donnerstag 16:30 - 18:00
AVZ III / A6c
AVZ III / A6c
LBH / E.08
16. April 2013 3,5 Brunsch, Röglin, Rösner

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 Literatur
9. April 1 Einleitung
2 Paging
2.1 Deterministische Algorithmen
2.1.1 Markierungsalgorithmen
Skript
11. April 2.1.1 Markierungsalgorithmen (Fortsetzung)
2.1.2 Untere Schranken
2.1.3 Optimaler Offline-Algorithmus
Skript
16. April 2.1.3 Optimaler Offline-Algorithmus (Fortsetzung)
2.1.4 Zusammenfassung der Ergebnisse
2.2 Randomisierte Algorithmen
2.2.1 Potentialfunktionen
Skript
18. April 2.2.2 Analyse von RANDOM Skript
23. April 2.2.2 Analyse von RANDOM (Fortsetzung)
2.2.3 Analyse von MARK
Skript
25. April 2.2.3 Analyse von MARK (Fortsetzung)
2.2.4 Untere Schranke für randomisierte Online-Algorithmen
Skript
30. April 3 Das k-Server-Problem
3.1 Einführende Bemerkungen
3.1.1 Der Greedy-Algorithmus
3.1.2 Die k-Server-Vermutung
3.1.3 Optimale Offline-Algorithmen
Skript
2. Mai 3.2 Untere Schranke für deterministische Algorithmen
3.3 Das k-Server-Problem auf Linien und Bäumen
Skript
7. Mai 3.3.1 Analyse des DC-Algorithmus auf der Linie Skript
14. Mai 3.3.2 Analyse des DC-Algorithmus auf Bäumen Skript
16. Mai 3.3.3 Anwendungen des DC-Algorithmus
3.4 Das 2-Server-Problem im euklidischen Raum
Skript
28. Mai 4 Approximation von Metriken
4.1 Approximation durch Baummetriken
4.1.1 Hierarchische Partitionen und Baummetriken
4.1.2 Erzeugung von hierarchischen Partitionen
Skript
4. Juni 4.1.3 Analyse des Streckungsfaktors Skript
6. Juni 4.1.3 Analyse des Streckungsfaktors (Fortsetzung)
4.2 Anwendung auf das k-Server-Problem
Skript
11. 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
Skript
13. Juni 5.1.2 Algorithmen für Online-Suche (Fortsetzung)
5.1.3 Optimaler Online-Algorithmus für One-Way-Trading
Skript
18. Juni 5.1.3 Optimaler Online-Algorithmus für One-Way-Trading (Fortsetzung)
5.2 Economical Caching
5.2.1 Ein Reservationspreisalgorithmus
Skript
20. Juni 5.2.1 Ein Reservationspreisalgorithmus (Fortsetzung)
5.2.2 Untere Schranken
Skript
25. Juni 5.2.2 Untere Schranken (Fortsetzung)
5.2.3 Algorithmen mit fester Lagerfunktion
Skript
27. Juni 5.2.4 Ein optimaler Online-Algorithmus
6 Scheduling
6.1 Identische Maschinen
Skript
2. Juli 6.2 Maschinen mit Geschwindigkeiten Skript
4. Juli 7 Das Online-Matching-Problem
7.1 Deterministische Algorithmen
7.2 Randomisierte Algorithmen
Skript
9. Juli 7.2 Randomisierte Algorithmen (Fortsetzung) Skript
11. Juli 7.2 Randomisierte Algorithmen (Fortsetzung)
8 Sekretärinnenprobleme
8.1 Klassische Problemvariante
Skript
Wikipedia
[BIK07]
16. Juli 8.2 Verallgemeinerte Problemvariante
8.2.1 k-faches Sekretärinnenproblem
[BIK07]
[BIKK07] (Section 3)
18. Juli Wiederholung Skript

Übungen

Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von drei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden. Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.

  • Präsenzblatt (Besprechung in KW 16, keine Abgabe)
  • Übungsblatt 1 (Besprechung in KW 17, Abgabe bis 16.04., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 2 (Besprechung in KW 18, Abgabe bis 23.04., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 3 (Besprechung in KW 19, Abgabe bis 30.04., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 4 (Besprechung in KW 20, Abgabe bis 07.05., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 5 (Besprechung in KW 22, Abgabe bis 14.05., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 6 (Besprechung in KW 23, Abgabe bis 28.05., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 7 (Besprechung in KW 24, Abgabe bis 04.06., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 8 (Besprechung in KW 25, Abgabe bis 11.06., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 9 (Besprechung in KW 26, Abgabe bis 18.06., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 10 (Besprechung in KW 27, Abgabe bis 25.06., 12:00 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 11 (Besprechung in KW 28, Abgabe bis 02.07., 12:00 Uhr, im Briefkasten in der Römerstraße)

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript. Weitere empfohlene Literatur:

lehre/ss13/online-algorithmen.txt · Zuletzt geändert: 2014/06/23 12:05 von roeglin

Benutzer-Werkzeuge