| 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 |
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 agerfunktion | 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 |
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.
Es wird nach der Vorlesungszeit mündliche Prüfungen geben. Die möglichen Termine sind der 22. Juli sowie der 14., 15. und 16. August. Bitte wenden Sie sich per E-Mail an Frau Bertram, um einen Termin zu vereinbaren.
Die Inhalte der Vorlesung finden sich in diesem Skript. Weitere empfohlene Literatur: