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.
24.10.2024: Hans-Peter Lehmann verteidigt sehr erfolgreich seine Dissertation "Fast and Space-Efficient Perfect Hashing".
11.10.2024: Das HPC-Projekt "Scalable Discrete Algorithms for Big Data Applications" auf HoreKa wurde auf dem 27. HLRS Results and Review Workshop mit dem "Golden Spike Award" ausgezeichnet.
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.
mehr17.06.2024: Die erste Version des C++ MPI-Wrappers KaMPIng ist erschienen und wurde auf der SPAA vorgestellt. Die Vollversion wurde auf der Supercomputing (SC) angenommen.
mehr30.11.2023: Daniel Funke verteidigt sehr erfolgreich seine Dissertation "Algorithms for Triangles, Cones & Peaks".
17.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".
26.10.2022: Tobias Heuer verteidigt sehr erfolgreich seine Dissertation "Scalable High-Quality Graph and Hypergraph Partitioning".
10.07.2020: Der massiv parallele und verteilte SAT Solver "mallob" von Dominik Schreiber hat im Cloud Track der internationalen SAT Competition 2020 mit Abstand den ersten Platz erreicht.
31.03.2020: Peter Sanders erhält einen ERC Advanced Grant für sein Projekt „ScAlBox – Engineering Scalable Algorithms for the Basic Toolbox“. Weitere Informationen finden Sie auf der Fakultätshomepage und der Webpräsenz des Europäischen Forschungsrats.
08.09.2020: Auf dem European Symposium on Algorithms 2020 hielten Peter Sanders und Ulrich Meyer (Universität Frankfurt) einen Vortrag zu ihrer Arbeit, für die sie im März 2020 mit dem "Test-of-Time"-Award 2019 ausgezeichnet worden waren. Sie finden den Vortrag hier.
mehr06.01.2020: Peter Sanders wurde zum Vorsitzenden des Steering Committes des SIAM Symposium on Algorithm Engineering and Experiments (ALENEX) gewählt. ALENEX ist die wichtigste nordamerikanische Konferenz zum Thema und eine der wichtigsten weltweit.