| Kurzkommentar |
This block course treats the same topics as the lecture 'Theoretische Informatik' from our Bachelor program where it has to be taught in German. Examinations come in two flavors
- normal: for a certificate (Schein) for the Bachelor program.
- somewhat harder: for a certificate as a special lecture in the graduate program.
If one has used the certificate for the Bachelor degree, one cannot use the certificate as a special lecture in the graduate program.
Time:
Lectures: Monday to Thursday 10:00 to 12:00 in the 6 weeks from
February 17 to March 27 2014
Exercises: twice per week
Contents:
1. Formal languages
- regular languages and finite automata, pumping lemma
- context free languages and pushdown automata, pumping lemma
2. Computability
- Recursive functions
- Turing machines
- Churchs thesis
- Undecidability of the Halting problem
- Recursion Theorem
3. Logics
- Elementary arithmetic
- Goedels incompleteness theorems
4. Complexity Theory
- Turing Machine Complexity Classes
- Hierarchy Theorems
- NP-completeness
- Speedup and Gap theorem
- Kolmogorov complexity
- More on separation of complexity classes |
