 Programmierpraktikum Diskrete Optimierung
n.Vereinb. (Prof. Dr. Bernhard Korte, Prof. Dr. Dieter Rautenbach, Prof. Dr. Jens Vygen)
 Algorithmische Geometrie II (4V+2Ü) (A,C) [A1]
Mo 13-15, HS 1, Mi 11-13, HS C (Prof. Dr. Rolf Klein)
Übungen: Mi 15-17, SR N1001, (ev. auch Mi 08-10) (Prof. Dr. Rolf Klein, Annette Ebbers-Baumann, Andrea Eubeler)
|
Vorlesung (Hauptstudium)
Online Algorithmen I
Prof. Dr. Rolf Klein
In vielen Bereichen der Informatik, aber auch des täglichen Lebens, ist es notwendig, Entscheidungen unter Unsicherheit zu treffen. Beispiele finden sich beim Paging und Scheduling eines Betriebssystems ebenso wie bei der Navigation eines Roboters in unbekannter Umgebung oder der Beantwortung der Frage, ob man im Urlaub die Ski kaufen oder mieten sollte. In allen Fällen fehlt die Information über die Zukunft bzw. die Kenntnis der näheren Umstände, die eine optimale Lösung ermöglichen würde. Bei der Entwicklung guter Online-Strategien bemüht man sich, dem Optimum zumindest bis auf einen konstanten Faktor nahezukommen.
| Zeit, Ort | Di 13-15, HS D |
| Semesterwochenstunden | 2V + 1Ü |
| Übungen | Do 13:30, SR N327 (14-tägig) (Prof. Dr. Rolf Klein, Ansgar Grüne) |
| Voraussetzungen | Die Vorlesung wendet sich an Studierende im Hauptstudium; sie setzt aber nur Kenntnisse von Informatik III und IV voraus. | | Nachfolgeveranstaltungen | Voraussichtlich wird im Wintersemester 2005/2006 die Vorlesung "Online-Algorihtmen II" angeboten. |
| Bereich (alte DPO) | A |
| Bereich (neue DPO) | A1 |
| Prüfungsmöglichkeiten | alte DPO: A, C; Prüfungen beliebig nach Vereinbarung; in Kombination mit anderen Vorlesungen dieser Bereiche (z.B. Online Algorithmen II, Algorithmische Geometrie, Bewegungsplanung, ...) über insgesamt 8 SWS
neue DPO: A1, 4 LP |
| Literatur | - A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998
- A. Fiat, G. J. Wöginger, Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998 |
| Informationen im WWW | http://web.informatik.uni-bonn.de/I/Lehre/Vorlesungen/Online05/ |
|
Übersicht: alle Semester