Modul
Algorithmische Methoden für schwere Optimierungsprobleme [M-INFO-101237]
Leistungspunkte
5Turnus
UnregelmäßigDauer
1 SemesterSprache
DeutschLevel
3Version
1Einrichtung
- KIT-Fakultät für Informatik
Bestandteil von
Teilleistungen
Identifier | Name | LP |
---|---|---|
T-INFO-103334 | Algorithmische Methoden für schwere Optimierungsprobleme | 5 |
Erfolgskontrolle(n)
Siehe Teilleistung.
Qualifikationsziele
Der/die Studierende
- identifiziert algorithmische Optimierungsprobleme aus unterschiedlichen Bereichen und kann diese entsprechend formal beschreiben,
- kann sich qualifiziert und in strukturierter Form zu verschiedenen Aspekten der Optimierung äußern,
- kann einfache Algorithmen exemplarisch ausführen und ihre Eigenschaften erklären,
- kennt methodische Ansätze für den Entwurf und die Beurteilung von Optimierungs-Algorithmen und weiß diese geeignet anzuwenden,
- kann die Berechnungskomplexität algorithmischer Probleme aus unterschiedlichen Bereichen herleiten und einschätzen,
- kann geeignete algorithmische Lösungstechniken erkennen und auf verwandte unbekannte Probleme anwenden.
Voraussetzungen
Siehe Teilleistung
Inhalt
Es gibt viele praktische Probleme, die nicht perfekt gelöst werden können oder bei denen es sehr lange dauern würde, eine optimale Lösung zu finden. Ein Beispiel dafür ist Bin-Packing, wo Objekte in Behältern ("bins") einzupacken sind, wobei man möglichst wenige Behälter benutzen will. 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 auch Bins abschließen und wegschicken, während vielleicht noch neue Objekte ankommen. Für verschiedene NP-schwere Problemstellungen behandelt die Vorlesung neben Approximationsalgorithmen und Online-Verfahren auch Lösungstechniken, die der menschlichen Intuition oder natürlichen Vorgängen nachempfunden sind (Heuristiken und Metaheuristiken).
Empfehlungen
Siehe Teilleistungen