Intelligente Algorithmen

Mit einem großen Abschlusskolloquium am KIT ging am 17. September 2014 das DFG-Schwerpunktprogramm 1307 Algorithm Engineering zu Ende.

Effiziente Algorithmen und Datenstrukturen sind eine Grundvoraussetzung für anspruchsvolle Computeranwendungen und deshalb in etlichen Bereichen entscheidend für die Umsetzung technologischer Möglichkeiten des täglichen Lebens.
Algorithmen werden für einfache und abstrakte Problem- und Maschinenmodelle entworfen, um beweisbare und zeitlose Leistungsgarantien für beliebige, auch noch unbekannte, Eingaben zu erzielen. Auswahl und Implementation eines Algorithmus ist Teil der Anwendungsentwicklung. Die Theorie entwickelt zwar immer ausgeklügeltere Algorithmen, diese sind jedoch häufig nicht implementierbar oder sie verhalten sich schlechter als im Modell vorhergesagt. Im Gegensatz dazu entwickelt sich Hardware durch Parallelismus, Pipelining, Speicherhierarchien immer weiter weg von einfachen Maschinenmodellen; die realen Anwendungen werden immer komplexer.
Bei wachsenden Anforderungen an innovative Algorithmen ergeben sich daraus immer größere Lücken zwischen Theorie und Praxis. Algorithm Engineering als Methodik vereint theoretische und experimentelle Ansätze und erlaubt eine enge Kopplung an Anwendungen und realistischen Maschinenmodellen. Kern ist ein Kreislauf aus Entwurf, Analyse, Implementierung und experimenteller Bewertung von Algorithmen.

2007 startete das Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, das sich zum Ziel setzte, zu einem nachhaltigen Innovationsschub durch die Anwendung verschiedener Algorithmen beizutragen. Die Wissenschaftler der beteiligten Institutionen wollten Algorithm Engineering großflächiger etablieren, es weiterentwickeln und zur Vernetzung der Wissenschaftler untereinander beitragen.^*
Am Schwerpunktprogramm beteiligt waren 25 Universitäten aus Deutschland und der Schweiz mit insgesamt 33 Einzelprojekten, die sich mit verschiedenen Anwendungsbereichen des Algorithm Engineering befassten. Koordiniert wurde das über sechs Jahre laufende Programm von Leibniz-Preisträger Prof. Peter Sanders vom Institut für Theoretische Informatik am KIT.

Zum Abschluss trafen sich die Beteiligten des Schwerpunktprogramms am 17. September 2014 zu einem Kolloquium in Karlsruhe, bei dem verschiedene Referenten einen Einblick darüber gaben, was gutes Algorithm Engineering bedeutet. Neben internen Referenten des SPPs waren auch externe Redner wie Renato Werneck von Microsoft Research, Lars Arge der Madalgo Aarhus Universität und Paolo Ferragina von der Universität Pisa eingeladen, ihre Algorithmen-Forschung zu präsentieren. „Die Abschlussveranstaltung hat noch einmal bestätigt, dass die Forschung in den letzten Jahren zu Algorithm Engineering in einigen Bereichen bereits erfolgreich dazu beigetragen hat, die Kluft zwischen Theorie und Praxis zu überbrücken,“ zieht Prof. Peter Sanders Bilanz. „Die rasanten Fortschritte, die durch neue Algorithmen für die Routenplanung oder die Suche in Texten erzielt wurden, sind Paradebeispiele für das Algorithm Engineering,“ so der KIT-Wissenschaftler weiter, „allerdings stellt die Weiterentwicklung der Hardware oder die zunehmende Verfügbarkeit riesiger Datensätze die Wissenschaft vor neue Herausforderungen“.

Koordinator Peter Sanders eröffnet das Abschlusskolloquim (li) Algorithm Engineering-Experten unter sich (re) (Bilder: KIT)

Begleitend fand im Anschluss an das Abschlusskolloquium eine zweitägige Summer School für Master-Studierende und Doktoranden statt. Führende Wissenschaftler auf dem Gebiet des Algorithm Engineering machten die Teilnehmer durch Vorträge und praktische Übungen mit der Thematik vertraut. Die Dozenten vermittelten ihr Wissen in allen Bestandteilen des Algorithm Engineering-Kreislaufs bezogen auf Gebiete wie Routenplanung, Datenkompression, Netzwerkanalyse oder Lineare Optimierung. Prof. Dorothea Wagner und Juniorprof. Henning Meyerhenke, die zum Thema Netzwerkanalyse referierten, zeigten sich begeistert: „Es war sehr inspirierend, sich hier bei der Summer School mit den jungen engagierten Teilnehmern aus aller Welt über Algorithm Engineering auszutauschen.“ Und sie ergänzen: “Auch in der Lehre an Universitäten sollte Algorithm Engineering in der Ausbildung von Informatikern einen festen Platz haben“.

Neben Beteiligten des Schwerpunktprogramms wie Prof. Dorothea Wagner vom KIT kamen beim Abschlussevent wie bei der Summer School auch externe Referenten zu Wort (Bilder: KIT)

^{* aus: Gesellschaft für Informatik/Informatiklexikon/Algorithm Engineering (Autoren Peter Sanders und Dorothea Wagner)}