In der theoretischen Informatik befassen wir uns mit grundlegenden Fragen, die den Computer betreffen:
- Gibt es Probleme, die kein Computer jemals lösen kann?
- Wenn man einem Computer mehr Zeit (oder Platz) gibt, kann er dann mehr Probleme lösen als vorher?
- Sind alle Computer(-modelle) mehr oder weniger gleich? Oder gibt es wesentliche Unterschiede?
- Gibt es Probleme, die man mit sehr viel Zeit lösen kann, aber niemals effizient mit wenig Zeit?
Um diese Fragen zu beantworten, abstrahieren wir von dem komplexen Begriff eines Computers und betrachten nur sehr einfache Programmiersprachen. In diesem Kontext lernen wir zeitgleich formal korrektes Arbeiten, mathematische Denkweisen und sauberes Führen von Beweisen. Auf dem Programm stehen:
- Landau- bzw. O-Notation
- WHILE-Programmierung, Turingmaschinen und endliche Automaten
- das Halteproblem und Nichtentscheidbarkeit
- P vs. NP
- Zeit- vs. Platzkomplexität
Zudem geben wir eine Einführung in die Algorithmik. Wir entwerfen effiziente Algorithmen für bekannte Probleme und beweisen deren Laufzeit und Korrektheit. Dabei lernen wir verschiedene Techniken zur Problemlösung kennen. Darunter fallen beispielsweise:
- Graphalgorithmen (kürzeste Wege, Tiefen-/Breitensuche, Spannbäume, Flüsse etc.)
- Arrayalgorithmen (Sortieren, Suchen, Partition, Median etc.)
- Dynamische Programmierung
- Algorithmische Geometrie
Dabei sind wir darauf bedacht, eine Dualität aufzuzeigen: Auf der einen Seite fragen wir uns häufig, was der schnellste Algorithmus ist, den wir für ein Problem finden können. Auf der anderen Seite möchten wir wissen, ob es mathematisch beweisbar ist, dass es keinen schnelleren Algorithmus geben kann.
