ERC Starting Grants: Informatik: Die schwierige Suche nach passgenauen Algorithmen

Geometrische Algorithmen sind überall. Mit ihrer Hilfe lassen sich die schnellste Route zur Arbeit berechnen, der Standort des nächsten Geldautomaten finden oder ähnliche Muster vergleichen. Doch nicht für alle praktischen Aufgaben sind Algorithmen bekannt, die so schnell und genau arbeiten wie für die jeweilige Anwendung gewünscht oder benötigt. Dieser Herausforderung nimmt sich ein Team um den Professor für Theoretische Informatik, Wolfgang Mulzer, im Rahmen des von ihm eingeworbenen ERC Starting Grants „Complexity Inside NP – A Computational Geometry Perspective“ (Komplexität innerhalb von NP – Ein Blick aus der algorithmischen Geometrie) an. Das Kernteam besteht dabei aus vier Personen; zusätzlich werden Fachleute aus dem Ausland einbezogen.

„Für viele Probleme kennen wir keine Algorithmen, die auch bei sehr großen Eingaben effizient funktionieren“, sagt der Informatiker. „Warum das so ist, ist eine offene Frage.“ Zwei Ursachen seien für ihn denkbar: „Es könnte sein, dass die Anwendungen einfach als solche schwierig sind, es könnte aber auch sein, dass wir das Problem noch nicht richtig verstanden haben.“ Um zu begreifen, wie Algorithmen auf effizientere Weise programmiert werden können, müssen Wolfgang Mulzer und sein Team also zunächst gewissermaßen bis an die Wurzel eines Problems vordringen: „Wir müssen erst einmal verstehen, was ein Problem schwierig macht. Sobald wir das ergründet haben, können wir maßgeschneiderte Lösungen für die Aufgaben entwickeln, die wir wirklich lösen wollen“, erläutert er.

Die Bedeutung von Algorithmen wird weiter steigen

Als Beispiel für praktische Probleme, die mit geometrischen Algorithmen gelöst werden sollen, nennt der Forscher die Aufgabe, ähnliche geometrische Muster zu finden, oder die Antwort auf die Frage, wie weit zwei Personen in einem geometrischen Labyrinth voneinander entfernt sein können. Es sind solche klassischen Probleme zur Wegfindung, Mustererkennung und Gittererzeugung, denen Mulzer und sein Team auf den Grund gehen. „Wir wollen beispielsweise untersuchen, ob es Beziehungen zwischen verschiedenen schwierigen Wegfindungsproblemen gibt.“ Dies würde bedeuten, dass ein schneller Algorithmus für ein bestimmtes Problem zu schnellen Algorithmen für viele weitere Herausforderungen führt. Doch damit nicht genug: „Wir wollen auch Aufgaben betrachten, für die eine gute Lösung zwar mathematisch garantiert ist, der Wissenschaft aber kein Weg bekannt ist, diese effizient zu finden.“

Die Erkenntnisse, die sich der Informatiker für die geometrische Wegführung erhofft, sollen im Idealfall auch anderen Anwendungen zugute kommen: „Denkbar sind beispielsweise Fortschritte im Umgang mit großen Datenmengen sowie Entwicklungen in der Computergrafik und in der Robotik“, erläutert Wolfgang Mulzer. Die Förderung des ERC läuft bis zu fünf Jahre, also bis 2022. Auch ohne eine Glaskugel steht für Wolfgang Mulzer allerdings schon jetzt fest: „Algorithmen werden unser Leben 2050 noch mehr prägen als heute.“

Carsten Wette