Module Theoretical Computer Science, Media and Communication Computer Science (Bachelor) (ER 3)

English language
Compact font

Color scheme

Module summary

Theoretical Computer Science

MKIB1303

Prof. Dr. Heiko Körner

/

1st Semester

none

none

Participants of this lecture will be in a position to recognize the fundamental limitations of today's computers when solving important problems. Hence, this course gives an intoduction to the basic areas of modern theoretical computer science. The Chomsky hierarchy helps the students to classify formal languages by their algorithmic complexity. Furthermore, the students use computational models (finite state automata, push-down automata) to represent today's computers and to understand their limits. Due to these limitations, several problems are shown to be unsolveable. Proving all these results requires precise mathematical and logical arguments, and the students are intensively trained to use them correctly.

Individual exams
Course Theoretical Computer Science

MKIB1313

Lecture

Prof. Dr. Heiko Körner

German

4/4

120 hours in total, including 60 hours of contact study.

Written Exam 90 Min. (graded)

This course gives an introduction to the theory of formal languages. The Chomsky hierarchy will serve as a model to classify these languages by their computational complexity. Modern computers are represented by finite state automatons, showing theier principal limits. The students also learn how to apply several proof techniques.

The lecture include the following areas of theoretical computer science: mathematical logic, formal languages, proof techniques, the O-calculus, finite automata, regular languages and expressions, the Chomsky hierarchy, the pumping lemma for regular and context-free languages and the minimization of finite automata by the theorem of Myhill-Nerode. Furthermore, the course covers pushdown automata, the CYK algorithm and closure properties of regular and context-free languages.

The substance of the lecture will be discussed at the blackboard. Lecture notes containing the complete material are also available. Furthermore, there are sample solutions to all exercises.

Literature: D. W. Hoffmann: Theoretische Informatik, 3. Auflage. Hanser, 2015.

M. Sipser: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, Inc., 2012.

This course will take place as a pure lecture. Numerous exercises deepen selected areas and will be discussed in tutorials.