Modulcode:	Inf-AE
Englische Bezeichnung:	Algorithm Engineering
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	jedes Jahr im SS (SS15 SS16 SS17)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) WIAlg (BSc Inf) WI (MSc WInf (15)) BSc Math (Export) WI (MEd Inf) WPI (MEd Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-Math-A Inf-Math-B Inf-Math-C

Kurzfassung:

Algorithm Engineering (AE) ist das moderne Konzept des Design von Algorithmen: durch eine methodische Wechselwirkung von Theorie und Implementierung wird ein Designkreislauf angetrieben, mit dem Ziel, die theoretisch-beweisbare als auch die praktische Reichweite von Algorithmen signifikant zu erweitern. Die experimentelle Evaluation von Algorithmen nimmt dabei eine Schlüsselrolle ein. Durch diese sollen algorithmische Innovationen erreicht, falsifizierbare Hypothesen zur Performance aufgestellt, experimentell fundiert und wenn möglich bewiesen werden.

Der Beweis der Hypothesen ist als Idealfall zu betrachten, aber anzustreben. In der Regel liegt schon ein Erfolg vor, wenn ein Algorithmus durch Modifikationen oder durch eine Erweiterung um eine neue Prozedur verbessert werden kann und diese Verbesserung experimentell nachgewiesen und quantifiziert wird, z.B. durch Profiling, Benchmarking und statistische Methoden, entsprechend den wissenschaftlichen Standards des Gebietes.

In der Vorlesung wird das AE auf diskrete Optimierungs- und Graphenprobleme angewandt und exemplarisch erlernt.

Lernziele:

Durch dieses Modul erlernen die Studierende die AE-Methodik: Algorithmen werden auf der Grundlage der theoretischen Vorarbeiten, die in der Vorlesung vermittelt werden, effizient in C++ implementiert, getestet und die Testergebnisse sinnvoll interpretiert. Die Ergebnisse sollen in die Verbesserung der betrachteten Algorithmen einfließen. Sie sollen lernen, wie durch Experimente eine wissenschaftliche Fundierung der Performance von Algorithmen gegeben werden kann, die gegenüber verschiedenen Instanzklassen robust ist.

An einem Beispiel soll auch der komplette Designkreislauf des AE durchlaufen werden: Für ein Covering- oder Packingproblem ist die Laufzeit und Approximationsgüte des LP-basierten randomized rounding bekannt. Dieser Algorithmus soll implementiert werden, dann um eine Greedy-Nachoptimierung erweitert, die Performance des hybriden Verfahrens durch die AE-Methodik experimentell fundiert, eine Hypothese aufgestellt und schließlich als Höhepunkt bewiesen werden.

Die Erreichung der Lernziele befähigt die Studierenden zur Lösung komplexer algorithmischer Probleme in der Forschung und in der Berufspraxis mit den state-of-the-art Methoden. Das kritische Herangehen an die Beurteilung der Performance von Algorithmen wird gezielt geschult.

Die Studierenden werden ferner befähigt, in weitergehenden Vorlesungen oder in BSc/MSc-Arbeiten u.a. in den Gebieten Effiziente Algorithmen, Kombinatorische Optimierung, Operations Research, Data Mining, numerische Algorithmen und Graphenlayout/-Visualisierung das AE-Konzept anzuwenden.

Lehrinhalte:

Kurze Einführung in C++, Konzept des AE, Datenstrukturen für Graphen, einfache statistische Methoden zur Auswertung von Experimenten, Generieren von Testinstanzen und Vergleich von Algorithmen am Beispiel des Problems "Minimum Spanning Tree" (Kruskal, Prim). (3 Wochen)

AE für das bipartite Matching. Dieses Problem ist in der Literatur sehr ausführlich behandelt und eignet sich hervorragend für eine einführende Veranstaltung. Als Motivation eignet sich u.a. String-Matching und/oder eine medizinische Anwendung. (2 Wochen)

Streaming-Algorithmen und externe Speicher, am Beispiel von Matching und einem NP-schweren Problem, z.B. längstem Pfad. Hier wird auch die Big-Data-Problematik adressiert und das de Novo Genome Assembly als Motivation vorgestellt. (3 Wochen)

Lineare Programmierung und Anwendungen. (2 Wochen)

Randomisierte, hybride Algorithmen, u.a. randomized rounding für ganzzahlige Packing- und/oder Covering-Probleme. (2 Wochen)

Weitere Voraussetzungen:

(Mathematik A-C) oder (Lineare Algebra I, II und Analysis I, II)

Ferner Programmierkenntnisse in C oder C++.

Prüfungsleistung:

Klausur

Lehr- und Lernmethoden:

Der Stoff wird in der Vorlesung mit Tafelanschrieb und Beamerpräsentation vermittelt.

Wöchentlich gibt es Übungsaufgaben mit einer Mischung aus Theorie und Implementierung/Experimenten. Dabei sollen die vorgestellten Auswertungsmethoden (Tabellen, Plots, statistische Auswertung) zum Einsatz kommen und die kritische Beurteilung in Form einer wissenschaftichen Diskussion der Ergebnisse geschult werden.

Verwendbarkeit:

An dieses Modul kann sich eine Bachelorabschlussarbeit anschließen, nach vorliegen individueller Voraussetzungen z.B. weitere Informatik- oder Mathematik-Vorlesungen. Hierfür ist ein persönliches Gespräch erforderlich.

Literatur:

• M. Müller-Hannemann, S. Schirra. "Algorithm Engineering -- Bridging the Gap between Algorithm Theory and Practice". LNCS 5971. 2010.
• K. Mehlhorn, P. Sanders. "Data Structures and Algorithms: The Basic Toolbox". 2008. Webseite.
• R.E. Tarjan. "Data Structures and Network Algorithms". SIAM. 1983.
• L. Kliemann, P. Sanders (Ed.). "Algorithm Engineering". Abschlussband zum gleichnamigen DFG Schwerpunktprogramm 1307. Erscheint voraussichtlich 2015.

Verweise:

Kommentar: