Module 11787 

Please complete the registration for the module on Moodle by 5 October 2026; see below

• First lecture: Tuesday 6 October 2026
• First tutorial: Wednesday 7 October 2026
• Information on module enrolment and deregistration
• Online-Portal for module enrolment and deregistration
• In addition to the official module registration with Student Services,
  please also register on the BTU learning platform Moodle(registration without a password).
  There you will find additional materials, in particular relating to the tutorials.
  Up-to-date information is also usually sent via Moodle.
• Homework assignments will be given throughout the semester, and successful completion of these assignments is a prerequisite for being admitted to the exam. It is expected that 12 homework assignments will be given, of which 9 are expected to be required for passing. Specific details will be provided throughout the semester.
• Rules for students repeating courses: Previous work completed in earlier semesters no longer counts. The work must therefore be completed again. This does not apply to students who wish to improve the grade they have already achieved in an exam.

The lecture does not follow a textbook or lecture notes exclusively.
The following references should be regarded as supplementary sources, enabling students to explore the topics covered in the lecture in greater depth and, in some cases, from an alternative perspective.  

• Alexander Asteroth, Christel Baier:
  Theoretical Computer Science: An Introduction to Computability, Complexity and Formal Languages,
  Pearson Studium 2002.

• Katrin Erk, Lutz Priese: Theoretical Computer Science – A Comprehensive Introduction,
  eXamen.press, 2008. [available to read online on campus]

• Dirk W. Hoffmann: Theoretical Computer Science, Hanser, 2009.

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman:
  An Introduction to Automata Theory, Formal Languages and Computability, 3rd,
  updated edition, Pearson Studium 2011.

• Juraj Hromkovic: Theoretical Computer Science: Formal Languages, Computability, Complexity Theory, Algorithms, Communication and Cryptography, Teubner, 2007. [available to read online on the Campus platform]

• Dexter C. Kozen: Automata and Computability, Springer 1997.

• Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1981.

• John E. Savage: Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998.
  [Available electronically on the website of Prof. John Savage, Department of Computer Science, Brown University]

• Michael Sipser: *Introduction to the Theory of Computation*, 3rd edition, Cengage Learning, 2013.