Der Kurs vermittelt einen Überblick der Theoretischen Informatik, sowie eine Einführung in die Welt der Informatik im Allgemeinen. Insbesondere werden dabei die folgenden Themen abgedeckt:
- Grundlegende Konzepte wie Graphen, Bäume, Verbände, verschiedene Arten der vollständigen Induktion, Hüllenbildung.
- Der Begriff des Algorithmus, (Nicht-) Determinismus, partielle und totale Korrektheit, Invarianten.
- Klassifikation und Beschreibung formaler Sprachen, die Chomsky-Hierarchie, endliche Automaten, Grammatiken.
- Aussagen- und Prädikatenlogik, Syntax und Semantik, der Begriff des Kalküls.
- (Nicht-)Berechenbarkeit von Funktionen, grundlegende Berechnungsmodelle, das Halteproblem.
- Komplexität von Problemen und Algorithmen, O-Notation, die Klassen P und NP.
Der Kurs enthält außerdem eine Einführung zum Textverarbeitungssystem LaTeX.
