inf401 - Foundations of Theoretical Computer Science (Course overview)
Department of Computing Science |
6 KP |
|
Module components |
Semester courses Wintersemester 2021/2022 |
Examination |
Lecture
|
|
|
Exercises
|
|
|
Hinweise zum Modul |
Prüfungszeiten |
At the end of the lecture period |
Module examination |
Written or oral exam |
Skills to be acquired in this module |
Introduction to the theory of automata, formal languages, computability, and complexity Professional competenceThe students: - Know different classes of languages (e.g. regular and context-free languages)
- Know automata models corresponding to the respective language classes (e.g. finite automata, pushdown automata, Turing machines)
- Construct automata, Turing machines, and grammars for given tasks
- Know equivalent formalisations of the concept of algorithm
- Classify functions as algorithmically computable and problems as algorithmically decidable
- Know and recognize undecidable problems
- Evaluate the complexity of algorithms
- Know problems that are solvable deterministically or nondeterministically in polynomial time
Methodological competenceThe students: - Learn about the power of abstract models of computation
Social competenceThe students: - Work together in small groups to solve problems
- Present solutions to problems to groups of other students
Self-competenceThe students: - Learn persistence in pursuing difficult tasks
- Learn precision in writing down solutions
|
|