Vorlesung: Online Algorithmen
(SS 2002)

Beschreibung:

In Online-Berechnungen muss ein Algorithmus beim Eintreffen von Anforderungen Entscheidungen treffen, ohne Kenntnis über zukünftige Entwicklungen zu haben. Dies ist eine in der Praxis häufig anzutreffende Situation. Man denke nur an Fragen wie: Einmal getroffene Entscheidungen können sich später als suboptimal herausstellen, da sich die Zukunft anders entwickelt hat als angenommen. Die Qualität eines Online-Algorithms wird häufig durch Vergleich mit dem Resultat bestimmt, das ein Algorithmus erreichen würde, der alle Anforderungen von vorneherein kennt. Die Vorlesung wird anhand zahlreicher typischer Probleme grundlegende Techniken dieses Teilgebiets der Algorithmik behandeln.

Termin:

Di, 8-10 und Do, 8-10, HS 1

Übungen:

2st n. Vereinbarung

Literatur:

A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998
Universität Bonn / Informatik / Abteilung V
14.01.2002 - ml@informatik.uni-bonn.de