Forschungsbereich „Algorithmische und formale Grundlagen“
Algorithmen sind strukturierte Anweisungsabfolgen, die Aufgaben lösen. Die Informatik strebt danach, effektive Algorithmen für bestimmte Fragestellungen zu entwickeln, welche mit minimalen Anweisungen und Ressourcen auskommen. Eine zentrale Frage ist, unter welchen Bedingungen Probleme überhaupt algorithmisch gelöst werden können. Ein besonderer Bereich der Informatik ist die nichtnumerische Informationsverarbeitung, die auf formalen Logikmechanismen basiert und aus berechnungstechnischen Perspektiven erschlossen wird.
Beispielhaft sind folgende Forschungsthemen von Bedeutung:
- Analyse von Problemen hinsichtlich ihrer algorithmischen Komplexität
- Entdeckung effizienter Algorithmen für konkrete Fragestellungen, beispielsweise durch Anlehnung an natürliche Phänomene (Computational Intelligence) oder Kombination effizienter Algorithmen für Teilprobleme zur Bewältigung komplexer Herausforderungen (Algorithm Engineering)
- Abschätzung der Komplexität von Algorithmen, zum Beispiel die Anzahl der auszuführenden Anweisungen
- Experimentelle Untersuchung von Algorithmen
- Bewertung von heuristischen und exakten Algorithmen auf Grundlage realer Anwendungsprobleme
Aktuelle Forschungsergebnisse
- Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick: Reasoning on data partitioning for single-round multi-join evaluation in massively parallel systems. Commun. ACM 60(3): 93-100 (2017). DOI: 10.1145/3041063
- Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume: Reachability Is in DynFO. J. ACM 65(5): 33:1-33:24 (2018). DOI: 10.1145/3212685
- Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger:
Fine-grained Complexity Analysis of Two Classic TSP Variants. ACM Trans. Algorithms 17(1): 5:1-5:29 (2021). DOI: 10.1145/3414845 - Jonas Ellert, Johannes Fischer: Linear Time Runs Over General Ordered Alphabets. ICALP 2021: 63:1-63:16. DOI: 10.4230/LIPIcs.ICALP.2021.63