Introduction to the Theory of Computation
Winter
(in German: Grundlagen der Theoretischen Informatik )
Module-ID: FIN-INF-110493 |
|
Abbreviation
|
Credit Points 5 |
Semester Winter |
Term |
Duration 1 Semester |
Language english |
Level Bachelor |
| Link: | LSF |
| Limited accessability: | |
| Responsibility: | Tetiana Lavynska |
| Lecturer: | Tetiana Lavynska |
| Classes: |
|
| Applicability in curriculum: | - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Aufbaumodule (SPO 2027) |
Intended learning outcomes:
- Basics of automata theory and formal languages for problem solving
- Ability to classify problems in terms of predictability and complexity
Content:
- Introduction to Formal Languages (regular and context-free languages, grammars),
- elementary automata theory (finite automata, basement automata),
- Computational models and Church's thesis,
- Decidability and semi-decidability,
- Complexity classes : P and NP, NP-completeness
Workload:
70h contact hours + 80h self study
| Pre-examination requirements: | Type of examination: | Teaching method / lecture hours per week (SWS): |
|
Exam preparation: Successful participation in the exercises (see lecture) |
Written exam 120 minutes |
Lecture (3 SWS) Exercise (2 SWS) |
| Prerequisites according to examination regulations: | Recommended prerequisites: |
|
none |
| Media: | Literature: |
|
Comments: