Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Theoretical Computer ScienceModule description #41282 / Version 1

← Module page Deutsche Fassung
Module / Version#41282 / #1
ValiditySince Summer semester 2026
Available language(s)English, German
Credit points6
Person responsible for the moduleNichterlein, André
GradingGraded
Exam formatWritten exam
Language(s) of instructionGerman

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34351100 FG Algorithmik und Komplexitätstheorie (AKT)

Contact

OfficeEN 23
Contact personThielcke, Christlinde
E-mail addresslehre@akt.tu-berlin.de
Websitehttps://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen

Learning outcomes

Graduates of this module have mastered fundamental concepts of theoretical computer science from the sub-areas of formal languages and automata, computability, and complexity. In particular, they understand formal languages and associated decision problems as tools of mathematical-exact formalization.
They master representations of formal languages in the form of grammars, finite automata, pushdown automata and Turing machines. They have a basic understanding of the computability of decision problems and basic complexity classes. They are able to assess the computational complexity of selected problem examples.


They can work on corresponding tasks both independently and in small groups.

Content

* Words, languages
* Chomsky hierarchy, grammars, non-determinism
* Finite automata, regular expressions, Myhill-Nerode
* Pushdown automata, CYK algorithm
* Turing machines, random access machines, Church's thesis
* Halting problem and undecidability
* Reducibility between problems
* Rice's theorem
* Complexity of word problems, computational effort, complexity classes, time hierarchy theorem
* Effort of algorithms and complexity of problems such as SAT or CLIQUE
* P, NP and NP-completeness
* Theorem of Cook and Levin

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Theoretische InformatikTutorial Winter semester[de]2 ISIS
Theoretische InformatikLecture Winter semester[de]2 ISIS

Facultative area

A selection of the following courses must be completed:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Theoretische InformatikMajor Excercise Winter semester[de]2 ISIS

Courses in the course catalog

Courses created from the teaching units of this module.

Winter semester 2026/27 (17)

Theoretische Informatik (Tutorial) 15

All groups of this course in the catalog

Theoretische Informatik (Lecture) 1

All groups of this course in the catalog

Theoretische Informatik (Major Excercise) 1

All groups of this course in the catalog

Workload and credit points

Theoretische Informatik (Tutorial)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing151 h15 h
45 h

Theoretische Informatik (Lecture)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
Pre/post processing153 h45 h
75 h

Theoretische Informatik (Major Excercise)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
30 h

Course-independent workload

Workload descriptionMultiplierHoursTotal
Solving homework for prerequisite130 h30 h
Exam preparation130 h30 h
60 h

The workload of the module adds up to 210 hours. The module therefore comprises 6 credit points.

Description of teaching and learning methods

The technical content of the module is taught in the lecture. In addition, a large exercise is offered in which special topics of the lecture are discussed again and solutions to problems are explained. However, no additional subject matter is taught, so participation is optional.

The material is applied and consolidated by regularly working on homework sheets and discussing the material and exercises in interactive tutorials. The tasks are completed by the students in small groups.

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

Knowledge from the module "Formal-mathematical Groundwork".

Mandatory requirements for the module examination registration:

The examination requirements could not be retrieved.

Completion of the module

GradingGraded
Exam formatWritten exam
LanguageGerman
Duration/Extent2 hours

Exam description

Description of prerequisites:
The "Unbenoteter Übungsschein" is obtained with at least 50% of the total points in the biweekly homework.
Effort: about 30h

Duration of the module

The following number of semesters is estimated for taking and completing the module: 1 semester(s).

This module can be started in the following semesters: Winter semester.

Maximum number of participants

This module is not limited to a number of students.

Registration procedures

The teaching materials are provided via ISIS.
Tutorials are assigned via MOSES in the first week of lectures.
Exam registration is done online.
Participants that obtained with 50% of the total points of the homework are admitted to the examination.
The registration and deregistration deadlines will be announced on ISIS as well as in the classroom course.

Recommended reading, lecture notes

Lecture notes

unavailable

Electronic lecture notes

unavailable

Recommended literature

  • Elaine Rich: Automata, Computability, and Complexity, Pearson, 2008
  • Uwe Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008

Assigned programs

This module version is used in the following programs:

Program / program versionSemester(s)Curriculum component
Computer Science
Computer Science (B. Sc.) - StuPO 2015
SS 2026Pflichtbereich
WS 2026/27Pflichtbereich › Theoretische Grundlagen der Informatik
Computer Science
Computer Science (B. Sc.) - StuPO 2025
WS 2026/27Pflichtbereich › Mathematisch-algorithmisch-konzeptionelle Kompetenzen

Miscellaneous

Not specified