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" weg und betrachten nur sehr einfache Programmiersprachen. In dem Kontext lernen wir zeitgleich formal korrektes Arbeiten, mathematische Denkweisen und saubere Beweisführung. Auf dem Programm stehen
- Landau bzw. O-Notation
- WHILE-Programmierung, Turing Maschinen und Endliche Automaten
- Das Halteproblem und Nichtentscheidbarkeit
- P vs. NP
- Zeit vs. Platzkomplexität
Auf der anderen Seite 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 ist der schnellste Algorithmus, 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.
