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, Chomsky hierarchy Elementary automata theory Decidability Basic complexity theory

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

ArtSWSTitelDozent(en)Termine
VO 4 Einführung in die Theoretische Informatik (IN0011) Montag, 09:00–11:00
Donnerstag, 14:00–16:00
Donnerstag, 16:00–17:00
UE 2 Tutorübungen zu Einführung in die Theoretische Informatik (IN0011) Termine in Gruppen

Learning and Teaching Methods

The module consists of lectures and tutorials. In the lectures, the material is presented by the teacher, in dialogue with the students. During the tutorials, the students work on given exercises either individually or in small groups with help from the tutors. 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 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

There is a possibility to take the exam 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
Einführung in die Theoretische Informatik
Di, 27.9.2016, 15:30 bis 18:30 00.02.001
MI: 00.02.001
MW: 2001
00.04.011
MI: 00.04.011
bis 19.9.2016 (Abmeldung bis 20.9.2016)

Condensed Matter

When atoms interact things can get interesting. Fundamental research on the underlying properties of materials and nanostructures and exploration of the potential they provide for applications.

Nuclei, Particles, Astrophysics

A journey of discovery to understanding our world at the subatomic scale, from the nuclei inside atoms down to the most elementary building blocks of matter. Are you ready for the adventure?

Biophysics

Biological systems, from proteins to living cells and organisms, obey physical principles. Our research groups in biophysics shape one of Germany's largest scientific clusters in this area.