Introduction to the Theory of Computation II

Summer
(in German: Grundlagen der Theoretischen Informatik II
)
Module-ID: FIN-INF-110494
Abbreviation
Credit Points
5
Semester
Summer
Term
Duration
1 Semester
Language
english
Level
Bachelor
Link:
 LSF
Limited accessability:
Responsibility:
Tetiana Lavynska
Lecturer:
Tetiana Lavynska
Classes:
Lecture Introduction to the Theory of Computation II
Exercise Introduction to the Theory of Computation II
 
Applicability in curriculum:
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)
Intended learning outcomes:
Students have advanced skills in assessing and classifying complex problems in terms of calculability and complexity.
Content:
Further information on formal languages and automata theory (closure properties, deterministic basement automata, state minimization of finite automata),
equivalence of different computational models (e.g. Turing machines, register machines, primitive recursive and mu-recursive functions, grammars),
further undecidable and NP-complete problems.
Workload:
56h contact hours + 94h self study (working on the exercises and following up on the lectures)
Pre-examination requirements:
Type of examination:
Teaching method / lecture hours per week (SWS):
Exam admission prerequisites: Successful participation in the exercises (see lecture)
Written exam 120 min
Lecture (2 SWS)
Exercise (2 SWS)
Prerequisites according to examination regulations:
Recommended prerequisites:
none
Introduction to the Theory of Computation
Media:
Literature:
Sipser; Theory of Computation
Kozen; Automata and Computability
Comments: