Workload:
270 h
|
Module Number INFM2410 |
Module Title Theoretical Computer Science 2: Formal Languages, Computability, and Complexity Theory (formerly Theoretical Computer Science) |
Type of Module Elective Compulsory |
|---|---|---|
| ECTS | 9 | |
|
Work load - Contact time - Self study |
Workload:
270 h Class time:
90 h / 6 SWS Self study:
180 h |
|
| Duration | 1 Semester | |
| Frequency | In the winter semester | |
| Language of instruction | German | |
| Type of Exam | Written Exam |
|
| Lecture type(s) | Lecture, Tutorial | |
| Content | Topics include formal languages, and automata, computability, decidability and recursive enumerability, existence of undecideable problems, Rice's first theorem, complexity theory, time and space requirements, and NP-completeness. |
|
| Objectives | Students have the ability to perform the standard constructions from the field of finite automata and regular expressions. They have an understanding of the phenomenon of non-computability and the frequency of its occurrence, as well as a basic understanding of the notion of NP-completeness and its motivation. |
|
| Allocation of credits / grading |
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Lecture
V
o
4
6.0
wt
90
g
100
Tutorial
Ü
o
2
3.0
|
|
| Prerequisite for participation | There are no specific prerequisites. | |
| Lecturer / Other | Hennig, von Luxburg | |
| Literature | Kenntnisse der Vorlesungen "Mathematik für Infomatik 1: Analysis" (INFM1010) und "Theoretische Informatik 1: Algorithmen und Datenstrukturen" (INFM2420) werden empfohlen. |
|
| Last offered | Sommersemester 2022 | |
| Planned for | Sommersemester 2024 | |
| Assigned Study Areas | BIOINFM, INFM, MDZINFM2510, MEINFM | |