AG Algorithmen und Komplexität
>

Forschung

Die Forschung an der AG adressiert Fragestellungen aus dem Bereich der Algorithmik. Wir untersuchen die Effizienz von Algorithmen und Datenstrukturen mit dem Ziel, diese zu verbessern. Dabei richtet sich unser Augenmerk auf das mittlere Verhalten (Average-Case) von Struktur- und Leistungsparametern, da deren erwartete Ausprägung bei realistischen Annahmen über die Verteilung der Eingaben besser über die Komplexität informiert als Extremfälle, zumal dann, wenn letztere höchst unwahrscheinlich sind.

Mit unserem Werkzeug MaLiJAn und der dahinter liegenden Theorie zur sog. Maximum Likelihood Analyse wird eine semi-automatische Analyse möglich und eine Brücke zwischen analytischer und experimenteller Betrachtung von Algorithmen geschlagen.  Mit seiner Hilfe is es möglich, Algorithmen (in ihrer Java-Implementierung) im Kontext beliebiger Eingabedaten zu untersuchen, und zu verstehen, welche ihrer Funktionen wesentlich zum Ressourcenverbrauch (Platz, Zeit, Branch Mispredictions, ...) beitragen. Aus diesem Wissen können dann Verbesserungen abgeleitet werden (siehe Java 7's Dual Pivot Quicksort und Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn).

Ein zweiter Schwerpunkt unserer Arbeit ist die Bioinformatik. Hier ist unsere Expertise zu effizienten Algorithmen und Datenstrukturen sowie über die mathematische Modellbildung und Analyse von großem Nutzen für unsere bioinformatische Forschung und die Entwicklung effizienter Algorithmen sowie deren Umsetzung in Werkzeugen für Naturwissenschaftler.

Aktuell arbeiten wir an einer Grid-Version unseres Werkzeugs JAguc zur Analyse (biodiversity estimation) von Next Generation Sequencing Daten sowie an neuen Methoden zur RNA Strukturvorhersage -- beispielsweise mit dem Ziel effizienterer Algorithmen (siehe etwa A n2 RNA Secondary Structure Prediction Algorithm).