Algorithmische Methoden für schwere Optimierungsprobleme
Modulnummer: W09-02
Englischer Titel: Algorithmic Methods for hard Optimization Problems
Leistungspunkte: 9
Lehrperson: Meyerhenke
Empfohlene Vorkenntnisse
Kenntnisse in Algorithmen und Datenstrukturen
Zwingende Voraussetzungen
Keine
Inhalt
Es gibt viele praktische Probleme, bei denen es extrem lange dauern würde, eine optimale
Lösung zu finden. Ein Beispiel dafür ist Bin-Packing, wo Objekte in Behälter (bins)
einzupacken sind, wobei man möglichst wenige Behälter benutzen will. (Die Fragestellung
ergibt sich bei einem großen Online-Versender tausendfach am Tag.) Manchmal gibt es auch
Probleme, bei denen man Entscheidungen treffen muss, ohne vollständige Kenntnis über die
Zukunft oder die Gegenwart zu haben (Online-Probleme). Man möchte etwa beim Bin-Packing
irgendwann Bins abschließen und wegschicken, während noch neue Objekte ankommen.
Ziel der Veranstaltung ist es, dass die Teilnehmer zunächst die Komplexität von
algorithmischen Problemen erkennen und nachweisen können. Darauf aufbauend, sollen sie
mögliche Lösungsansätze erkennen und anwenden sowie implementieren und hinsichtlich ihrer
Qualität, Anwendbarkeit und Laufzeit bewerten können.
Die besprochenen Optimierungsprobleme werden grundsätzlich praktisch motiviert. In den
Übungen erhalten Sie die Gelegenheit, die gelernten Methoden selbst umzusetzen. Die
wesentlichen übergeordneten Lösungsmethoden, die vorgestellt werden, sind:
- Heuristiken
- Metaheuristiken
- Approximationsalgorithmen
- Online-Algorithmen
Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung
- keine
Lehrveranstaltungen
Vorlesung: 4 SWS
Übung: 2 SWS
Forschungsorientiert
nein
Angeboten für Studiengänge
Monobachelor: ja
Kombinationsbachelor: ja
Infomit: ja
Angeboten im
Wintersemester: nein
Sommersemester: nein
Turnus
Alle zwei Jahre