Die Vorlesung findet in englischer Sprache statt.
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.
Die Vorlesung Online Problems behandelt verschiedene Aspekte von Online-Algorithmen. Bei der Online-Berechnung muss ein Computeralgorithmus entscheiden, wie er auf eingehende Informationen einwirkt, ohne dass er zukünftige Eingaben kennt. Wie sollte es den nächsten Telefonanruf leiten? Wo im Speicher sollte es eine gerade-geschlossene Aufzeichnung speichern? Die Veranstaltung bietet eine ausführliche Darstellung der Wettbewerbsanalyse, in dem solche Probleme analysiert und gelöst werden können. In diesem Rahmen 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-Entscheidungen ist zu einem Standardansatz in der Informatik geworden. Ausgehend von den grundlegenden Definitionen des Konkurrenzanalysemodells werden die wesentlichen Techniken anhand verschiedener Beispiele vorgestellt, von denen einige zu den zentralen Problemen des Bereichs zählen, wie z. B. Listenzugriff, Paging in einem virtuellen Speichersystem, Routing in einem Kommunikationsnetzwerk, metrische Task-Systeme, k-Server-Systeme, Lastverteilung, Suche und Portfolio-Auswahl. Es wird auch erläutert, wie sich die Wettbewerbsanalyse auf klassischere Themen wie Spieltheorie und Entscheidungstheorie bezieht.
Im Einzelnen werden folgende Themen besprochen:
Competitive Analysis
Randomized Algorithms
Deterministic Algorithms
Game-Theoretic Foundations
Request-Answer Games
Dozent | Ort | Zeit | Beginn |
---|---|---|---|
Prof. Dr.-Ing. Uwe Schwiegelshohn | IRF 108 | Mittwoch, 10.15 - 12.00 Uhr | 13.10.2021 |
In der ersten Übungsstunde am11.10.21 findet die erste Vorlesung statt. Danach sind montags Übungen.
Dozent | Ort | Zeit | Beginn |
---|---|---|---|
Samin Jamalabadi | IRF 108 | Montag, 14.15 - 15.00 Uhr | 18.10.2021 |
Für das Fach "Online Problems" müssen von den Studierenden folgende Prüfungsleistungen erbracht werden:
Die Vorlesung basiert größtenteils auf:
Prof. Dr.-Ing. Uwe Schwiegelshohn
Tel.: 0231 755-2634
E-Mail senden
Umfang SWS: 2 V, 1 Ü
Vorlesung: 08 8008
Übungen: 08 8009
Credits: 5
3. Semester im Master ET/IT und A&R
Modul Nr. 3-35, ETIT-292