Lehrende/r: Dr. rer. nat. Frank Fischer
Veranstaltungsart: Vorlesung/Übung
Anzeige im Stundenplan: 08.079.23401
Semesterwochenstunden: 4
Credits: 6,0
Unterrichtssprache: Deutsch
Min. | Max. Teilnehmerzahl: - | -
Voraussetzungen / Organisatorisches: DSeA
Inhalt: Klassische Algorithmen gehen davon aus, dass die gesamte Information, d.h. die Probleminstanz, von Beginn an bekannt ist. Beispiele hierfür sind etwa das TSP, Kürzeste-Wege-Probleme oder Sortieren. Im Gegensatz dazu geht man bei Online-Algorithmen davon aus, dass die Information erst nach-und-nach bekannt wird, während der Algorithmus bereits läuft. Insbesondere muss der Algorithmus dabei bereits Entscheidungen treffen, während nur ein Teil der Information bereits bekannt ist. Ein Beispiel hierfür aus dem Alltag sind Lieferdienste: Kundenaufträge müssen bearbeitet werden, während ständig neue Bestellungen eintreffen. In der Informatik ist das Paging-Problem bekannt: während ein Programm läuft muss das Betriebssystem entscheiden, welche Speicherseiten aus dem Hauptspeicher entfernt werden ohne zu wissen, welche dieser Seiten zukünftig erneut benötigt werden. In dieser Vorlesung beschäftigen wir uns mit Online-Algorithmen und deren Analyse. Insbesondere lernen wir dabei spezielle Analyse-Techniken wie die kompetitive Analyse kennen.
Empfohlene Literatur: Borodin, Allan: Online computation and competitive analysis, Cambridge Univ. Press, 1998 Krumke, Rambau: Online Optimierung, Konrad-Zuse-Institut Berlin, 2000
