de | en

Introduction to Theory of Computation

Module IN0011

This Module is offered by TUM Department of Informatics.

This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.

Basic Information

IN0011 is a semester module in German language at Bachelor’s level which is offered in summer semester.

Total workloadContact hoursCredits (ECTS)
240 h 90 h 8 CP

Content, Learning Outcome and Preconditions

Content

Formal languages, grammars, Chomsky hierarchy.

Regular languages: DFA, NFA with and without ε-transitions, regular expressions and translations between them; systems of language equations; closure under boolean operations; Arden’s lemma; pumping lemma; decision problems; minimization; Myhill-Nerode theorem.

CFLs: PDAs and translation between CFGs and PDAs; proof that DPDAs are weaker than PDAs; closure properties; CYK algorithm; pumping lemma; Chomsky and Greibach normal forms.

Context-sensitive languages and LBAs.

Computability: computability, decidability, semi-decidability, recursive-enumerability and their relationships; existence of non-computable problems; Turing machines, accepted languages, type-0 languages: equivalence of Turig machines, While-programs and Goto-programs; primitive and µ-recursive functions; reductions between problems; the Halting problem; universal Turing machines; Rice’s theorem; Rice-Shapiro theorem; undecidability of the Post Correspondence Problem and important problems on CFGs.

Complexity theory: time and space complexity classes; polynomial-time reductions; the classes P and NP; NP-completeness; Cook’s theorem; important NP-complete problems and reductions between them.

All proofs are covered.

Learning Outcome

After successfully completing this module, the students understand the core concepts of the theory of computation on a basic but scientific level. They know what regular expressions, contextfree grammars, the Chomsky hierarchy, finite automata and Turing machines are. They can define formal languages with the appropriate grammars or machines. They can prove that a given language cannot be defined with a given class of grammars or machines. They can prove that certain grammars and machines are equivalent and they can transform them into each other algorithmically. They can explain the basic concepts of complexity theory and can reduce decision problems algorithmically to each other under given complexity limitations.

Preconditions

IN0015 Discrete Structures, MA0901 Linear Algebra for Informatics, MA0902 Analysis for Informatics

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

TypeSWSTitleLecturer(s)DatesLinks
VO 4 Introduction to Theory of Computation (IN0011) Esparza Estaun, F. Mon, 14:00–16:00, MW 2001
Thu, 14:15–16:00, MW 2001
Mon, 13:00–14:00, MW 2001
UE 2 Introduction to Theory of Computation, Exercise Session (IN0011) Czerner, P. Helfrich, M. dates in groups

Learning and Teaching Methods

The module consists of lectures and exercises. In the lectures, the material is presented by the teacher, in dialogue with the students. During the exercises, the students work on given exercises either individually or in small groups with help from the supervisors. Exercises and homework are primarily pen and paper based but can also involve computer-based components.

Media

Lecture notes, slides, blackboard, animations, video recordings, online exercises and homework assignments, online discussion forum

Literature

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation
Dexter Kozen. Automata and Computability
Katrin Erk, Lutz Priese. Theoretische Informatik. Eine umfassende Einführung.
Uwe Schöning. Theoretische Informatik kurzgefasst.

Module Exam

Description of exams and course work

The exam takes the form of a 180 minutes written test. Knowledge questions allow to assess acquaintance with concepts of Theoretical Informatics, algorithmic questions assess the ability to apply known algorithms to concrete problems or to design small new algorithms, and deductive questions assess the ability to reason logically about the concepts of the course.

Exam Repetition

The exam may be repeated at the end of the semester.

Current exam dates

Currently TUMonline lists the following exam dates. In addition to the general information above please refer to the current information given during the course.

Title
TimeLocationInfoRegistration
Introduction to Theory of Computation
Tue, 2022-10-04, 11:15 till 14:15 2502
1450
004
0001
2001
till 2022-09-26 (cancelation of registration till 2022-09-27)
Top of page