Grundlagen der Theoretischen Informatik
(in German: Grundlagen der Theoretischen Informatik )
Module-ID: FIN-INF-110105 |
| Link: | LSF |
| Responsibility: | Tetiana Lavynska |
| Lecturer: | Tetiana Lavynska |
| Classes: |
|
| Applicability in curriculum: | - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik |
|
Abbreviation
|
Credit Points 5 |
Semester Winter |
Term
|
Duration 1 Semester |
Language english |
Level Bachelor |
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) |
Exam 120 minutes |
Lecture (3 SWS) Exercise (2 SWS) |
| Prerequisites according to examination regulations: | Recommended prerequisites: |
|
none |
| Media: | Literature: |
|
Comments: