Online Algorithmen
Dozent:innen: Dr. rer. nat. Frank FischerKurzname: 08.079.23401
Kurs-Nr.: 08.079.23401
Kurstyp: Vorlesung/Übung
Voraussetzungen / Organisatorisches
DSeAEmpfohlene Literatur
Borodin, Allan: Online computation and competitive analysis, Cambridge Univ. Press, 1998Krumke, Rambau: Online Optimierung, Konrad-Zuse-Institut Berlin, 2000
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.
Termine
| Datum (Wochentag) | Zeit | Ort |
|---|---|---|
| 24.10.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 31.10.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 07.11.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 14.11.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 21.11.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 28.11.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 05.12.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 12.12.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 19.12.2023 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 09.01.2024 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 16.01.2024 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 23.01.2024 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 30.01.2024 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |
| 06.02.2024 (Dienstag) | 12:15 - 13:45 | 05 136 2413 - Neubau Physik/Mathematik |