Theoretische Informatik

Theoretische Informatik

Die Theoretische Informatik beschäftigt sich mit den theoretischen Grundlagen der Informatik. Zwei Kerngebiete sind die Komplexitätstheorie und die Algorithmik. Forschende im Bereich der Komplexitätstheorie stellen sich die Frage, welche Probleme sich wie effizient lösen lassen. Basierend auf einem formalen Rechenmodell ergeben sich dabei Klassen von Problemen verschiedener Komplexität. Die Komplexitätstheorie untersucht, wie sich diese Klassen zueinander verhalten.

In der Algorithmik werden Methoden zum Entwurf und der Analyse effizienter Algorithmen betrachtet. Die beiden Gebiete, Algorithmen und Komplexität, hängen eng miteinander zusammen. Auch sind Algorithmen eng verknüpft mit Datenstrukturen, da manche effizienten Algorithmen geschickte Datenstrukturen benötigen. Datenstrukturen hingegen benötigen geschickte Algorithmen zur Konstruktion, Modifikation und Abfrage.

Herausforderungen

Viele Probleme haben eine geometrische Komponente, z.B. die Abfrage numerischer Daten in einer Datenbank oder die Suche nach einem kürzesten Weg. Algorithmen für solche Probleme nennt man auch kurz geometrische Algorithmen. Diese nutzen, neben allgemeinen Techniken für effiziente Algorithmen, auch Techniken basierend auf den geometrischen Eigenschaften des Problems. Viele der Fragen, die betrachtet werden, sind motiviert aus Anwendungen. Umso komplexer dabei die Probleme sind, umso häufiger stellen sich diese als weniger effizient lösbar heraus. Die Herausforderung ist, hierfür dennoch nach effizienten Lösungen zu suchen.

Schwerpunkte

Der Forschungsbereich Theoretische Informatik rund um Prof. Dr. Maike Buchin betrachtet insbesondere geometrische Probleme auf polygonalen Kurven, geometrisch eingebetteten Graphen und einfachen Polygonen. Wie diese miteinander verglichen, zusammengefasst oder in homogene Teile zerlegt werden können, ist unter anderem Gegenstand der Forschung.

Vergleich Geometrischer Objekte: Eine fundamentale Frage ist es, die Ähnlichkeit zwischen geometrischen Objekten, z.B. Punktmengen, Polygonkurven oder triangulierten Flächen zu bestimmen. Hierfür existieren unterschiedliche Ähnlichkeitsmaße, deren effiziente Berechnung von der Komplexität des Maßes und der Objekte abhängt.

Analyse von Bewegungsdaten:  Heutzutage treten Bewegungsdaten, also diskrete Sample einer kontinuierlichen Bewegung, in immer größeren Mengen auf. Geometrisch sind diese Daten Polygonkurven in Zeit und Raum, wobei diese in der Regel fehlerbelastet und eingebettet in eine Umgebung sind. Diese zu analysieren erfordert geeignete effiziente Algorithmen.

Analyse von geometrischen Netzwerken: Netzwerke, z.B. Fluss- oder Straßennetzwerke, treten in vielen Kontexten auf. In deren Analyse stellen sich unterschiedliche Fragen, zum Beispiel, wie man die Qualität verschiedener Netzwerke vergleicht oder basierend auf einer großen Menge an Bewegungsdaten auf einem Netzwerk selbiges rekonstruiert. Auch hier variiert die algorithmische Komplexität der resultierenden Probleme stark.