Theoretical Computer Science

Undergraduate / Graduate Course, Ruhr University Bochum, 2022

  • Lecturer: Prof. Dr. Zeume
  • Language: German
  • Credits: 8 CP
  • Programs: B.Sc. Applied Computer Science, B.Sc. Computer Science, B.Sc. IT-Security, B.Sc./M.Sc. Mathematics
  • Examination: 100 % Written Exam (120 Minutes) + 10 % Homework / 100 % Oral Exam (30 Minutes)

Course Description

The lecture is intended for students of mathematics, computer science, applied computer science and IT security. It provides an introduction to the theory of grammars (especially context-free grammars) and automata (finite state automaton, pushdown automaton, Turing machine). It will also give an insight into computability and NP-comleteness theory, where the question is which computational problems can be solved (at all or with reasonable effort). It will be shown that there are inherently hard problems that cannot be solved satisfactorily by computers. The lecture will yiels fundamental insights into the relationship between automata and grammars and the relationship between determinism and non-determinism. By practicing techniques such as mutual simulation or (polynomially) computable reductions, the insight should mature that concepts that look different on the surface can be identical at the core. The goal is also deeper understanding of complexity. On the lower levels of the so-called Chomsky hierarchy one finds efficiently solvable application problems of text manipulation and text analysis. On the upper levels, on the other hand, one encounters the phenomenon of the inherent hardness (or even undecidability) of a problem.


Part A: Regular Languages

  1. Regular Expressions and Languages
  2. Finite Automata
  3. Equivalence of the models
  4. Minimizing automata
  5. Properties of regular languages
  6. Applications and Extensions Part B: Context-free Languages
  7. Context-Free Grammar
  8. Normal forms and proofs of correctness
  9. Pushdown automata
  10. Properties of context-free languages
  11. Membership problem and Syntax analysis Part C: Computability
  12. Turing machines
  13. Church-Turing thesis
  14. Undecidability of Halting problem
  15. Undecidable problems
  16. Further Variations and Results Part D: Computational complexity theory
  17. Polynomial Time
  18. NP and NP-Completeness
  19. First NP-complete problems
  20. Further NP-complete problems
  21. Dealing with NP-complete problems
  22. Algorithms for SAT and Exponential Time Hypothesis
  23. Random-based complexity classes