Online-Algorithmen

BA-INF 119

Termine

Art Wann Wo Beginn Dozent
V4 Dienstag 12:30 - 14:00
Donnerstag 12:30 - 14:00
AVZ III / HS 1
AVZ III / HS 1
12. April 2016 Röglin
Ü2 Mittwoch 10:15 - 12:00
Freitag 10:15 - 12:00
AVZ III / A7b
AVZ III / A7b
20. April 2016 Großwendt
Plitt

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
12. April 1 Einleitung
2 Paging
2.1 Deterministische Algorithmen
2.1.1 Markierungsalgorithmen
14. April 2.1.1 Markierungsalgorithmen (Fortsetzung)
2.1.2 Untere Schranken
19. April 2.1.3 Optimaler Offline-Algorithmus
2.1.4 Zusammenfassung der Ergebnisse
2.2 Randomisierte Algorithmen
2.2.1 Potentialfunktionen
21. April 2.2.2 Analyse von RANDOM
26. April 2.2.2 Analyse von RANDOM (Fortsetzung)
2.2.3 Analyse von MARK
28. April 2.2.3 Analyse von MARK (Fortsetzung)
2.2.4 Untere Schranke für randomisierte Online-Algorithmen
3. Mai 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
10. Mai 3.2 Untere Schranke für deterministische Algorithmen
3.3 Das k-Server-Problem auf Linien und Bäumen
3.3.1 Analyse des DC-Algorithmus auf der Linie
12. Mai 3.3.1 Analyse des DC-Algorithmus auf der Linie (Fortsetzung)
3.3.2 Analyse des DC-Algorithmus auf Bäumen
24. Mai 3.3.2 Analyse des DC-Algorithmus auf Bäumen (Fortsetzung)
3.3.3 Anwendungen des DC-Algorithmus
31. Mai 3.4 Das 2-Server-Problem im euklidischen Raum
4 Approximation von Metriken
4.1 Approximation durch Baummetriken
2. Juni 4.1.1 Hierarchische Partitionen und Baummetriken
4.1.2 Erzeugung von hierarchischen Partitionen
4.1.3 Analyse des Streckungsfaktors
7. Juni 4.1.3 Analyse des Streckungsfaktors (Fortsetzung)
9. Juni 4.2 Anwendung auf das k-Server-Problem
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
14. Juni 5.1.2 Algorithmen für Online-Suche (Fortsetzung)
5.1.3 Optimaler Online-Algorithmus für One-Way-Trading
16. Juni 5.1.3 Optimaler Online-Algorithmus für One-Way-Trading (Fortsetzung)
21. Juni 5.2 Economical Caching
5.2.1 Ein Reservationspreisalgorithmus
5.2.2 Untere Schranken
23. Juni 5.2.2 Untere Schranken (Fortsetzung)
5.2.3 Algorithmen mit fester Lagerfunktion
5.2.4* Ein optimaler Online-Algorithmus
28. Juni 6 Scheduling
6.1 Identische Maschinen
6.2 Maschinen mit Geschwindigkeiten
30. Juni 6.2 Maschinen mit Geschwindigkeiten (Fortsetzung)
7 Das Online-Matching-Problem
7.1 Deterministische Algorithmen
7.2* Randomisierte Algorithmen
5. Juli 7.3 Random-Order-Modell
7.3.1 Das klassische Sekretärinnenproblem
7.3.2 Das Online-Matching-Problem in gewichteten Graphen
7. Juli 7.3.2 Das Online-Matching-Problem in gewichteten Graphen (Fortsetzung)
7.3.3 Eine untere Schranke
12. Juli 8 Das Minimax-Prinzip
8.1 Spielbaumauswertung
8.2 Das Minimax-Prinzip
8.2.1 2-Personen-Nullsummenspiele
8.2.2 Anwendung auf randomisierte Algorithmen
14. Juli 8.3 Untere Schranke für Spielbaumauswertung
8.4 Anwendungen auf Online-Probleme
8.4.1 Paging
8.4.2 Matching

Mit * markierte Abschnitte sind nicht prüfungsrelevant.

Ü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 zwei 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.

Bitte melden Sie sich bis zum 15. April 2015 im Tutorienvergabesystem für die Übungen an.

  • Präsenzblatt (Besprechung in KW 16, keine Abgabe)
  • Übungsblatt 1 (Besprechung in KW 17, Abgabe bis 19.04., 14:00 Uhr, in der Vorlesung)
  • Übungsblatt 2 (Besprechung in KW 18, Abgabe bis 26.04., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 3 (Besprechung in KW 19, Abgabe bis 03.05., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 4 (Besprechung in KW 22, Abgabe bis 10.05., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 5 (Besprechung in KW 23, Abgabe bis 31.05., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 6 (Besprechung in KW 24, Abgabe bis 07.06., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 7 (Besprechung in KW 25, Abgabe bis 14.06., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 8 (Besprechung in KW 26, Abgabe bis 21.06., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 9 (Besprechung in KW 27, Abgabe bis 28.06., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 10 (Besprechung in KW 28, Abgabe bis 05.07., 14:00 Uhr, in den Briefkasten der Vorlesung)
  • Übungsblatt 11 (Besprechung in KW 29, keine Abgabe)

In den Kalenderwochen KW 20 und KW 21 finden keine Übungen statt.

Prüfungen

Es wird am Ende der Vorlesungszeit mündliche Prüfungen geben. Die möglichen Termine für die erste Prüfung sind 27.07., 28.07. und 29.07. Bitte melden Sie sich spätestens bis zum 30.06. bei Antje Bertram, um einen Termin auszumachen. Die Nachprüfungen werden am 26.09. stattfinden.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.

Weitere empfohlene Literatur:

lehre/ss16/vl-online.txt · Zuletzt geändert: 2016/07/14 15:25 von roeglin

Benutzer-Werkzeuge