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.
