Theoretical Computer Science

CS 406 Theoretische Informatik

Spring Semester 2023 | German

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.


There will be six tutorials. Time slots and rooms are the same as for the lectures.

  • Monday, 06.03.2023
  • Wednesday, 15.03.2023
  • Wednesday, 29.03.2023
  • Wednesday 19.04.2023
  • Wednesday, 26.04.2023
  • Monday  08.05.2023

Important: There will be no tutorials on 15.05. and 24.05. The alternative dates can be found above.

Any changes will be posted on this side and communicated via ILIAS.


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.


Conntact via email to linda.scheu-hachtel