Modulcode:	Inf-AP-EffAlg
Englische Bezeichnung:	Final Project - Efficient Algorithms
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS12/13 SS13 WS13/14 SS14 WS14/15 SS15 WS15/16)
Präsenzzeiten:	6Ü
ECTS:	15
Workload:	450 Std.
Dauer:	ein Semester
Modulkategorien:	AP (BSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

In diesem Projektmodul werden entweder approximative Algorithmen zur Lösung klassischer Optimierungsprobleme der Informatik oder praktische Problemstellungen (z. B. Sportligaoptimierung oder Transportoptimierung) behandelt. Hauptaugenmerk liegt hierbei einerseits auf den Designtechniken, andererseits auf Fragen der Effizienz bei der Implementierung.

Lernziele:

Die Studenten erlernen, Algorithmen hinsichtlich Laufzeit und Güte zu analysieren, die verwendeten Verfahrensweisen zu erkennen, zu verbessern und auf andere Problemstellungen zu übertragen.

Lehrinhalte:

Optimierungsprobleme sind ein spannendes Thema. Einerseits treten sie in sehr vielen Bereichen des täglichen Lebens auf, wie in der Wirtschaft, andererseits spielen sie in der theoretischen Informatik eine große Rolle. Viele Optimierungsprobleme sind NP-vollständig: Man weiß bis heute nicht, ob man effizient (d.h. schnell) eine optimale Lösung finden kann. Deswegen betrachtet man Approximationsalgorithmen, die effizient eine angenäherte Lösung mit garantierter Genauigkeit finden können.

Dieses Bachelor-Abschlussprojekt bietet Themen aus Theorie und Praxis an:

1) Theoretische Fragestellungen: Entwicklung von approximativen und Online-Algorithmen sowie untere Schranken zur Laufzeit von Algorithmen; u.z. zu folgenden Optimierungsproblemen: 2D und 3D Packungen, Bin Packing, Scheduling von Jobs auf identischen oder heterogenen Maschinen, Knapsack Probleme, Lineare Optimierung sowie Ganzzahlige Optimierung. Mögliche Themen mit direktem Bezug zu unseren Forschungsprojekten.

2) Praktische Fragestellungen: Fluglinienplanung (Fleet Assignment), Touren- und Routenplanung, Robuste Algorithmen zur Bahnoptimierung, Sportliga-Optimierung, Stundenplan-Optimierung, Zeichnen von Graphen. Mögliche Themen teilweise in Kooperation mit Firmen.

Weitere Voraussetzungen:

Das Projektmodul richtet sich an Bachelorstudenten der Informatik im 5. und 6. Semester. Voraussetzungen für die Teilnahme sind

• Interesse an Optimierungsproblemen
• Besuch der Vorlesung Algorithmen und Datenstrukturen

Prüfungsleistung:

Schriftliche Ausarbeitung (Bachelorarbeit) und institutsöffentlicher Vortrag

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Verweise:

Kommentar: