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. 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.
In dem Seminar sollen Online-Algorithmen für verschiedene Probleme vorgestellt
werden. Zu diesen Problemen zählen unter anderem sogenannte Scheduling-Probleme,
die eine zentrale Rolle bei der Implementierung von Betriebsystemen spielen. In
diesem Zusammenhang wird für interessierte Teilnehmer im Wintersemester
2008/2009 ein Praktikum angeboten, in dem die im Seminar vorgestellten
Online-Algorithmen für ein echtes Betriebsystem implementiert werden sollen.
Seminartermin:
jeweils Dienstags, 13-15 Uhr
Raum: N328