| INFMW Theory of Informatics | Course | INF | |
|---|---|---|---|
| Lecturers : |
Prof. Dr. Matthias Homeister
eMail
|
Term | 3 |
| Course Classification : | Master Informatik (Winter-Immatrikulation) | CH | 4 |
| Language : | Deutsch | Type | VÜS |
| Type of examination : | PL | Credits | 6 |
| Method of evaluation : | written examination 120 min | ||
| Requirements : | |||
| Cross References : | |||
| Previous knowledges : | Knowledge of NFAs, DFAs and context-free grammars, as taught in the Bachelor course “Formal Languages / Automata Theory”. | ||
| Aids and special features : | |||
| Teaching aims : | Students understand the theory of formal languages and the Chomsky hierarchy and can use formal systems for the exact modeling and classification of problems. They know several formal systems for describing computable problems and understand their equivalence. They understand the equivalence of non-deterministic linearly constrained automata and context-sensitive grammars. Students understand the structure of selected non-decidable problems, the meaning of reductions and can construct simple reductions. They know the time complexity and the classes P and NP, as well as several NP-complete problems and can prove NP-completeness. They know the classes P, NP, PSPACE and BQP and understand the relationships with regard to the P-NP question. They know several NP-complete problems, understand the associated reduction proofs and can construct simple polynomial-time reductions. Students understand the procedure of selected approximation algorithms and can assess their use in relation to the situation. | ||
| Contents : | - Theory of formal languages: Automata, grammars, Chomsky hierarchy. - Church-Turing thesis: equivalence of Turing machine variants, of Turing machines, register machines and grammars, of LBAs and type-1 grammars. - Decidability: Halting problem, Post's correspondence problem, reductions - Space and time complexity: the classes P, NP, P-SPACE and BQP - NP-completeness: polynomial time reductions, Cook's theorem and various NP-complete problems - Approximation algorithms for NP-hard optimization problems | ||
| Literature : | Sipser M.: Introduction to the Theory of Computation, Cengage Learning, 3nd edition, 2021. Schulz, A.: Grundlagen der Theoretischen Informatik, Springer Vieweg 2022. John MacCormick: What can be computed? Princeton University Press, 2018. Mertens S., Moore C.: The Nature of Computation, Oxford University Press, 2011 Schöning U.: Theoretische Informatik kurzgefasst, Spektrum Akademischer Verlag; 5. Auflage, 2008. Hoffmann D. W.: Theoretische Informatik, Hanser Verlag; 5. Auflage, 2022 | ||