Ankündigung der Vorlesung

Online-Optimierung

Dr. Sven O. Krumke
Diese Vorlesung findet im SS 2000 statt. Der Eintrag im kommentierten Vorlesungsverzeichnis der TU Berlin findet sich hier.
Die Ankündigung der Vorlesung ist als Postscriptdatei [27 KByte] und als PDF-Datei [19 KByte] verfügbar.

Aktuelles

Inhalt

Wie soll man einen Aufzug steuern, wenn man keine Informationen über zukünftige Fahraufträge besitzt? Soll man eine Bahncard kaufen, wenn die nächsten Bahnreisen noch unbekannt sind? Was ist eine gute Seitenersetzungsstrategie beim Caching in virtuellen Speichersystemen?

In der klassischem kombinatorischen Optimierung geht man davon aus, da"s die Daten jeder Probleminstanz vollständig gegeben sind. In vielen Fällen modelliert diese Offline-Optimierung jedoch die Situationen aus Anwendungen nur ungenügend. Zahlreiche Problemstellungen in der Praxis sind in natürlicher Weise online: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen.

Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die kompetitive Analyse durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Mit Hilfe der kompetitiven Analyse werden in der Vorlesung Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schwächen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt.

Neben der theoretischen Seite werden wir auch die Anwendung der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchten. Bei der Steuerung automatischer Transportsysteme tritt eine Fülle von Online-Problemen auf. Hierbei werden werden die Algorithmen oftmals weitere Anforderungen gestellt. So müssen Entscheidungen unter strikten Zeitbeschränkungen gefällt werden (Echtzeit-Anforderungen).

Termine

Die Vorlesung findet Donnerstags von 10:00-12:00 Uhr im Raum MA 541 der Technischen Universität Berlin statt.

Formalitäten

Anrechenbarkeit: 2 Semesterwochenstunden
Schein: Teilnahmebescheinigungen werden vergeben

Zielgruppe und Voraussetzungen

Die Veranstaltung richtet sich an Studenten der Mathematik und Informatik im Grund- und Hauptstudium. Grundkenntnisse in der kombinatorischen Optimierung sind hilfreich, aber nicht erforderlich.
Dr. Sven Krumke
Last modified: Thu Apr 20 08:48:23 MET DST 2000