• 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.

Contents

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