50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Forschungsschwerpunkte


Schwerpunkte

Mission

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.

Zentrale Forschungsgebiete

  1. Algorithmik

    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.

    Weitere uns interessierende Aspekte sind die Fehlertoleranz algorithmischer Verfahren und das Lösen von Optimierungsproblemen bei beschränkter Information, die Online-Problematik, beispielsweise die verzögerungsfreie Erfüllung von Requests, die sukzessive eintreffen (Server- und Scheduling-Probleme). Schließlich untersuchen wir im Teilgebiet Algorithmische Spieltheorie die globalen Auswirkungen eigennütziger Entscheidungen mehrerer Akteure, etwa bei elektronischen Auktionen oder Auslastung von Netzwerken.

  2. Maschinen- und Berechnungsmodelle

    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.

  3. Algorithmische Komplexität

    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.

  4. Bioinformatik

    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.

  5. IT-Sicherheit

    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.

  6. Data-Mining

    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.

  7. Kompetenzen

    • Komplexitätsanalysen von Berechnungsproblemen
    • Entwurf und Analyse algorithmischer Strategien
    • Entwurf und Analyse von Datenstrukturen
    • Entwurf und Analyse sicherer Kommunikationsprotokolle
    • Signierung digitaler Dokumente
    • Didaktik der Algorithmik
    • Typographie und Satzsysteme
  8. Anwendungsgebiete

    Kommunikationsnetzwerke, hoheitliche Dokumente, E-Commerce, Immunologie