Theoretical Computer Science

The lecture provides an algorithm-oriented introduction to central areas of theoretical computer science such as basic computational models and mutual simulations, decidability, complexity theory (definition and structure of basic complexity classes, reducibility, NP-completeness), information theory and cryptography, automata theory, basics of programming languages and syntax analysis.

The lecture will take place weekly on

• Monday, 15:30 – 17:00 in C012
• Wednesday, 13:45 – 15:15 in C014

The first lecture takes place on Monday, 06.02.2023, 15:30 – 17:00 in C012.

Six of the lectures will be replaced by tutorials, see the next section.

Important: The lecture on Wednesday, 19.04.23, will be postponed on Thursday, 20.04.23, 10:15–11:45 in B6, 26 A1.01.

The lecture slides as well as the exercise sheets and their corresponding solutions are available in the lecture's ILIAS course.

• Wegener, Ingo: Theoretische Informatik – eine algorithmenorientierte Einführung, Teubner Verlag, 2005.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung, Oldenbourg, 2010.