Im Institut für Theoretische Informatik erforschen wir die Grundlagen der algorithmischen Verarbeitung von Daten. Die Basis unserer Untersuchungen ist eine formale Modellierung, aus der mittels mathematischer Analysen präzise Aussagen gewonnen werden, welche unabhängig von speziellen Systemeigenschaften oder Technologiedetails gültig sind. Die Anwendungsgebiete sind vielfältig und reichen von Optimierungsproblemen, Kommunikationsnetzwerken, Datensicherheit und E-Commerce bis zur Bioinformatik und Immunologie.

Unser zentrales Ziel ist zu verstehen, wie viel Ressourcen (wie Zeit, Speicherplatz oder Prozessorkerne) benötigt werden, um konkrete algorithmische Probleme zu lösen. Hierzu entwerfen wir einerseits effiziente Algorithmen und Protokolle – von der Problemmodellierung über die Entwicklung von Lösungsstrategien bis zur Konstruktion geeigneter Datenstrukturen, wobei sich beispielsweise Laufzeitverbesserungen erreichen lassen durch Randomisierung oder Parallelisierung. Andererseits sind wir an Ergebnissen negativer Art interessiert der Form, dass zur Lösung eines Problems ein hoher algorithmischer Aufwand unumgänglich ist - sogenannte untere Komplexitätsschranken, auf denen die Sicherheit informatischer Systeme beruht.

Wichtige Hilfsmittel bei diesen Untersuchungen sind Methoden aus der Logik, der Diskreten Mathematik, insbesondere Kombinatorik und Graphentheorie, der Wahrscheinlichkeits- und Informationstheorie sowie der Zahlentheorie und Algebra.

Unsere wichtigsten Forschungsthemen sind:

Algorithmik

Maschinen- und Berechnungsmodelle

Algorithmische Komplexität

Bioinformatik

IT-Sicherheit

Data-Mining