02.04.2007: Einführung am Beispiel des Ski-Rental-Problems,
Kompetitive Analyse, Amortisierte Analyse am Beispiel eines
Bitzählers
04.04.2007: Amortisierte Analyse mit Potentialfunktionen, das
List-Accessing-Problem, der Move-To-Front-Algorithmus, Beweis,
dass der Move-To-Front-Algorithmus 2-kompetitiv ist
11.04.2007: Untere Schranke für statisches List-Accessing mit
Durchschnittsargument und mit expliziter Konstruktion eines
Offline-Algorithmus, Einführung randomisierte Online-Algorithmen
16.04.2007: Die Algorithmen BIT und RMTF sowie die Abschätzungen
ihrer kompetitiven Faktoren
18.04.2007: Selbstanpassende Suchbäume: Realisierung der Operationen
SPLAY, INSERT, DELETE, JOIN, SPLIT, amortisierte Kosten von
SPLAY (teilweise)
23.04.2007: Kosten von SPLAY, Vergleich von Splay-Bäumen mit
optimalen statischen Suchbäumen, Einführung Paging
25.04.2007: Optimalität von LFD, Analyse von LIFO, LFU, LRU,
FWF, Markierungsalgorithmen
30.04.2007: Konservative Algorithmen, FIFO, untere Schranke für
deterministische Paging-Algorithmen, Analyse von RANDOM
02.05.2007: Analyse von MARK, untere Schranke für randomisierte
Paging-Algorithmen
07.05.2007: Beweis der unteren Schranke für randomisierte
Paging-Algorithmen, das Zugriffsgraphen-Modell
09.05.2007: Beweis einer unteren Schranke für FIFO im
Zugriffsgraphen-Modell
14.05.2007: Beweis einer oberen Schranke für LRU im
Zugriffsgraphen-Modell, Einführung in das
k-Server-Problem
16.05.2007: Untere Schranke für deterministische
Algorithmen für das k-Server-Problem,
die k-Server-Vermutung, der Algorithmus
Double-Coverage
21.05.2007: Analyse von Double-Coverage,
Einführung Spieltheorie
23.05.2007: reine und gemischte Strategien,
Verhaltensstrategien, Spielbäume
30.05.2007: Umformungen zwischen Spielbäumen und
Matrixdarstellungen, Beispiele für die Unterschiede zwischen
gemischten Strategien und Verhaltensstrategien
04.06.2007: Äquivalenzaussagen zwischen gemischten
Strategien und Verhaltensstrategien
06.06.2007: Request-Answer-Games
11.06.2007: Beweis, dass Randomisierung für den
Gegenspieler nutzlos ist, Beziehungen zwischen den verschiedenen
Arten von Gegenspielern, Beweis, dass Randomisierung gegenüber
adaptiv-offline arbeitenden Gegenspielern nutzlos ist
13.06.2007: Die Sätze von von Neumann und Loomi, Berechnung
von optimalen gemischten Strategien mit linearer Programmierung
18.06.2007: Das Minimax-Prinzip von Yao, List-Factoring
20.06.2007: Beweis der unteren Schranke für randomisierte
Online-Algorithmen für das List-Accessing-Problem
25.06.2007: Restliche Fälle der Analyse von DET, Einführung
in Kauf- und Verkaufsprobleme
27.06.2007: Zusammenhänge zwischen dem
One-Way-Trading-Problem und dem Suchproblem, der Algorithmus RPP
und die untere Schranke für deterministische Online-Algorithmen
für das Suchproblem
02.07.2007: Der Algorithmus EXPO, die Threat-based Policy
für One-Way-Trading
04.07.2007: Abschätzung des kompetitiven Faktors für
die Threat-based Policy
09.07.2007: Der Money-Making-Algorithmus für das Two-Way-Trading-Problem
Die Kapitel 1-4 der Vorlesung entsprechen im Wesentlichen den Kapiteln 1-4
aus dem
Skript von Matthias Westermann, Berthold Vöcking und Christian
Sohler aus dem Jahr 2004.
Weiteres Begleitmaterial steht als
PDF-Datei zur Verfügung.
Anmerkungen und Korrekturen
sind ebenfalls vergfügbar.