- Semester: WS 2016/17
- Zielgruppe: Bachelor, 3. Jahr
- Leitung: Prof. Dr. Henning Meyerhenke
- Zeit: Dienstags 11:30-13:00 Uhr und donnerstags 14:00-15:30 Uhr, jeweils Raum 236, Geb. 50.34
- SWS: 2+1
- LVNr: 2400013
- Hinweis: Die Veranstaltung ist mit 2+1 SWS angesetzt, findet aber mit 4 Wochenstunden statt, da einige Termine im Semester aufgrund von Terminkonflikten ausfallen werden. Diese werden rechtzeitig angekündigt.
Aktuelles
- 15.3.: Skript Version 0.4 online.
- 31.1.: Die Projektpräsentationen finden erst am 9.2. statt. Die Prüfungsvorbereitung ist für den 21.2. um 11 Uhr im SR 301 vorgesehen.
- 11.1.: Prüfungstermine sind online.
- 7.12.: Foliensätze 10 und 11 aktualisiert.
- 22.11.: Heute keine Veranstaltung!
- 10.11.: Heute wird NetworKit eingeführt. Jedes Projektteam hat idealerweise ein Notebook dabei, auf dem NetworKit bereits installiert ist!
- Bitte registrieren Sie sich für die Mailingliste vorlesung-amfso!
Kontext
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ä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 auch Bins abschließen und wegschicken, während vielleicht noch neue Objekte ankommen.
Softwareentwickler mit Expertise in Optimierungstechniken sind in der Wirtschaft (und in der Wissenschaft) sehr gefragt.
Veranstaltungsziele
Ziel der Veranstaltung ist es, dass die Teilnehmenden 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.
Inhalte
Da in der Praxis viele schwierige Optimierungsprobleme auftreten, werden alle besprochenen klassischen Optimierungsprobleme 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
Literatur
- E. Talbi: Metaheuristics. From Design to Implementation. John Wiley & Sons, 2009.
- S. Luke: Essentials of Metaheuristics. Lulu, 2009.
- J. Hromkovic: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd edition. Springer-Verlag, 2003.
- R. Wanka: Approximationsalgorithmen. Eine Einführung. Teubner, 2006.
- T. Gonzalez (ed.): Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall, 2007.
- B. Korte, J. Vygen: Kombinatorische Optimierung. Theorie und Algorithmen. 2. Auflage. Springer-Verlag, 2012.
Ablauf und zugehörige Materialien
Skript
Das Skript dient zur Zeit lediglich der Ergänzung und deckt bei weitem nicht die ganze Vorlesung ab. Es enthät aber vielfach konkrete Literaturverweise. Beachten Sie, dass das Skript momentan noch sehr unvollständig ist, wir aber an Erweiterungen und Verbesserungen arbeiten.
Aktuelle Version: 0.4 (15.3.17)
Übungszettel
Es werden in den Übungen überwiegend Präsenzaufgaben besprochen.
Veranstaltungstermine
In der folgenden Tabelle werden die Inhalte der Termine angekündigt sowie nach der Veranstaltung die zugehörigen Materialien verlinkt. Beachten Sie bitte, dass der Ablaufplan vorläufig ist und sich noch ändern kann. Mehr Termine folgen.
| KW | Di (11:30-13:00) | Do (14:00-15:30) | 42 | V: Einführung und Bin-Packing | V: Bin-Packing |
|---|---|---|
| 43 | Ü (R. Glantz) | V: TSP: Christofides, Nichtapproximierbarkeit |
| 44 | --- (Feiertag) | Ü: Harmonic, Christofides; V: TSP: (Meta)Heuristiken |
| 45 | V: TSP mit LK, SA | V: Online-TSP (H. M.), Ü: NetworKit-Tutorial (E. Bergamini) |
| 46 | V: Rest Online-TSP, Einführung (Max-)SAT | Ü: PAH, V: RR-Max-SAT |
| 47 | --- | V/Ü: Max-SAT, Tabusuche, ILS (R. Glantz) |
| 48 | V: Rest ILS, Clusteranalyse von Graphen | Ü: Modularität, V: Lokale Heuristiken |
| 49 | V/Ü: VNS, Approximation mit Flüssen | V/Ü: GPP, KL/FM (R. Glantz) |
| 50 | V/Ü: Multilevel, ACO | --- |
| 51 | V/Ü: Einbettung von Graphen | --- |
| 2 | Übung zur Wdh. | V/Ü: Einbettung von Graphen (R. Glantz) |
| 3 | V: Evolutionäre Algorithmen (R. Glantz) | --- |
| 4 | --- | --- |
| 5 | --- | --- |
| 6 | --- | Projektpräsentationen |