Themen des Lehrstuhls Theoretische Informatik/Formale Sprachen

Die Theoretische Informatik behandelt die mathematischen Grundlagen und formale Methoden der Informatik. Wie der Name des Lehrstuhls andeutet, spielen die Formalen Sprachen dabei eine zentrale Rolle.

Zentrale Begriffe der Theoretischen Informatik:

• Formale Sprachen sind ein grundlegendes Mittel der theoretischen Informatik um Problemstellungen zu Formalisieren. Sie ermöglichen eine struktusierte und lineorisierte Darstellung von Daten. Anwendungen in der Praxis sind beispielsweise im Compilerbau zu finden. Bekannte Beispiele für Formale Sprachen, die in der Praxis auftauchen, sind Programmiersprachen oder auch HTML und XML.
• Die Berechenbarkeitstheorie beschäftigt sich aus mathematischer Sicht mit der Idee der Berechnung, oder auch des Algorithmus. Verschiedene Modelle zur Fassung der Idee der Berechnung werden betrachtet und deren Möglichkeiten erforscht.
• Komplexitätstheorie: Neben der Frage, wie ein Problem algorithmisch gelöst werden kann, ist auch die Frage nach der Effizienz einer solchen algorithmischen Lösung fundamentaler Bestandteil der Informatik. Die Komplexitätstheorie beschäftigt sich mit der Frage, welchen Ressourcenaufwand die Lösung eines Problems erfordert.

Wir beschäftigen uns mit folgenden Themen:

• In der Circuit Complexity, zu Deutsch Schaltkreisproblematik, werden statt sequenzieller Maschinen Schaltkreises als Berechnungsmodell betrachtet. Auch hier lassen sich verschiedene Maße für die Komplexität eines Problems finden. Schaltkeires haben eine enge Verbindung zu parallelen Berechnungsmodellen.
• Die Allgegenwart von Computern im täglichen Leben, auch in sicherheitskritischen Bereichen wie im Auto, erfordert die Möglichkeit, Hard- und Softwaresysteme beim Entwurf auf ihre Korrektheit zu überprüfen. Ein wichtiger Ansatz dabei ist das sogenannte Model Checking. Hierbei werden Systeme durch endliche Automaten dargestellt und gegen eine durch logische Formeln beschriebene Spezifikation verifiziert.
• Kryptologie
• Parametriesierte Algorithmen

Mehr zu den einzelnen Gebieten finden Sie unter Forschung.