In der theoretischen Informatik befassen wir uns mit grundlegenden Fragen, die den Computer betreffen:
- Wie können wir Programme und algorithmische Problemstellungen formal beschreiben?
- Gibt es Probleme, die kein Computer jemals lösen kann?
- Sind alle Computer(-modelle) mehr oder weniger gleich? Oder gibt es wesentliche Unterschiede?
- Wenn man einem Computer mehr Zeit (oder Platz) gibt, kann er dann mehr Probleme lösen als vorher?
Um diese Fragen zu beantworten, vereinfachen wir den komplexen Begriff eines Computers und betrachten zunächst nur sehr einfache Programmiersprachen. Auf diesen bauen wir dann weitere Abstraktionen, um die Funktionalität moderner Programmiersprachen zu imitieren, und dennoch die einfachen Regeln zur Beweisführung annehmen zu können. In diesem Kontext lernen wir zeitgleich formal korrektes Arbeiten, mathematische Denkweisen und sauberes Führen von Beweisen. Auf dem Programm stehen:
- WHILE-Programmierung
- das Halteproblem und Nichtentscheidbarkeit
- Reduktionen
- die Arithmetische Hierarchie
Zudem geben wir eine Einführung in die Algorithmik. Wir entwerfen effiziente Algorithmen für bekannte Probleme und beweisen dabei auch deren Laufzeit und Korrektheit. Dabei lernen wir verschiedene Techniken zur Problemlösung kennen. Darunter fallen insbesondere:
- Greedy-Algorithmen
- Divide and Conquer
- Dynamische Programmierung
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.
