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)

Basedata

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

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
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
U-Schein
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.


Contents

  • 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.

Literature

  • 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)

Courses

Requirements for attendance of the module (formal)

None

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