Introduction to the Theory of Computation

11B0416

Bachelor

German

5.0

winter and summer term

1 semester

Theoretical computer science forms a very important basis for computer science studies in terms of terminology, considerations and conclusions, and is regarded as a core subject. It covers the fundamentals of automata theory, formal languages and computability. 

Introduction to formal languages and automata based on the language classes of the Chomsky hierarchy

1. Finite automata and regular expressions

2. Pigeonhole automata and context-free grammars

3. Linear-bounded automata and context-sensitive grammars

4. Turing machines and unrestricted grammars

5. Computability & complexity theory

The total workload for the module is 150 hours (see also "ECTS credit points and grading").

The event will be conducted according to the inverted classroom model or as a traditional lecture. 

• oral exam or
• Written examination or
• Written examination and Multiple choise written examination

Oral examination: see General Section of the Examination Regulations;

Written examination: see the applicable Study Regulations;

Written examination and multiple-choice procedure: see the applicable Study Regulations.

Students should have a solid foundation in computer science from their first semesters. This includes, in particular, a sound knowledge of formal mathematics, such as set theory, relations, functions, proof techniques and basic combinatorics. Good programming skills and an understanding of algorithms and data structures are also important, as many concepts of computability and complexity are based on these. Experience with formal descriptions is also helpful, as is the ability to understand abstract models such as automata or Turing machines. A certain enjoyment of formal precision, logical thinking and abstract modelling supports successful learning in this module.

Students gain a comprehensive overview of the fundamental concepts and theories of theoretical computer science. They become familiar with the different classes of automata and grammars, as well as the basics of computability and complexity theory. This knowledge forms the basis for a deeper understanding of computer science as a science capable of abstraction.

Students specialise in the detailed analysis of core topics in theoretical computer science. These include understanding the Chomsky hierarchy, the structure and functioning of different types of automata, and the basic principles of computability and complexity theory. The aim is to develop a deep understanding of these concepts.

Students should not only accumulate knowledge, but also understand its application and significance in computer science. This includes recognising connections between theoretical principles and their practical application in the development of algorithms, the analysis of languages and the solution of complex problems.

Students learn to apply their acquired theoretical knowledge to practical problems. This includes the ability to select and adapt suitable theoretical models for solving problems in computer science. They should be able to use theoretical concepts for the analysis, evaluation and development of algorithms and software systems. 

Students are encouraged to think beyond the existing state of knowledge and develop their own research approaches. This includes the ability to critically question existing theories, formulate new hypotheses, and develop innovative solutions to theoretical and practical problems in computer science.

Students develop communication and teamwork skills. They learn to communicate complex theoretical content in an understandable way. Cooperative work on projects also promotes teamwork skills and the exchange of ideas.

Students develop an awareness of the importance and responsibility of theoretical computer science within science and society. This includes reflection on ethical aspects in research and application of computer science, as well as recognition of the role of theoretical computer science as a basis for innovation in technology.

• Morisse, Karsten

• Morisse, Karsten
• Kleuker, Stephan