http://www.tu-ilmenau.de

Logo TU Ilmenau


FG Komplexitätstheorie und Effiziente Algorithmen


headerphoto FG Komplexitätstheorie und Effiziente Algorithmen
Ansprechpartner

Univ.-Prof. Dr. Martin Dietzfelbinger

Fachgebietsleiter

Telefon +49 (0)3677 69 2656

E-Mail senden

Ihre Position

INHALTE

Fachgebiet Komplexitätstheorie und Effiziente Algorithmen

Im Kern (fast) jeder ernsthaften Informatikanwendung stecken clevere Algorithmen, die jeweils erforderliche Grundaufgaben lösen: Verwaltung von Daten, damit man sie aufgrund von Schlüsseln schnell finden kann, Sortieren, Finden von kurzen Wegen oder billigen Verbindungen in Netzwerken, Finden von Teilstrukturen wie etwa Wörtern in Texten oder Teilmustern in Bildern, Routen von Nachrichten in Netzwerken auf kurzen Wegen, die einfach zu finden sind. Trotz immer schneller werdender Rechner sind in vielen Fällen gute Algorithmen nötig, um die ebenfalls immer größer werdenden Datenumfänge zu bewältigen. Gegenstand der Arbeit des Fachgebietes sind solche Algorithmen. Die Teile „Effiziente Algorithmen“ und „Komplexitätstheorie“ bilden dabei zwei Seiten derselben Medaille: Im Gebiet „Effiziente Algorithmen“ befasst man sich mit der Pflege eines großen Fundus von etablierten Algorithmen, mit Entwurfsstrategien und mit Methoden, die die quantitative Vorhersage des Ressourcenverbrauchs von Algorithmen ermöglichen. Ein immer wichtiger werdender Aspekt ist das relativ neue Gebiet des „Algorithm Engineering“, in dem die Probleme der Implementierung und der Beherrschung des realen Verhaltens von implementierten Algorithmen im Vordergrund stehen, insbesondere im Hinblick auf moderne Rechnerarchitekturen. In der „Komplexitätstheorie“ stellt man Untersuchungen an, die zeigen sollen, dass gewisse Probleme vermutlich nicht effizient (d.h. schnell oder in vorgegebenem Speicherplatz oder mit einem vorgegebenen Kommunikationsaufwand) gelöst werden können – solche Aussagen helfen im Bereich des Algorithmenentwurfs, um entscheiden zu können, wann man besser auf approximative Lösungen oder unter Verzicht auf Performanzgarantien auf Heuristiken ausweichen sollte.

 

In der Forschung des Fachgebiets werden insbesondere die folgenden Bereiche betont:

·        Randomisierte Suchstrukturen (Hashtabellen): Entwurf und Analyse

·        Randomisierte Algorithmen, Approximationsalgorithmen

·        Maschinennahe Algorithmenanalyse, Algorithm Engineering

·        Analyse von randomisierten Suchheuristiken

·        Untere Schranken für Routingverfahren in Netzwerken

·        Konkrete Komplexitätstheorie: Grenzen der effizienten Berechenbarkeit

Die Lehre des Fachgebietes deckt den gesamten Bereich der Algorithmik von den Grundlagen bis hin zu speziellen forschungsnahen Bereichen ab, ebenso wie die Grundzüge des großen Gebiets der Komplexitätstheorie.

 

 

 

 Erschienen im Juni 2014:    Erschienen im Januar 2011:    Erschienen im Mai 2008: