Spezialvorlesung Online-Algorithmen

Spezialvorlesung

"Online-Algorithmen"

Sommersemester 2006


Veranstalter:		Detlef Sieling
Termin:		Donnerstag, 14.15-16.00 Uhr, OH-14, R. 304
Beginn der Vorlesung:		6. April 2006
Übungen:		Dienstag, 10.15-12.00 Uhr, OH-14, R. 305 (14-tägig)

Bei den meisten der in den Vorlesungen "Datenstrukturen, Algorithmen und Programmierung" oder "Effiziente Algorithmen" behandelten Algorithmen ist beim Aufruf des Algorithmus die vollständige Eingabe bekannt. In der Realität gibt es aber auch viele Aufgabenstellungen, bei denen die Eingabe nach und nach geliefert wird und der Algorithmus jeweils sofort "Entscheidungen" treffen muss, ohne die zukünftigen Eingaben zu kennen. Dabei hängt aber die Qualität der Entscheidungen auch von zukünftig ankommenden Eingaben ab. Derartige Algorithmen bezeichnet man als Online-Algorithmen.

Ein einfaches Beispiel ist der Verkauf eines Autos. Es treffen nach und nach Kaufangebote ein und man muss bei den einzelnen Angeboten kurzfristig entscheiden, ob man das Auto zu dem gebotenen Preis verkauft oder ob man auf ein besseres Angebot hofft. Im nachhinein ist es leicht zu entscheiden, welches das beste Angebot war, d.h., für einen Offline-Algorithmus (also einen Algorithmus, der gesamte Folge von Angeboten kennt) ist dieses Problem trivial. Ein häufig gewählter Ansatz, die Qualität von Online-Algorithmen zu bewerten, besteht daher darin, die Qualität der von ihnen berechneten Lösungen mit denen eines optimalen Offline-Algorithmus zu vergleichen. Der Vergleich der Kosten eines Online-Algorithmus mit denen eines Offline-Algorithmus wird auch als konkurrierende Analyse (engl.\ competitive analysis) bezeichnet.

Neben dem genannten Beispiel von Verkaufsentscheidungen gibt es zahlreiche weitere Anwendungen für Online-Algorithmen, beispielsweise Routing-Probleme in Rechnernetzen, Lastbalancierung, dynamische Datenstrukturen für Dictionaries oder die Verwaltung von Caches. In der Vorlesung werden Online-Algorithmen für verschiedene Aufgabenstellungen vorgestellt und analysiert. Im Vergleich zum gewohnten Entwurf von Offline-Algorithmen kommen neue "Tricks" hinzu, während bei der Analyse verschiedene Techniken vorgestellt werden, die auch in anderen Bereichen der Analyse von Algorithmen nützlich sind.

Literatur zur Vorlesung

M. Westermann, B. Vöcking, Ch. Sohler (2004). Skript zur Spezialvorlesung Online-Algorithmen, erhältlich unter http://ls2-www.cs.uni-dortmund.de/~westermann/online-algorithmen.s2004.
A. Borodin, R. El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press.
N. Blum (2004). Algorithmen und Datenstrukturen (Kapitel 6). Oldenbourg.

26.1.2006 - Detlef Sieling