Online-Algorithmen oder wo ist der Aufzug

Lecturers:Kókai, G.
Coverage:2 SWS
Prerequisites:

Anmeldung: per Email kokai@informatik.uni-erlangen.de

Scheinkriterien: Folgende Scheinkriterien sind zu erfüllen:

  • Ein 45 minütiger Vortrag
  • Erstellen einer Ausarbeitung (Handout) mit den wesentlichen Punkten des Vortrags (keine bloßen Folienkopien, 6-8 Seiten)
  • Anwesenheit bei den Vorträgen der anderen Teilnehmer
  • Kontaktieren des Betreuers spätestens 2 Wochen vor dem Vortragstermin, Fertigstellung der Vortragsfolien und des Handouts spätestens 4 Tage vor dem Vortrag
Dates & location:
  • single date on May 22, 2009, 09:15 - 13:15, 04.150
  • single date on June 19, 2009, 09:15 - 13:15, 04.150
Audience:PF INF-BA (2.-8. Semester)
PF INF-BA-SEM (2.-8. Semester)
WPF CE-BA-G (2.-8. Semester)
WPF CE-BA-SEM (2.-8. Semester)
WPF CE-MA (6.-10. Semester)
WPF INF-DG (6.-10. Semester)
WPF IuK-BA (2.-6. Semester)
WPF IuK-DG (2.-8. Semester)
WPF IuK-DH (6.-10. Semester)
Literature:

A. Borodin and R. El-Yaniv, Online computation and competitive analysis, Cambridge University Press, 1998.

A. Fiat and G. J. Woeginger (eds.), Online algorithms: The state of the art, Lecture Notes in Computer Science, vol. 1442, Springer, 1998.

Topics:

Wir erleben es täglich: Morgens verspätet unterwegs Bus fährt nicht püntlich und dann kommt der Aufzug im blauen Hochhaus nicht. Wer hat wohl diese Steuerung entworfen? Das muß man doch leicht mit OR lösbar! Wirklich?

Es ist weit nicht so einfach, wie man zuerst denkt, soll in diesem Seminar gezeugt werden. Wir führen anhand der Beispielen die wesentlichen Fragestellungen und Analysemethoden bei Online- und Echtzeit-Algorithmen ein.

In der klassischen kombinatorischen Optimierung wird davon ausgegangen, dass die Daten jeder Probleminstanz vollständig gegeben sind. Aufbauend auf diesem vollständigen Wissen berechnet dann ein Algorithmus eine optimale (oder approximative) Lösung. In vielen Fällen modelliert diese Offline-Optimierung jedoch das Problem nur ungenügend und in vielen Anwendungen erweist sich diese Annahme als unrealistisch. Zahlreiche Problemstellungen sind in der Praxis in natürlicher Weise online: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen. Online-Probleme treten in vielen Bereichen der Informatik auf, beispielsweise in der Ressourcenverwaltung auf Betriebssystemebene, in verteilten Systemen, in der Robotik oder im Bereich Cache-Verwaltung.

Exam/certificate

Scheinkriterien: Folgende Scheinkriterien sind zu erfüllen:
  • Ein mindestens 40, maximal 60 minütiger Vortrag
  • Erstellen einer Ausarbeitung (Handout) mit den wesentlichen Punkten des Vortrags (keine bloßen Folienkopien, 6-8 Seiten)
  • Anwesenheit bei den Vorträgen der anderen Teilnehmer
  • Kontaktieren des Betreuers spätestens 2 Wochen vor dem Vortragstermin, Fertigstellung der Vortragsfolien und des Handouts spätestens 4 Tage vor dem Vortrag
watermark seal