Fakultät Informatik

Algorithms & Complexity

Die Forschung des Clusters deckt ein breites Spektrum grundlangenorientierter und angewandter Arbeitsrichtungen in der Algorithmik ab. Ziel ist es, Algorithmen zu entwickeln und ihre Performanz bezüglich eines gewünschten Qualitätsmaßes zu analysieren. Die Schwerpunkte liegen u. a. auf der Erforschung von

  • Approximations- und Online-Algorithmen. In der internationalen Algorithmenforschung bildet ihre Entwicklung seit geraumer Zeit einen Arbeitsschwerpunkt. Sie sollen helfen, Näherungslösungen für Probleme zu entwickeln, die sich nur schwer oder gar nicht exakt lösen lassen. Der Cluster entwickelt Algorithmen, die ein beweisbar gutes Verhalten erzielen. Untersucht werden insbesondere Probleme, die in der Ressourcenverwaltung von Computersystem, in großen Netzwerken sowie in der Datenstrukturierung auftreten.
  • Randomisierten Algorithmen. Über die letzten 25 Jahre ist ihre Entwicklung und Analyse ein wesentlicher Bestandteil der Algorithmentheorie geworden. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Der Cluster entwickelt und analysiert randomisierte Algorithmen für grundlegende Optimierungsprobleme.
  • Parallelen und Netzwerk-Algorithmen. Netzwerk- und Graphen-Algorithmen dienen der Optimierung von Abläufen in verschiedensten Anwendungsbereichen. Die Forschung auf dem Gebiet der parallelen Algorithmen untersucht parallele Rechnerarchitekturen und entwickelt parallele Algorithmen für grundlegende Probleme.
  • Algorithmischer Spieltheorie. Dabei handelt es sich um ein junges Forschungsgebiet an der Schnittstelle von theoretischer Informatik, Mathematik und Betriebswirtschaftslehre, da es sich mit dem optimalen strategischen Verhalten in interaktiven Situationen befasst.
  • Algorithm Engineering. Hier hat die Forschung in einigen Bereichen bereits erfolgreich dazu beigetragen, die Kluft zwischen Theorie und Praxis zu überbrücken. Paradebeispiele sind die rasanten Fortschritte, die sich durch neue Algorithmen für die Routenplanung oder die Suchfunktion in Texten erzielen ließen. Der Cluster führt experimentelle Studien durch, in denen die durch mathematische Analysen gewonnenen Forschungsergebnisse validiert werden.

Ein weiterer aktueller Arbeitsbereich beschäftigt sich mit der Entwicklung von energieeffizienten Algorithmen. Da auch Rechen- und Datenzentren von den stark gestiegenen Energiekosten betroffen sind, untersucht der Cluster algorithmische Techniken, die den Energiebedarf in Computersystemen reduzieren.

Im Bereich Anwendungen erforschen die Cluster-Mitglieder grundlegende algorithmische und komplexitätstheoretische Probleme in der Berechnungslogik, Programm- und Systemverifikation, mathematischer Optimierung, Bilderkennung sowie im wissenschaftlichen Rechnen. In diesem Kontext studieren sie verschiedene Effizienz- und Komplexitätsmaße. Außerdem werden Algorithmen für massiv-parallel Architekturen entwickelt, in denen eine riesige Anzahl von Prozessoren über ein Netzwerk verbunden sind.

Wissenschaftler/innen

  • Prof. Susanne Albers
  • Prof. Michael Bader
  • Prof. Martin Bichler
  • Prof. Felix Brandt
  • Prof. Hans-Joachim Bungartz
  • Prof. Daniel Cremers
  • Prof. Javier Esparza
  • Prof. Peter Gritzmann (Fak. f. Mathematik)
  • Prof. Stephan Günnemann
  • Prof. Ernst W. Mayr
  • Prof. Tobias Nipkow
  • Prof. Harald Räcke
  • Prof. Helmut Seidl

 

 

Aktuelle Aktivitäten

DFG Priority Programme 1736 "Algorithms for Big Data"

(2013 - 2019)

 Mehr dazu

Exemplarische Projekte

Energy-efficient Scheduling

Partner: Prof. Susanne Albers

