inf401 - Foundations of Theoretical Computer Science (Complete module description)
Module label | Foundations of Theoretical Computer Science |
Module code | inf401 |
Credit points | 6.0 KP |
Workload | 180 h |
Institute directory | Department of Computing Science |
Applicability of the module |
|
Responsible persons |
|
Prerequisites | |
Skills to be acquired in this module | Introduction to the theory of automata, formal languages, computability, and complexity
Methodological competence
Social competence
Self-competence
|
Module contents | In the first part of the course, different classes of languages are introduced (regular and context-free languages). For each class a matching automata model is presented (finite automata, pushdown automata). Various properties are proven for the introduced classes of languages and models of automata. In the second part of the course, we examine which functions are computable and which problems are decidable. To this end, the concept of algorithm is formalised. Turing machines and grammars turn out as equivalent approaches. We show that there are problems that are undecidable. Many of these problems are of practical interest. The third part of the course deals with the complexity of algorithms, i.e. how much time and space is required to solve a problem. In particular, we consider problems that are solvable in polynomial time, either deterministically or non-deterministically. These problems are classified as P and NP. |
Recommended reading | Essential:
Recommended:
Good secondary literature:
|
Links | |
Language of instruction | German |
Duration (semesters) | 1 Semester |
Module frequency | annual |
Module capacity | unlimited |
Teaching/Learning method | V+Ü |
Previous knowledge | Useful prerequisites: set theory, functions, relations, propositional and predicate logic |
Type of course | Comment | SWS | Frequency | Workload of compulsory attendance |
---|---|---|---|---|
Lecture | 3 | WiSe | 42 | |
Exercises | 1 | WiSe | 14 | |
Total module attendance time | 56 h |
Examination | Prüfungszeiten | Type of examination |
---|---|---|
Final exam of module | At the end of the lecture period |
Written or oral exam |