|
Universität Bonn
Institut für Informatik V
Prof. Dr. N. Blum
Vorlesung: Online Algorithmen
(SS 2000)
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:
- Welcher Block soll aus dem Cache entfernt werden, wenn er voll ist?
- Über welche Knoten soll der nächste Telefonanruf laufen?
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 C
Ü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
18.01.2000 - rick@informatik.uni-bonn.de
|