Dieses Projekt erforscht algorithmische Techniken zur Energieeinsparung in Hardwareumgebungen. Es unterstützt damit die Verarbeitung großer Datenmengen auf Systemebene. Im Mittelpunkt steht die Methode des Dynamic Speed Scaling. Der Großteil der in der Literatur existierenden Arbeiten geht von idealisierten Annahmen bezüglich der Prozessorarchitektur aus: Es wird angenommen, ein Prozessor habe ein kontinuierliches, unbegrenztes Geschwindigkeitsspektrum und könne Änderungen in der Geschwindigkeit jederzeit verlustfrei vornehmen. Das Projekt entwickelt und analysiert Algorithmen für ein realistisches Szenario, in dem ein Prozessor über eine endliche Menge von diskreten Geschwindigkeiten verfügt. Experimente, welche die Algorithm-Eingineering-Komponente des Projekts bilden, ergänzen hierbei die theoretisch orientierte Forschungsarbeit. Algorithmische Ergebnisse sollen im Rahmen des Projektes stärker für die Praxis nutzbar werden.

 Mehr dazu

Gottfried Wilhelm Leibniz-Preis für Prof. Susanne Albers

Die Auszeichnung unterstützt die Forschung in einem weiten, fast unbegrenzten Themenspektrum in der Entwicklung und Analyse von Algorithmen, der algorithmischen Spieltheorie und des Algorithm Engineering. Die Arbeiten konzentrieren sich auf den wissenschaftlichen Fortschritt im Bereich der Online- und Approximationsalgorithmen. Die Studien betreffen insbesondere grundlegende Probleme in der Ressourcenverwaltung von Computersystemen, das Prozessorscheduling, Netzwerkdesignspiele und energieeffiziente Algorithmen.

 Mehr dazu

Geometrische Rekonstruktion in refraktions- und diffraktionsbasierter Tomografie

Partner: Prof. Peter Gritzmann

Im Zentrum steht die mathematische Modellierung und Analyse von Problemen in der (dynamischen) Tomografie sowie die Entwicklung von Algorithmen basierend auf Geometrie und kombinatorischer Optimierung.

 Mehr dazu

Gradschranken für Gröbnerbasen wichtiger Klassen von Polynomidealen und effiziente Algorithmen

Partner: Prof. Ernst Mayr

Im Jahr 1965 führte Buchberger in seiner Dissertation Gröbnerbasen ein, um Probleme der Computeralgebra algorithmisch zu lösen. Das grundlegendste Beispiel ist das Wortproblem für Polynomideale, welches darin besteht zu entscheiden, ob ein gegebenes Polynom Element eines gegebenen Ideals ist. Buchberger konnte einen Algorithmus präsentieren, mit dem sich eine Gröbnerbasis für jedes Polynomideal berechnen lässt.

 Zunächst war die Komplexität des Algorithmus unbekannt. Kleine Probleminstanzen konnten gut gelöst werden, und zahlreiche Verbesserungen des Algorithmus als auch neue Ansätze wurden vorgestellt. Für größere Probleminstanzen erreichten die Algorithmen jedoch schnell die durch Rechenzeit und Speicherplatz gesetzten Grenzen. Insbesondere konnten Gröbnerbasen mit vielen Variablen nur selten berechnet werden. Dieses Verhalten ist unvermeidlich wie Mayr und Meyer zeigten. Sie konnten eine untere Schranke für den Platzbedarf des Wortproblems für Polynomideale herleiten, welche exponentiell in der Anzahl der Variablen ist. Da Gröbnerbasen verwendet werden können, um das Wortproblem für Polynomideale zu lösen, muss ihre Berechnung ebenfalls schwer sein.

 Das Ziel unseres Projektes innerhalb des SPP1489 ist es interessante Fälle zu finden, in denen das Wortproblem für Polynomideale beweisbar einfacher und somit in der Praxis besser handhabbar ist. Bisher haben wir neue und exakte Komplexitätsergebnisse für das Wortproblem für allgemeine Polynomideale erzielt. Diese hängen von der Dimension des Ideals ab. Ferner haben wir zahlreiche neue und substantiell verbesserte obere Schranken für Probleme mit Polynomidealen erzielt; diese beziehen sich auf radikale Binomideale.

 Mehr dazu