Theoretical Computer ScienceModule description #41282 / Version 1
- 6 CP
- Written exam
- Graded
- Winter semester
- German
| Module / Version | #41282 / #1 |
|---|---|
| Validity | Since Summer semester 2026 |
| Available language(s) | English, German |
| Credit points | 6 |
| Person responsible for the module | Nichterlein, André |
| Grading | Graded |
| Exam format | Written exam |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Contact
| Office | EN 23 |
|---|---|
| Contact person | Thielcke, Christlinde |
| E-mail address | lehre@akt.tu-berlin.de |
| Website | https://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.
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
* 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:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Theoretische Informatik | Tutorial | Winter semester | [de] | 2 | WS 2026/27 (15) ISIS | |
| Theoretische Informatik | Lecture | Winter semester | [de] | 2 | WS 2026/27 (1) ISIS |
Facultative area
A selection of the following courses must be completed:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Theoretische Informatik | Major Excercise | Winter semester | [de] | 2 | WS 2026/27 (1) ISIS |
Courses in the course catalog
Courses created from the teaching units of this module.
Winter semester 2026/27 (17)
Theoretische Informatik (Tutorial) 15
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 10:00 - 12:00 MA 542
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 12:00 - 14:00 MA 648
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 12:00 - 14:00 MA 751
- Theoretische Informatik (Tutorium) Di. 13.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 16:00 - 18:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Do. 15.10 - 17.12.26, wöchentlich, Do. 07.01 - 11.02.27, wöchentlich, 12:00 - 14:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Fr. 16.10 - 18.12.26, wöchentlich, Fr. 08.01 - 12.02.27, wöchentlich, 10:00 - 12:00 MA 142
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 10:00 - 12:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 12:00 - 14:00 EB 133C
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 12:00 - 14:00 MA 742
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 14:00 - 16:00 E-N 193
- Theoretische Informatik (Tutorium) Mi. 14.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 14:00 - 16:00 MA 143 (Tafel defekt)
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 10:00 - 12:00 M 128
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 10:00 - 12:00 MA 142
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 12:00 - 14:00 MA 551
- Theoretische Informatik (Tutorium) Mo. 12.10 - 14.12.26, wöchentlich, Mo. 04.01 - 08.02.27, wöchentlich, 14:00 - 16:00 MA 143 (Tafel defekt)
Theoretische Informatik (Lecture) 1
- Theoretische Informatik (Vorlesung) Vorlesung
Theoretische Informatik (Major Excercise) 1
- Theoretische Informatik (Großübung) Großübung
Workload and credit points
Theoretische Informatik (Tutorial)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 15 | 1 h | 15 h |
| 45 h | |||
Theoretische Informatik (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| Pre/post processing | 15 | 3 h | 45 h |
| 75 h | |||
Theoretische Informatik (Major Excercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| 30 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Solving homework for prerequisite | 1 | 30 h | 30 h |
| Exam preparation | 1 | 30 h | 30 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.
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
| Grading | Graded |
|---|---|
| Exam format | Written exam |
| Language | German |
| Duration/Extent | 2 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
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.
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 version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Science Computer Science (B. Sc.) - StuPO 2015 | SS 2026 | Pflichtbereich |
| WS 2026/27 | Pflichtbereich › Theoretische Grundlagen der Informatik | |
| Computer Science Computer Science (B. Sc.) - StuPO 2025 | WS 2026/27 | Pflichtbereich › Mathematisch-algorithmisch-konzeptionelle Kompetenzen |
Miscellaneous
Not specified