Skip to main content

Module description - Introduction to Theoretical Computer Science
(Einführung in die Theoretische Informatik)

ECTS 3.0
Level intermediate
Overview The module introduces the fundamental ideas and problems of the theoretical foundations of computer science.

    Formal Languages:
  • Repetition: Languages, decision problems, grammars, Chomsky hierarchy
  • Finite automata and regular languages, (DFA, NFA and minimal DFA), pumping lemma, proposition of Myhill and Nerode
  • Regular expressions
  • Context-free languages

    Theory of computation:
  • Models of computation (Turing machines, recursive functions, loop-, while- und goto-programs)
  • Church-Turing thesis
  • Decidability and recursive enumerability
  • Universal Turing machines
  • Undecidability

  • Reduction
  • Rice’s theorem

  • Complexity classes
  • Polynomial reduction
  • Problems in P and NP

(The order and emphasis of the topics are left to the lecturers.)
Learning objectives
  • Formal Languages:
  • are able to describe languages with grammars, understand the Chomsky hierarchy and are able to classify languages according to this hierarchy;
  • know the properties of regular languages and are able to transform a regular expression to a non-deterministic automaton as well as to a minimal deterministic automaton;
  • can, in simple cases, apply the pumping lemma and the proposition of Myhill and Nerode to recognize that a language is not regular;
  • are able to bring a context-free grammar to Chomsky normal form and decide the word problem with the Cocke-Younger-Kasami-algorithm.

  • Theory of computation:
  • know some important models of computation and are able to explain the Church-Turing thesis.
  • know the notions of decidability and recursive enumerability and understand the concept of a universal Turing machine;
  • can explain what an undecidable language is and know some important examples;
  • know the notion of reduction, are able to do reductions in simple cases and to explain the Theorem of Rice.

  • Complexity:
  • can explain what a complexity class is and know some examples;
  • are aware of the importance of the classes P and NP, know important problems in these classes and understand polynomial reduction.

Previous knowledge
  • Module Mathematics for Computer Science (mgli),
  • English level B2 (e.g. passed Module ten1)

Exam format Continuous assessment grade
Diese Seite teilen: