Algorithmen und Theoretische Informatik

Im Folgenden beschreiben wir vier verschiedene Ansätze, mit denen wir Probleme im Zusammenhang mit Algorithmen angehen. Für viele von uns sind Graphen und Hypergraphen die Objekte, mit denen wir arbeiten. Sie bestehen aus einer (endlichen) Menge von Scheitelpunkten, manchmal auch Knoten genannt, und einer Menge von Kanten. Die Knoten haben Beschriftungen, z. B. ganzzahlige Beschriftungen, bis , wobei die Anzahl der Knoten ist. In Anwendungen stellt jedoch jeder Knoten oft ein bestimmtes Objekt dar, z. B. eine Person, ein Gebäude, eine Aufgabe, ein Ziel oder eine Variable.

Kanten in Graphen sind einfach eine Menge von zwei Scheitelpunkten, d. h. wir stellen uns vor, dass diese zwei Scheitelpunkte in einer Beziehung zueinander stehen. Es ist üblich, sich die Eckpunkte durch Punkte und die Kanten durch Linien zwischen zwei Eckpunkten vorzustellen. Dennoch ist ein Graph a priori unabhängig von einer solchen Darstellung. In Hypergraphen lassen wir auch größere Kanten zu, d. h. mit drei oder mehr Scheitelpunkten. Dies wird in der Regel durch eine Blase um alle Scheitelpunkte der (Hyper-)Kante veranschaulicht.

Kanten in Graphen können auch gerichtet sein, d. h. eine Ausrichtung haben, und von einem Scheitelpunkt zu einem anderen führen, oder mit Gewichten versehen sein.

Graphen sind grundlegende Strukturen in der Mathematik. Sie sind sehr vielseitig und kommen daher in vielen Kontexten vor. Doch obwohl (Hyper-)Graphen so einfach zu definieren sind, weisen sie ein sehr faszinierendes und teilweise rätselhaftes Verhalten auf, das in den letzten Jahrzehnten Gegenstand sehr aktiver Forschung war.

Traditionell werden Algorithmen anhand einfacher Modelle von Problemen und Maschinen entworfen. Im Gegenzug sind wichtige Ergebnisse nachweisbar, wie z. B. Leistungsgarantien für alle möglichen Eingaben. Dies führt oft zu eleganten Lösungen, die an viele Anwendungen angepasst werden können und deren Leistung für zuvor unbekannte Eingaben vorhersehbar ist.  In der Algorithmentheorie hingegen ist das Aufgreifen und Implementieren eines Algorithmus Teil der Anwendungsentwicklung.  Leider ist diese Art der Übertragung von Ergebnissen ein langwieriger Prozess, und manchmal schneiden die theoretisch besten Algorithmen in der Praxis schlecht ab.  Dadurch entsteht eine wachsende Kluft zwischen Theorie und Praxis: Realistische Hardware mit ihrer Parallelität, ihren Speicherhierarchien usw. weicht von traditionellen Maschinenmodellen ab.

Im Gegensatz zur Algorithmentheorie verwendet die Algorithmenentwicklung einen Innovationszyklus, bei dem die Entwicklung von Algorithmen auf der Grundlage realistischer Modelle, theoretischer Analysen, effizienter Implementierungen und sorgfältiger experimenteller Bewertungen unter Verwendung realer Eingaben die Lücken zwischen Theorie und Praxis schließt und zu verbesserten Anwendungscodes und wiederverwendbaren Softwarebibliotheken führt (siehe hier). Dies führt zu Ergebnissen, auf die sich Anwender für ihre spezifische Applikation verlassen können.

Die Gruppe Algorithm Engineering befasst sich mit einem breiten Spektrum skalierbarer Graphenalgorithmen, insbesondere im Zusammenhang mit sehr großen Eingaben. Im Allgemeinen stützt sich die Forschung auf fünf stark miteinander verbundene Säulen: mehrstufige Algorithmen, praktische Kernelisierung, Parallelisierung, memetische Algorithmen und dynamische Algorithmen. Zu diesem Zweck entwickelt unsere Gruppe Algorithmen, die bekannte Methoden verbessern. In der Regel veröffentlichen wir die entwickelten Techniken und Algorithmen als einfach zu verwendende Open-Source-Software. Beispiele hierfür sind eine weit verbreitete Bibliothek von Algorithmen für (Hyper-)Graphenpartitionierung, Graphenzeichnung, (gewichtete) unabhängige Mengen, Graphenclusterung, Graphengenerierung, minimale Schnitte, Prozessabbildung und vieles mehr.

Eines der bekanntesten algorithmischen Probleme ist das Problem des Handlungsreisenden. Gegeben sind Städte und Entfernungen zwischen jedem Städtepaar. Wie lautet die kürzeste Tour durch alle Städte? (Dies kann durch einen vollständigen Graphen mit Eckpunkten und Gewichten an den Kanten modelliert werden). Sicherlich können wir einfach alle möglichen Routen prüfen und die kürzeste auswählen. Dies ist jedoch überhaupt nicht möglich! Es gibt ungefähr solcher Routen, was eine gigantische Zahl ist, selbst wenn nur mäßig groß ist, sagen wir etwas über 20.

