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.
Die Algorithmik beschäftigt sich mit dem Entwurf und der Analyse systematischer Strategien für Problemstellungen, die mit Hilfe von Computerprogrammen gelöst werden können. Bei der Diskreten Optimierung sollen für gegebene Eingaben möglichst gute Lösungen gefunden werden, beispielsweise die kostengünstigste Fahrtroute für ein Speditionsunternehmen, die optimale Art der Weiterleitung von Paketen in Postzentren oder die beste Packung von Gegenständen in einem Versandpäckchen. Für derartige Probleme entwickeln wir effiziente, allgemeine Lösungsstrategien. Methodisch werden hierbei Prinzipien wie Heuristiken, Algorithmen mit probabilistischen Entscheidungen sowie Approximationsverfahren weiterentwickelt und Analysewerkzeuge – etwa zur Laufzeitabschätzung – verfeinert.
Die Theoretische Informatik versucht mit ihren Methoden, von Technologiedetails möglichst zu abstrahieren. Jedoch ist der Unterschied zwischen beispielsweise einem Ein-Kern-System und einem Multi-Kern-System von so grundlegender Bedeutung, dass er einer theoretischen Analyse zugänglich ist. Wir beschäftigen uns hier konkret mit der Frage, wie sich parallele Systeme modellieren lassen und welche Probleme sie prinzipiell schneller lösen können als Ein-Kern-Rechner. Allgemeiner reicht das Spektrum der in der Theorie untersuchten Maschinenmodellen von der klassischen Von-Neumann-Architektur über logische Schaltkreise und Turing-Maschinen bis zu „exotischen“ Berechnungsmodellen wie DNA-Computern oder Quantenrechnern. Die Untersuchung dieser Architekturen zeigt Chancen, aber auch Grenzen möglicher zukünftiger Rechnergenerationen auf.
Das Ziel der (algorithmischen) Komplexitätstheorie ist zu verstehen, wie „schwierig“ konkrete Probleme sind. Im Idealfall erreicht man eine exakte Klassifikation des Problems anhand sogenannter Komplexitätsklassen (hiervon sind die Klassen P und NP aus dem berühmten P-NP-Problem nur die prominentesten Beispiele). Eine solche Klassifikation ist unerlässlich um zu entscheiden, ob ein konkreter Lösungsalgorithmus bereits ideal ist oder noch Verbesserungspotential birgt. Unser Hauptinteresse im Bereich der Komplexitätstheorie gilt den kleinen Platzklassen und der Klassifikation von Problemen auf Graphen, mit welchen sich solch unterschiedliche Dinge wie Straßennetze, biologische Netzwerke oder das Internet modellieren lassen, sowie der average-case-Zeitkomplexität.
In den Life Sciences, insbesondere in der Medizin und der Biologie, wächst die jährlich neu gewonnen Datenmengen rapide an – benötigte die erste Entschlüsselung eines menschlichen Genoms noch Jahre, ist dies mittlerweile in wenigen Tagen möglich –, weshalb eine geeignete Algorithmik unerlässlich ist, um mit diesen wertvollen Daten zu arbeiten. Unsere Forschung auf diesem Gebiet hat das Ziel, die speziellen bioinformatorischen Probleme mit den Methoden der Theoretischen Informatik zu analysieren und spezielle algorithmische Verfahren zu entwickeln. Wir untersuchen, wie schnell sich prinzipiell menschliche Genome aufgrund unvollständiger Daten rekonstruieren lassen. Betreffend Modellierungen interessiert uns das menschliche Immunsystem; unser Ziel ist es, durch Modellbildungen und agentenbasierten Simulationen quantitative Vorhersagen über immunologische Prozesse zu machen.
Wir beschäftigen uns mit Methoden, die Speicherung und den Austausch von Information gegen Ausspähen oder Verändern durch dritte Personen zu schützen sowie IT-Systeme – einzelne Rechner bis komplette Netzwerke – gegen unautorisierte Zugriffe und andere externe Angriffe zu sichern. Um digitale Dokumente durch digitale Siegel oder Wasserzeichen gegen Manipulation oder Urheberrechtsverletzungen zu schützt, entwickeln und analysieren wir mathematisch fundierte kryptologische Verfahren, auf deren Grundlage sich dann komplexere Protokolle entwerfen lassen. Aktuell gilt unser besonderes Interesse der Steganographie, der heimlichen Übermittlung von Nachrichten durch Einbettung in unverfänglich aussehende digitale Dokumente.
Beim Algorithmischen Lernen versucht man mit intelligenten Klassifikationsverfahren aus einer Sequenz von Datensätzen weiterreichende Information zu gewinnen. Wir beschäftigen uns mit dem Lernen von Konzeptklassen und Netzwerken, die funktionale Abhängigkeiten beschreiben.
Kommunikationsnetzwerke, hoheitliche Dokumente, E-Commerce, Immunologie
