Modulcode:	MS0202
Englische Bezeichnung:	Efficient Algorithms / Operations Research
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS07/08 WS09/10 WS11/12 SS14 SS15 SS16 SS17 SS18 WS19/20 WS20/21 WS21/22 SS23 SS25)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Übung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) IG (TA) (MSc Inf (2-Fach)) OR (MSc WInf) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS

Kurzfassung:

Jenseits der grundsätzlichen Lösbarkeit von Problemen eröffnet sich ein neues Problemfeld: Es ist interessant, ein Optimierungsproblem möglichst schnell und gut lösen zu können. Effiziente Algorithmen sind solche Algorithmen, deren Laufzeit durch ein Polynom in der Problemgröße beschränkt ist. Besonders für Optimierungsprobleme aus der Praxis sind solche Algorithmen von großer Bedeutung, um relevante Lösungen in angemessener Zeit zu finden. Die Vorlesung lässt sich in folgende Hauptbereiche zusammenfassen:

1. Einfache Komplexitätstheorie,
2. algorithmische Lösungsverfahren,
3. Anwendungen wie Maschinenbelegung (Scheduling), Transport- und Packungsprobleme, Tourenplanung, ...

Lernziele:

Die Studierenden erlernen Komplexitätsmaße für Algorithmen und grundlegende Designprinzipien für den Entwurf effizienter, exakter und approximativer Algorithmen und betrachten diese anhand klassischer angewandter Optimierungsprobleme. Nach Abschluss des Moduls sind die Studierenden in der Lage, effiziente Algorithmen für Optimierungsprobleme aus der Praxis zu analysieren, zu entwerfen und auch experimentell zu bewerten.

Lehrinhalte:

Angesichts praktischer Anwendungen stellt sich ein Problem, das über die grundsätzliche Lösbarkeit (Entscheidbarkeit) hinausgeht: Selbstverständlich ist es interessant, ein gegebenes Problem nicht nur überhaupt, sondern auch mit möglichst geringem Ressourcenbedarf lösen zu können. Effiziente Algorithmen sind solche Algorithmen, deren Laufzeit durch ein Polynom in der Problemgröße beschränkt ist. Konkret behandelte Themen:

• Zeitkomplexität von Algorithmen.
• Grundlegende algorithmische Methoden: Divide-and-conquer, dynamische Programmierung, Greedy-Algorithmen, approximative Algorithmen.
• Grundlegende Algorithmen für Bin Packing und 2D-Packungsprobleme.
• Approximationsschemata für das Rucksackproblem und Verallgemeinerungen.
• Asymptotische Approximationsschemata für Bin Packing.
• Approximative Algorithmen für Schedulingprobleme auf identischen und nicht-identischen Maschinen.
• Approximative Algorithmen für Scheduling mit parallelen Jobs.
• Approximative Algorithmen für 2D-Packungsprobleme.
• Approximative Algorithmen für das Problem des Handlungsreisenden (Traveling Salesman Problem, TSP) und Varianten.
• Approximative Algorithmen für Tourenplanung.
• Untere Schranken zur Laufzeit von exakten und approximativen Algorithmen.

Weitere Voraussetzungen:

Besuch der Vorlesung [Einführung in die Algorithmik, Mathematik A und B] oder äquivalente Vorlesungen.

Prüfungsleistung:

Die Note für das Modul ergibt sich vollständig über das Forschungsprojekt und dem zugehörigen Vortrag sowie der zugehörigen Ausarbeitung. Eine Voraussetzung für das Bestehen ist weiter, dass mindestens 40% der Punkte in den Hausaufgaben erreicht werden.

Als Prüfungsleistung werden den Studierenden individuelle Forschungsaufgaben gestellt, welche die Studierenden bearbeiten müssen. Die Bewertung der Forschungsaufgabe ergibt sich aus 2 Teilen:

• Schriftliche Ausarbeitung (ca 8-15 Seiten) eines Forschungsergebnisses, z.B. Verbesserung eines Algorithmus bezüglich Laufzeit oder Approximationsgüte. Statt eines Forschungsergebnisses kann auch eine neue algorithmische Idee implementiert werden und eine Ausarbeitung dazu erstellt werden.
• Vortrag über Forschungsergebnis (bzw Vortrag über neue algorithmische Idee und Implementierung), Dauer ca. 30 min

Lehr- und Lernmethoden:

Vorlesung, gruppeninterne Vorträge, betreute Ausarbeitung einer wissenschaftlichen Arbeit

Verwendbarkeit:

Literatur:

• K. Jansen: Effiziente Algorithmen, Skript zur Vorlesung, 2002
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3ed., MIT Press, 2001
• A.V. Aho, J.E. Hopcroft, J.D. Ullmann: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974
• K. Jansen, M. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit,

de Gruyter, Berlin, New York, 2008

• V.V. Vazirani: Approximation Algorithms, Springer, Berlin, 2003, ISBN: 3-540-65367-8
• D.H. Hochbaum, ed.: Approximation Algorithms for NP-Hard problems, PWS Publishing, 1997, ISBN: 0-534-94968-1
• D.P. Williamson und D.B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, Cambridge, 2011, ISBN: 978-0-521-19527-0
• R. Wanka: Approximationsalgorithmen: Eine Einführung, Teubner, Wiesbaden, 2006
• C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, Englewood Cliffs, NJ, 1982
• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms, 2nd ed., Springer, Berlin, 2002, ISBN: 978-3-662-21711-5
• W. Domschke, A. Drexl. R. Klein, A. Scholl: Einführung in Operations Research, 9. Aufl., Springer, Berlin, 2015, ISBN: 978-3-662-48215-5
• B. Werners: Grundlagen des Operations Research, 3. Aufl., Springer, Berlin, 2006, ISBN: 978-3-642-4010113

Verweise:

Kommentar:

Dieses Modul kann auch im Wahlpflichtbereich des Bachelorstudiengangs Informatik gehört werden.