Im allgemeinen wird bei der algorithmischen Behandlung von Problemen davon ausgegangen, daß die gesamte Eingabe a priori vorliegt. Bei vielen praktischen Problemen ist jedoch ein Algorithmus erforderlich, der, ohne verläßliche Informationen über die zukünftige Eingabe zu haben, Entscheidungen auf der Basis der bisherigen Informationen trifft. Diese Algorithmen werden Online-Algorithmen genannt. Die Qualität der Lösung eines Online-Algorithmus' wird durch den Vergleich zu der des besten Offline-Algorithmus' für alle möglichen Eingaben bestimmt ( competitive analysis).
In diesem Seminar werden Online-Algorithmen zu den folgenden Themen behandelt:
| | Paging |
| | Graph Colouring |
| | Bin Packing |
| | Matching |
| | Scheduling |
| | Shortest Path |
| | Computational Geometry |
| | Currency trading |
| Zeit und Raum | Genauer Termin nach Absprache mit den Teilnehmern. |
| Beginn Mitte November 1996 | |
| Vorbesprechung | Freitag, 18.10.1996, 11 Uhr s.t. |
| Seminarraum A121 | |
| Anmeldungen vorab per email jens@uran.informatik.uni-bonn.de möglich | |
| Zuordnung | Bereich B/C |
| Modus | Einzelvorträge, schriftliche Ausarbeitung in Latex |
| bei einigen Vorträgen Implementierung des Algorithmus' | |
| Voraussetzungen | Vordiplom, Kenntnisse in algorithmischer Graphentheorie |
| und / oder kombinatorischer Optimierung | |
| Anzahl der Plätze | 8 |
| Literatur | Basisliteratur |
| Eine allgemeine Literaturübersicht ist als .ps-file (34 KB) oder | |
| als .bib-file (compressed 32KB) verfügbar. |