BrandingBranding
Fakultät
Mathematikon Entrance

Unsere Fakultät ist akademische Heimat von Forscher:innen, Dozent:innen, und Student:innen der Mathematik und Informatik. Ihre Institute und Betriebseinrichtungen sind untergebracht im angenehm gelegenen Mathematikon auf dem Campus Neuenheimer Feld der Universität Heidelberg. Herzlich Willkommen!

Promotion
Mathematikon Seminar Room

Die Promotion ist der Nachweis der Befähigung zu selbständiger wissenschaftlicher Forschung. Unter dem Schirm der Gesamtfakultät für Mathematik, Ingenieur- und Naturwissenschaften vergeben wir jedes Jahr über 30 Doktortitel in den Fächern Mathematik und Informatik.

Studium
Mathematikon Library

heiMATH: Ob Mathematik, Informatik oder eine interdisziplinäre Variante, mit Abschluss B.Sc., M.Sc. oder M.Ed., Berufsziel in Forschung, Schule oder Industrie: Bei uns in Heidelberg finden Sie ein reichhaltiges und erstklassiges Lehrangebot für ein anspruchsvolles Studium in einer intellektuell stimulierenden und traditionsreichen Umgebung. 

Outreach
Mathematikon Lobby

Wir fördern das Interesse an Mathematik und Informatik – durch unsere Veranstaltungen für Schulen sowie ein breites Publikum. Ehemalige und Einsteiger nehmen Teil und tragen bei zu gemeinsamem Wissen und Kontakten.

home icon
envelope icon
Mathematikon Courtyard
Mathematik und Informatik — Forschung

Algorithmen und Theoretische Informatik

In der modernen Welt sind wir von Algorithmen umgeben. Jede Aufgabe, die ein Computer ausführt - sei es die Verarbeitung von Bildern, die Verbindung zum Internet oder die Verwendung einer Kreditkarte - erfordert eine präzise Schritt-für-Schritt-Anleitung, die ein Computer verstehen kann. Diese Anleitung ist ein Algorithmus. Aber Algorithmen sind nicht nur für Computer gedacht. Schon vor mindestens 3600 Jahren wurden Algorithmen in der Mathematik verwendet und auch heute noch sind viele mathematische Beweise algorithmisch aufgebaut. Es gibt drei Hauptfragen, die man sich zu einem Algorithmus stellen kann: Gibt es einen Algorithmus, der ein bestimmtes Problem löst? Wenn ja, wie viele Ressourcen (Rechenleistung, Kommunikation, Arbeitsspeicher, Speicherplatz) benötigt er? Und wie schnell ist er, wenn er auf einer bestimmten Hardware ausgeführt wird?

In Heidelberg beschäftigen wir uns mit Algorithmen aus verschiedenen Blickwinkeln. Insbesondere konzentrieren sich einige Forscher:innen auf die Leistung von Algorithmen, auf reale Daten oder auf die optimale Nutzung von Hardware zur Beschleunigung von Algorithmen, während andere daran interessiert sind, ob es überhaupt Algorithmen gibt, die bestimmte Probleme lösen, unabhängig davon, ob sie in der Praxis anwendbar sind. Wir beweisen insbesondere Strukturtheoreme für diskrete Objekte wie Graphen und Hypergraphen, die die Grundlage für neue theoretische Techniken bilden. Wir untersuchen, wie verschiedene, oft bekannte, theoretische Techniken in der Praxis funktionieren, und entwickeln und optimieren Algorithmen, um die beste Leistung zu erzielen.
Im Rahmen unserer Forschung befassen wir uns mit verschiedenen Problemen und Techniken, die eine bessere Skalierung von Algorithmen ermöglichen. Dazu gehören die Theorie und das Engineering von (Hyper-)Graphenalgorithmen, randomisierten Algorithmen, massiv parallelen Algorithmen (Many-Core, Multi-Core, verteilter Speicher), kommunikationseffizienten Algorithmen sowie Out-of-Core-Algorithmen. Unser Forschungscluster entwickelt auch Open-Source-Software für die Lösung algorithmischer Probleme und nutzt sein Know-how zur Lösung ausgewählter konkreter Anwendungsprobleme.

Verschiedene Perspektiven auf Algorithmen

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.

Algorithmenentwicklung

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.

Theoretische Informatik

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.

Anwendungsspezifische Datenverarbeitung

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.

Optimierung für Maschinelles Lernen

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.

Arbeitsgruppen und Juniorwissenschaftler/ Forschungsgruppenleiter

Prof. Dr. Christian SchulzAlgorithmenentwicklung

Skalierbare Graphenalgorithmen, praktische Datenreduktion, dynamische Graphenalgorithmen, memetische Algorithmen

 
Prof. Dr. Christian Schulz
Jun.-Prof. Dr. Felix JoosTheoretische Informatik

Graphentheorie, Algorithmen auf Graphen, Diskrete Mathematik

 
Jun.-Prof. Dr. Felix Joos
Prof. Dr. rer. nat. Robert StrzodkaAnwendungsspezifische Datenverarbeitung

Parallele Algorithmen und Hardware (GPU, Many-Core-CPU, FPGA) in Bezug auf Datendarstellung, Datenzugriff, Datenstruktur, numerische Methoden und Programmierabstraktionen

 
Prof. Dr. Robert Strzodka
Gruppe Anwendungsspezifische Datenverarbeitung
Dr. Bogdan SavchynskyyOptimierung für Maschinelles Lernen

Diskrete Optimierung in großem Maßstab, diskrete grafische Modelle, Zuweisung und Verfolgung, Lernen von kombinatorischen Problemen

 
Bogdan Savchynskyy
PD Dr. Wolfgang MerkleTheoretische Informatik

Logik und Berechenbarkeit

 
Wolfgang Merkle
Zuletzt aktualisiert am 13. Okt. 2021 um 15:52