Course details
Computability and Complexity
VSL Acad. year 2003/2004 Winter semester 6 credits
Mathematical models of computation and computing systems, Turing machines. Multi-tape and non-deterministic Turing machines. Turing machines as language acceptors. Decidability. Universal Turing machine. Halting problem, Post correspondence problem. Computability, primitive recursive functions, partial recursive functions. Turing-Church thesis. Algorithmic complexity, problem complexity. Asymptotic approximation of complexity. Complexity in the context of various model of computation, polynomilally bound models. Deterministic decidability in polynomial time. NP-languages, NP-problems. NP-completness.
Guarantor
Language of instruction
Completion
Time span
Department
Subject specific learning outcomes and competences
Understanding theoretical and practical limits of arbitrary computational systems.
Learning objectives
To learn mathematical models of computation and theory of computability and complexity.
Study literature
- Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.
Fundamental literature
- Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
- Saloma, A.: Computation and Automata, Cambridge University Press, 1985.
Course inclusion in study plans
- Programme EI-BC-3, field VTB, 1st year of study, Elective
- Programme EI-BC-3 (in English), field VTB, 1st year of study, Elective
- Programme EI-MGR-3, field VTN, 2nd year of study, Compulsory
- Programme EI-MGR-5, field VTI, 2nd year of study, Compulsory
- Programme EI-MGR-5 (in English), field VTI, 2nd year of study, Compulsory