Modulcode:	WInf-OR
Englische Bezeichnung:	Operations Research
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (SS14)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BM-IDWM (MSc WInf) OR (MSc WInf)
Lehrsprache:	Deutsch
Voraussetzungen:

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 Algorithmen und Datenstrukturen

Prüfungsleistung:

• Entwicklung eines Algorithmus oder von theoretischen Aussagen zu vorgegebenen Optimierungsproblemen
• Ausarbeitung einer wissenschaftlichen Arbeit zu den erzielten Ergebnissen
• Präsentation der Ergebnisse im Rahmen eines Vortrages

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• K. Jansen: Effiziente Algorithmen, Skript zur Vorlesung, 2002
• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press, 2001
• Aho, Hopcroft, Ullmann: The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974
• Jansen, Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008
• Vijay V. Vazirani, Approximation Algorithms. Berlin: Springer, 2003
• Dorit H. Hochbaum, ed., Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997
• David P. Williamson und David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
• Rolf Wanka, Approximationsalgorithmen, Teubner Verlag, 2006
• Papadimitriou und Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications
• Korte und Vygen, Combinatorial Optimization: Theory and Algorithms, Springer
• Domschke und Drexl, Einführung in Operations Research, Springer
• Werners, Grundlagen des Operations Research, Springer
• Borgwaldt, Optimierung, Operations Research, Spieltheorie, Birkhäuser

Verweise:

Kommentar: