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 |
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:
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.
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:
Besuch der Vorlesung [Einführung in die Algorithmik, Mathematik A und B] oder äquivalente Vorlesungen.
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:
Vorlesung, gruppeninterne Vorträge, betreute Ausarbeitung einer wissenschaftlichen Arbeit
de Gruyter, Berlin, New York, 2008
Dieses Modul kann auch im Wahlpflichtbereich des Bachelorstudiengangs Informatik gehört werden.