inf401 - Foundations of Theoretical Computer Science (Course overview)
| Department of Computing Science |
6 KP |
|
| Module components |
Semester courses Wintersemester 2021/2022 |
Examination |
|
Lecture
|
|
|
|
Exercises
|
|
|
|
Notes for the module |
| Time of examination |
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
|
|
