Herzlich willkommen im Institut für Theoretische Informatik |
Wir vertreten die Theoretische Informatik an der Fakultät für Informatik und Automatisierung der Technischen Universität Ilmenau. Hierunter verstehen wir insbesondere die Algorithmik und die Komplexitätstheorie, die Automatentheorie und die Logik in der Informatik. Diese Schwerpunkte spiegeln sich im Lehrangebot, in der Forschung und in der Gliederung des Instituts in die Fachgebiete "Algorithmik" und "Automaten und Logik" wider.
Institutsdirektor
Sekretariat
Anschrift
Technische Universität Ilmenau
Fakultät für Informatik und Automatisierung
Institut für Theoretische Informatik
Postfach 10 05 65
98684 Ilmenau
Technische Administration
Dipl.-Ing. Andreas Krechla
+49 3677 69 - 2787
⌂ Zusebau, Raum 1049
Fachgebiete im Institut für Theoretische Informatik |
Das Fachgebiet Algorithmik befasst sich mit der Entwicklung von Algorithmen und der Untersuchung ihrer prinzipiellen Grenzen.
Die beiden Kernfragen sind:
- Unter welchen Bedingungen existieren effiziente Algorithmen und wie unterscheidet sich die Struktur von "leichten" und "schweren" Eingabeinstanzen?
- Was sind die Möglichkeiten und die prinzipiellen Grenzen bestimmter algorithmischer Strategien und Lösungsverfahren?
Die untersuchten Verfahren reichen hierbei von klassischen Entscheidungsproblemen (wie dem Erfüllbarkeitstest der Aussagenlogik) über Zähl- und Aufzählalgorithmen (das Bestimmen der Anzahl bzw. das Generieren aller Lösungen) bis hin zu dynamischen Algorithmen, die effiziente Updateoperationen unterstützen.
Konkrete Anwendungsfelder dieser Forschung sind
- Methoden zur Anfrageoptimierung und Anfrageauswertung auf relationalen und probabilistischen Datenbanken sowie
- Verfahren und Datenstrukturen im Bereich SAT- und Constraint-Solving.
Die Forschungsschwerpunkte des Fachgebiets Automaten und Logik liegen in den Bereichen Methoden der automatischen Verifikation verteilter Systeme und automatische Strukturen. Diese Untersuchungen verwenden insbesondere Methoden der Logik und der Automatentheorie und gehören daher zum umfassenderen Gebiet der Logik in der Informatik.
In der automatischen Verifikation versuchen wir einen Kompromiss zwischen der Ausdrucksstärke von Spezifikationssprachen und ihrer algorithmischen Beherrschbarkeit zu finden. Dabei werden kürzlich gewonnene theoretische Erkenntnisse zu verteilten Modellen mit endlich vielen internen Zuständen auch auf ihre praktische Relevanz hin untersucht, angepasst und erweitert.
Neben diesen Systemen ist auch die Verifikation von solchen mit unendlich vielen internen Zuständen (die z. B. durch stacks oder string-Variablen auftreten können) von Interesse. Ein abstraktes Modell dieser Systeme sind automatische Strukturen. Wir untersuchen diese Strukturen von der algorithmischen (Welche Fragen sind mit welchem Aufwand lösbar?) und von der abstrakten Seite (Welche modelltheoretischen Eigenschaften zeichnen diese Strukturen aus?)
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.
Aktuelles aus dem Institut für Theoretische Informatik |
