Hauptinhalt

Forschung der AG Algorithmik

Die Arbeitsgruppe Algorithmik beschäftigt sich mit dem Entwurf und der Analyse von Algorithmen und Datenstrukturen, mit dem übergeordneten Ziel, das Arbeiten mit immer größeren Datenmengen effizienter zu gestalten.

Unsere Forschung umfasst einerseits die grundlegenden Fragen der Theoretischen Informatik, die aus diesem Ziel folgen und mittels mathematischer Beweise beantwortet werden; etwa die Frage nach der asymptotischen Komplexität einer algorithmischen Fragestellung.  Andererseits betätigen wir uns im Engineering von Algorithmen und Datenstrukturen, um theoretische Ergebnisse für praktische Anwendungen zugänglich und gewinnbringend nutzbar zu machen.

Aktuelle Schwerpunktthemen sind:

Speichereffiziente Datenstrukturen, Computing over Compressed Data

Daten komprimiert, d.h. mit möglichst wenig Bits, darzustellen ist ein Standardvorgehen für die Speicherung und Übertragung von Daten.  Aber auch für Berechnungen selbst wird Speichereffizienz zunehmend wichtiger, um mehr Daten im schnellen Hauptspeicher verarbeiten zu können.  Anders als für klassische Komprimierungsverfahren genügt dafür aber nicht eine sequentielle Dekomprimierungsmethode, sondern wir brauchen Algorithmen, die wahlfrei direkt in der komprimierten Darstellung arbeiten können (computing over compressed data).
In der AG Algorithmik entwickeln wir solche Methoden, deren Speicherbedarf sich bestmöglich an die tatsächlich vorhandenen Daten und ihre Komprimierbarkeit anpasst, insbesondere für Daten mit einer Baum- oder Graphstruktur.

Unsere Forschung wird dabei vom britischen EPSRC mit dem Projekt Computing over Compressed Graph-Structured Data finanziert.

Adaptive Algorithmen, Analysis of Algorithms, Algorithm Science

Die Analyse von Algorithmen umfasst die präzise Vorhersage der Kosten von Algorithmen und Datenstrukturen, sowohl rein mathematisch-asymptotisch, etwa durch Average-Case-Analysen (analysis of algorithms), als auch durch empirische Untersuchungen (algorithm science).  Dabei berücksichtigen wir konstante Faktoren ebenso wie der Einfluss der konkreten Eingabe (adaptive analysis).

Auf Basis dieser Analysen entwerfen wir schließlich verbesserte Lösungen für die fundamentalen algorithmischen Bausteine der Informatik – insbesondere Suchen, Sortieren und Selektieren – inklusive dem Entwickeln konkreter Implementierungen (algorithm engineering), die im Erfolgsfall breite Verwendung finden; so etwa im Fall von Powersort, dem neuen Standardsortierverfahren in Python.

Aktuelle Informationen zu unsere Forschung finden sich auf www.wild-inter.net, inklusive einer Liste von Publikationen und Vorträgen.