Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-82-59-M-2

Foundations of Theoretical Computer Science (M, 6.0 LP)

Module Identification

Module Number Module Name CP (Effort)
INF-82-59-M-2 Foundations of Theoretical Computer Science 6.0 CP (180 h)


CP, Effort 6.0 CP = 180 h
Position of the semester 1 Sem. in SuSe
Level [2] Bachelor (Fundamentals)
Language [DE] German
Module Manager
Area of study [INF-LA] Teacher Education
Reference course of study [INF-31.79-SG] B.Ed. LaGR Computer Science
Livecycle-State [NORM] Active


Type/SWS Course Number Title Choice in
Presence-Time /
SL SL is
required for exa.
PL CP Sem.
3V+2U INF-02-04-K-2
Formal Languages and Computability
P 70 h 110 h
ja PL1 6.0 SuSe
  • About [INF-02-04-K-2]: Title: "Formal Languages and Computability"; Presence-Time: 70 h; Self-Study: 110 h
  • About [INF-02-04-K-2]: The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.
    • It is a prerequisite for the examination for PL1.

Examination achievement PL1

  • Form of examination: written exam (Klausur) (90-120 Min.)
  • Examination Frequency: each summer semester
  • Examination number: 60205 ("Logic and Semantics of Programming Languages")

Evaluation of grades

The grade of the module examination is also the module grade.


  • Formal languages for the description of computer systems (including grammars as generators of languages, automata as acceptors of languages, logic calculus)
  • Grammars and models of automata (finite automata, cellar automata, Turing machines)
  • Chomsky Hierarchy
  • Algorithm definition
  • Computability and its limits, decidability, complexity, NP-complete problems, computability and complexity classes
  • Correctness of programs

Competencies / intended learning achievements

The students
  • have an understanding of the basic questions of computer science;
  • know automata and formal languages and their interrelationships;
  • know procedures for the evaluation of computability and decidability;
  • know measures of complexity and methods for coping with complexity;
  • can apply mathematical methods to clarify fundamental questions of computer science.


  • Sperschneider, Hammer: Theoretische Informatik — Eine problemorientierte Einführung, Springer, 1996.
  • Hopcroft, Motwani, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison Wesley, Pearson Studium, 2002.

Requirements for attendance of the module (informal)


Requirements for attendance of the module (formal)


References to Module / Module Number [INF-82-59-M-2]

Course of Study Section Choice/Obligation
[INF-31.79-SG] B.Ed. LaGR Computer Science [Compulsory Modules] Further modules [P] Compulsory
[INF-B4.79-SG] ZEP LaG Computer Science [Compulsory Modules] Certificate course of studies [P] Compulsory