Finden wir also eine bessere Lösung? Ja, aber es scheint, dass im Allgemeinen eine exponentielle Anzahl von Berechnungsschritten in notwendig ist.

Der Nachweis, dass Algorithmen nicht mehr als eine garantierte Anzahl von Schritten benötigen, wird als Worst-Case-Analyse bezeichnet. Zu diesem Zweck werden häufig schwere mathematische Theoreme ausgenutzt, um Strukturen auf Graphen aufzuzeigen, die wiederum Verbesserungen bei der Laufzeit von Algorithmen ermöglichen.

Unser Forschungsschwerpunkt liegt auf der Untersuchung von Graphen und Hypergraphen unter verschiedenen Gesichtspunkten. Dazu gehören Fragen der folgenden Form:

• Wann ist ein bestimmter einfacher Graph ein Untergraph eines anderen Graphen?
• Wann erhält man Dekompositionen der Knotenmenge oder der Kantenmenge eines Graphen in einem anderen einfachen Graphen?
• Wie verhalten sich typische Graphen im Vergleich zu Worst-Case-Fällen?

Neben anderen Ergebnissen haben wir das berühmte Oberwolfach-Problem für große Instanzen gelöst, das von Gerhard Ringel in den 1960er Jahren gestellt wurde.

Für die meisten Probleme gibt es viele verschiedene Algorithmen, die sie lösen können, und ihr Ressourcenverbrauch (Berechnung, Kommunikation, Speicherplatz) hängt von den Problemparametern ab (Datengrößen, Datenanordnung, Datentypen, Datenwerte). Schon aus theoretischer Sicht erfordern unterschiedliche Problemparameter also unterschiedliche Algorithmen, aber es gibt zu viele Algorithmen, um sie alle im Hinblick auf den Ressourcenverbrauch zu bewerten. Außerdem gibt es für die meisten Algorithmen viele verschiedene Implementierungen, und die Ausführungszeit jeder Implementierung hängt von der jeweiligen Hardware ab. Aus praktischer Sicht ist es also sehr schwierig, für gegebene Problemparameter und Hardware zu wissen, welcher Algorithmus und welche Implementierung am besten sind. Wir können nur sehr wenige Kombinationen zu bewerten, denn die Entwicklung guter Algorithmen und Implementierungen ist ein langwieriger Prozess, und die Suche nach der besten Kombination gleicht der Suche nach der Nadel im Heuhaufen.

Wir können dieses Problem nicht generell lösen, sondern nähern uns der besten Kombination von oben und unten. Von unten bedeutet, dass wir algorithmische Bausteine mit nahezu optimaler Leistung auf spezifischer Hardware erstellen, d. h. die gegebene Berechnung kann nicht in wesentlich kürzerer Zeit durchgeführt werden. Mit solchen Bausteinen lassen sich Algorithmen mit hoher Leistung zusammenstellen, aber nur, wenn auch die Interaktion zwischen den Blöcken effizient ist. Darüber hinaus benötigen wir von oben her einige Anwendungshinweise für die Art der algorithmischen Strukturen, auf die wir abzielen sollten. Wir arbeiten hauptsächlich mit wissenschaftlichen Anwendungen, bei denen die Anleitung durch die numerische Analyse der Schemata gegeben wird. Die Bausteine sind parallele Datenauswahl und parallele lineare Algebra-Operationen.

In vielen Fällen wissen wir noch nicht, wie weit unsere aktuelle Lösung von der besten Kombination aus Algorithmus und Implementierung entfernt ist, aber manchmal gelingt es uns, etwas zu entwerfen, das der optimalen Lösung sehr nahe kommt, und dann sind die Ergebnisse überwältigend.

Wir konzentrieren uns auf große kombinatorische Optimierungsprobleme mit Anwendungen in den Bereichen Computer Vision und Bioinformatik. Kombinatorisch bedeutet, dass die Lösung aus einer endlichen, aber exponentiell wachsenden Menge ausgewählt werden muss, z. B. aus der Menge aller möglichen Untermengen einer gegebenen Menge, Permutationen oder Pfaden in einem gegebenen Graphen. Die meisten dieser Probleme lassen sich in einem gängigen Format ganzzahliger linearer Programme formulieren und mit handelsüblicher Software lösen. Groß bedeutet, dass die Größe der Probleme ihre Lösung mit Standardmethoden ineffizient oder sogar praktisch unmöglich macht. Dies ist häufig der Fall bei Anwendungen wie Stereovision und Bildsegmentierung, Schätzung von Objektrotation und -translation im Raum sowie Zellvergleich und -verfolgung in mikroskopischen Bildern.

Wir entwickeln nicht nur spezielle Algorithmen zur Optimierung gegebener kombinatorischer Probleme, sondern lernen auch Problemparameter aus Trainingsdaten. Zu diesem Zweck kombinieren wir künstliche neuronale Netze mit den effizientesten kombinatorischen Techniken.