Online Problems
Über die Vorlesung
Die Vorlesung Online Problems behandelt verschiedene Aspekte von Online-Algorithmen. Bei der Online-Berechnung muss ein Computeralgorithmus entscheiden, wie er eingehende Informationen bearbeitet, ohne zukünftige Eingaben zu kennen. Die Veranstaltung bietet eine ausführliche Darstellung der Wettbewerbsanalyse, mit der solche Probleme analysiert werden können. Bei diesem Ansatz wird die Qualität eines Algorithmus relativ zur bestmöglichen Leistung eines Algorithmus gemessen, der vollständige Kenntnisse über die Zukunft besitzt. Diese Methodik zur Analyse von Online-Algorithmen ist ein Standardansatz in der Informatik geworden. Ausgehend von den grundlegenden Definitionen des Konkurrenzanalysemodells werden die wesentlichen Techniken anhand der Beispiele Listenzugriff und Paging in einem virtuellen Speichersystem dargestellt. Es wird auch erläutert, wie die Wettbewerbsanalyse mit der Spieltheorie in Zusammenhang steht.
Im Einzelnen werden folgende Themen besprochen:
- Competitive Analysis
- Randomized Algorithms
- Deterministic Algorithms
- Game-Theoretic Foundations
- Request-Answer Games
Organisatorisches
Vorlesung
Die Vorlesung findet in englischer Sprache statt.
Dozent: Prof. Dr.-Ing. Uwe Schwiegelshohn
Termin: Mittwoch, 10.15 - 12.00 Uhr, IRF 108, ab 11.10.2023
Übung
Dozent: Samin Jamalabadi
Termin: Montag, 14.15 - 15.00 Uhr, IRF 108, ab 16.10.2023
Organisatorische Hinweise
Aktuelle Informationen im Zusammenhang mit der Vorlesung, Übung und Prüfungen (Termine) werden ausschließlich über Moodle veröffentlicht. Des Weiteren dient der Moodle-Arbeitsraum mit seinen vielfältigen Kommunikationsmöglichkeiten (Chat, Mailinglisten, Forum etc.) dem kollaborativen Arbeiten im Rahmen der Vorlesung.
Interessierte Studierende melden sich bitte im LSF an. Es werden nur Teilnehmer, die sich im LSF angemeldet haben, automatisch vom LSF in den Moodle-Arbeitsraum übertragen. Für die weiteren Ankündigungen im Rahmen der Vorlesung und der Übung wird ausschließlich Moodle genutzt.
Für das Fach "Online Problems" müssen von den Studierenden folgende Prüfungsleistungen erbracht werden:
- Erfolgreiche Teilnahme an der mündlichen Prüfung
- Umfang SWS: 2 V, 1 Ü
- Credits: 5
- Veranstaltungsnummern:
- Vorlesung: 08 8008
- Übung: 08 8009
- 3. Semester im Master ET/IT und A&R
- Modul Nr. 3-35, ETIT-292
Die Vorlesung basiert größtenteils auf:
Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University PressKontakt