Theoretical Computer Science

Takes place in FSS2019

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.

  • Lecture

    Please note:

    • 01.06.2019: The final version of the lecture slides is now available for download (see below). A list of changes to the last pre-releases can be found at hier.
    • 31.05.2019: The dates for the oral examinations can be found at here.
    • 29.04.2019: The oral tests will be held on Monday 17.06.2019 and Thursday 11.07.2019. Please register with Alexander Moch with your desired date.
    • 21.02.2019: The website for the exercises can be found here.
    • 05.02.2019: The lecture starts on Monday, 11.02.2019.

    Aktuelles Material zur Vorlesung



    • Wegener, Ingo: Theoretische Informatik - eine algorithmen­orientierte Einführung, Teubner Verlag, 2005.

    Reference works and further literature

    • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010.
  • Practice

    • On Mondays or Wednesdays (alternating with the corresponding lecture) in room B 6, A 1.01 (Alexander Moch)

    Please note:

    • 31.05.2019: The dates for the oral examinations can be found here.
    • 31.05.2019: An error occurred at task 5.5. With a deterministic cellar automat, as it was defined in the lecture, this task cannot be solved. Therefore, the task was changed to require a non-deterministic cellar automat.
    • 29.04.2019: The oral examinations will take place on Monday, 17.06.2019 and Thursday, 11.07.2019. Please register with Alexander Moch with your desired date.
    • 21.02.2019: The first exercise will take place on Wednesday, 27.02.2019.