Modulcode:	WInf-BProjOR
Englische Bezeichnung:	Bachelor Thesis: Operations Research
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS14/15 SS15 WS15/16)
Präsenzzeiten:	4PÜ
ECTS:	15
Workload:	210 Std. Projektarbeit, mit 60 betreuten Projektstunden; 240 Std. Berarbeitung der individuellen Aufgabe, mit ca. 100 Std. zur Erstellung der Abschlussarbeit und -präsentation
Dauer:	ein Semester
Modulkategorien:	AP (BSc WInf)
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) 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.

2) 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.

Weitere Voraussetzungen:

Vorlesung Algorithmen und Datenstrukturen

Prüfungsleistung:

Schriftliche Ausarbeitung (Bachelorarbeit) und institutsöffentlicher Vortrag

Lehr- und Lernmethoden:

Die Bachelorarbeit wird vom Betreuer vergeben und bewertet. Die Bearbeitung erfolgt als eigenständige Leistung unter Betreuung.

Verwendbarkeit:

Literatur:

Verweise:

Kommentar:

Bitte beachten Sie, dass es sich bei Bachelorarbeit und Abschlussprojekt gemäß der Prüfungsverfahrensordnung der Christian-Albrechts-Universität zu Kiel nicht um ein Modul handelt.