Grundkurs Theoretische Informatik

Theoretical Computer Science – the Lecture Companion. Computability, formal languages, algorithms, and complexity theory are theoretical topics with practical relevance, and there are also practical approaches to them. Look forward to a modern didactics that connects strict formalism with your intuition, is designed to be learner-friendly, and ultimately presents application fields of computer science for each topic. Stefan Neubert not only enjoys theoretical computer science himself but also passionately dedicates himself to teaching it at the beginning and throughout the bachelor's program. An introduction with many exercises and examples, also suitable for self-study.

Contents:

Basic mathematical notation
Models and limits of computability
Formal languages: Finite automata, context-free grammars, pumping lemmas, and more
Proof methods for the correctness and runtime of algorithms
Paradigms for algorithm design
Amortized analysis and lower bounds for runtimes
NP-completeness and reduction.