Inhalt der Vorlesung

• 6.4.2006: Einführung: Online-Algorithmus für das Ski-Rental-Problem, Beweis seiner Optimalität, grundlegende Begriffe, amortisierte Analyse am Beispiel eines Binärzählers
  
• 13.4.2006: List-Accessing-Problem: Aufgabenstellung, der Move-To-Front-Algorithmus, eine untere Schranke für deterministische Algorithmen
  
• 20.4.2006: Randomisierte Online-Algorithmen, der BIT-Algorithmus und der Random-Move-to-Front-Algorithmus für das List-Accessing-Problem
• 27.4.2006: Selbstanpassende Suchbäume
• 4.5.2006: Paging: Grundlagen, deterministische  Online-Algorithmen, kompetitive Analyse von Markierungsalgorithmen
  
• 11.5.2006: Verallgemeinerung auf verschiedene Cache-Größen des Online- und Offline-Algorithmus, der randomisierte Algorithmus RANDOM und seine Analyse
• 18.5.2006: Analyse des randomisierten Algorithmus MARK, untere Schranke für randomisierte Online-Algorithmen, Einführung in das Zugriffsgraphen-Modell
• 1.6.2006: Vergleich von LRU und FIFO im Zugriffsgraphen-Modell
• 8.6.2006: Einführung Spieltheorie
• 22.6.2006: Äquivalenzaussagen zwischen gemischten Strategien und Verhaltensstrategien
• 29.6.2006: Modellierung von Online-Problemen als Request-Answer-Games, Randomisierung des Gegners, Beziehungen zwischen verschiedenen Arten von Gegnern, Randomisierung ist gegenüber adaptive-offline-adversaries nutzlos
• 6.7.2006: Kauf- und Verkaufsprobleme: Vergleich des Suchproblems und des One-Way-Trading-Problems, Reservation-Price-Policy, EXPO
• 13.7.2006: Die sog. Threat-Based-Policy für das One-Way-Trading-Problem
  

Übungsblätter