inf401 - Foundations of Theoretical Computer Science (Course overview)

inf401 - Foundations of Theoretical Computer Science (Course overview)

Department of Computing Science 6 KP
Module components Semester courses Winter semester 2023/2024 Examination
Lecture
Exercises
Notes on the module
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 competence
The 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
  • know the relevance of NP-complete problem 

Methodological competence
The students:

  • learn about the power of abstract models of computation
  • know problems which are not efficiently solvable and can detect these in practical tasks

Social competence
The students:

  • work together in small groups to solve problems
  • present solutions to problems to groups of other students

Self-competence
The students:

  • learn persistence in pursuing difficult tasks
  • learn precision in writing down solutions