Modul

The assessment of the module consists of a written examination according to §4(2), 1 of the examination regulations. The grade of the module corresponds to the grade of the written examination. Further details see the german section.

The student

• has a deeper insight into the fundamentals of theoretical computer science and knows the computation models and proof techniques,
• understands the limits and possibilities of computer science in relation to the solution of definable but only partially predictable problems
• knows basic aspects of computer science in contrast to specific circumstances, such as specific computers or programming languages and also can phrase general statements about the solvability of problems
• is able to apply the proof techniques learned for the specification of systems of computer science and for the systematic design of programs and algorithms

There are important problems whose solutions can clearly be defined but one will never be able to calculate such a solution systematically. Other problems are "likely" to be solved only through trial and error. Other topics of the module provide the basis for circuit design, design of compilers, and many others. Most results are rigorously proved. The proof techniques learned by the way are important for the specification of systems of computer science and for the systematic design of programs and algorithms.

The module provides a deep insight into the principles and methods of theoretical computer science. In particular, this will be discussed on the basic properties of Formal Languages as foundations of programming languages and communication protocols (regular, context-free Chomsky hierarchy), machine models (finite automata, pushdown automata, Turing machines, non determinism, and relations to families of formal languages), equivalence of sufficiently powerful computation models (Church's thesis), non computable important functions (halting problem,...), Gödel's incompleteness theorem and introduction to complexity theory, NP-complete problems and polynomial reductions.

approx. 210 h