Course details
Computability and Complexity
VSL Acad. year 2005/2006 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
- 39 hrs lectures
- 12 hrs exercises
- 14 hrs projects
Department
Subject specific learning outcomes and competences
Understanding basics of mathematical models of computation and theory of computability and complexity. Understanding theoretical and practical limits of arbitrary computational systems.
Understanding theoretical and practical limits of arbitrary computational systems.
Learning objectives
To learn mathematical models of computation and theory of computability and complexity.
Prerequisite knowledge and skills
Formal languages theory basics.
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.
Syllabus of lectures
- 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 aproximation of complexity.
- Complexity in the context of various model of computation, polynomialy bound models.
- Deterministic decidability in polynomial time.
- NP-languages, NP-problems. NP-completness.
Progress assessment
At least 50 precent of mid-term exam points (10 pionts).
Controlled instruction
Homeworks - 5 points.
Mid-term exam - 20 points.