Forschungsgebiet
Effiziente Algorithmen und Datenstrukturen sind Grundvoraussetzung für alle anspruchsvollen Computeranwendungen. Algorithmik – die systematische Entwicklung effizienter Algorithmen – ist deshalb entscheidend für die Umsetzung technologischer Möglichkeiten in Anwendungen mit großer Bedeutung für Technik, Wirtschaft, Wissenschaft und unser tägliches Leben. Der Lehrstuhl von Professor Sanders am Institut für Theoretische Informatik beschäftigt sich vor allem mit der „Basic Toolbox“ von Verfahren, die in sehr vielen Anwendungen benötigt werden. Dazu zählen beispielsweise Sortieren, Indexdatenstrukturen, Wegesuche in Graphen oder deren Zerlegung in kompakte Teile. Die Arbeitsgruppe entwickelt auch Open-Source Software zur Lösung dieser Probleme und setzt das erworbene Know-How zur Lösung ausgewählter konkreter Anwendungsprobleme ein.
Auf den ersten Blick ist es erstaunlich, dass es trotz jahrzehntelanger Forschung noch viele offene Probleme bei Basisalgorithmen gibt. Dafür gibt es zwei Gründe. Einerseits haben wir es in den letzten Jahren mit explosiv wachsenden Datenmengen zu tun, die nur noch mit immer komplexerer paralleler Hardware zu bewältigen sind. Dadurch eröffnen sich außerdem zusätzliche, vielseitig benötigte Fragestellungen wie Lastbalancierung und effiziente Kommunikation. Andererseits hat sich in den letzten Jahrzehnten ein Graben zwischen Theorie und Praxis aufgetan. Theoretiker entwerfen ausgefeilte Lösungen mit starken Leistungsgarantien für vereinfachte Fragestellungen, ignorieren dabei aber allzu oft die Implementierbarkeit oder die tatsächlichen Gegebenheiten der Anwendungen und moderner Hardware. Praktiker ignorieren ihrerseits oft theoretische Einsichten und Methoden und gelangen dadurch zu Ad-Hoc-Ansätzen ohne erkennbare Leistungsgarantien. Deshalb steht am Lehrstuhl Sanders die Methodik des Algorithm Engineering im Mittelpunkt, die die beschriebenen Herausforderungen durch eine Integration von realistischer Modellierung, Entwurf, Analyse, Implementierung und experimenteller Evaluierung zu überwinden hilft.
28.08.2024: Dominik Schreiber erhält für seine Dissertation "Scalable SAT Solving and its Application" zwei Auszeichnungen: zum einen den gemeinsamen Dissertationspreis der Gesellschaft für Informatik, der Österreichischen Computergesellschaft und der Schweizer Informatik Gesellschaft, und zum anderen den Fahiem Bacchus PhD Award in Satisfiability.
Mehr erfahren30.11.2023: Daniel Funke verteidigt sehr erfolgreich seine Dissertation "Algorithms for Triangles, Cones & Peaks".
Dissertation anzeigen17.11.2023: Dominik Schreiber verteidigt sehr erfolgreich seine Dissertation "Scalable SAT Solving and its Application".
21.07.2023: Demian Hespe verteidigt sehr erfolgreich seine Dissertation "Enabling Scalability: Graph Hierarchies and Fault Tolerance".