Online-Algorithmen

Termine

Art Wann Wo Beginn Dozent
V4 Montag 14:15 - 15:45
Dienstag 14:15 - 15:45
AVZ III / HS 1
AVZ III / HS 1
18. April 2017 Prof. Dr. N. Blum
Ü2 Donnerstag 14:00 - 15:30 AVZ III / A6a 4. Mai 2017 Schmitz

Die Übung am Donnerstag, den 25.05.2017 wird aufgrund des Feiertags auf den 24.05.2017, von 10:15 bis 11:45 in Raum II.57 im LBH verlegt.

Die Übung am Donnerstag, von 10:15 bis 11:45 wird wegen einer zu geringen Teilnehmerzahl vorerst ausgesetzt. Sollte wieder Bedarf an diesem Termin bestehen, schicken Sie bitte spätestens einen Tag vor der Übung eine E-Mail an Adrian Schmitz.

Inhalt

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.

Vorlesungsnotizen

Übungsblätter


Page Tools