Universität Bonn

Institut für Informatik V

Prof. Dr. N. Blum, M. Löhnertz

Proseminar Online Algorithmen
(WS 2000/2001)

Inhalt:

Im Gegensatz zu "herkömmlichen" Algorithmen müssen sog. "Online Algorithmen" Entscheidungen treffen und Ausgaben machen, bevor die gesamte Eingabe bekannt ist. Daraus ergibt sich meist zwangsläufig eine schlechtere Qualität der Lösung. Ziel dieses Proseminars ist es, Verfahren zu diskutieren, die es erlauben, diese Veränderung zu erfassen, und Methoden zu untersuchen, die eine Begrenzung der Verschlechterung ermöglichen.

Themenübersicht:

Selbstanordnende Listen
Bin Packing
Ausweg aus einem Labyrinth
Online Scheduling
Online Algorithmen fuer Maschinelles Lernen
Kompetetive Analyse von Paging Algorithmen
Online TSP
Zielpunktsuche in unbekannter Umgebung I
Zielpunktsuche in unbekannter Umgebung II
Online Sitzplanreservierung
Das Bahncard Problem
Das Brückenproblem

Seminartermin:

jeweils Dientags, 16-18 Uhr, N102

Vortragsmodus:

Vortragsausarbeitung, Einzelvortrag

Plätze:

Literatur:

Buchkapitel und Zeitschriftenartikel

Universität Bonn / Informatik / Abteilung V

12.9.2000 - ml@informatik.uni-bonn.de