Computability and Complexity
VSL Acad. year 2005/2006 Winter semester 6 credits
Language of instruction
Subject specific learning outcomes and competences
Generic learning outcomes and competences
Prerequisite kwnowledge and skills
- Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.
- 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.
- 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.
Syllabus - others, projects and individual work of students
- 5 homeworks during semester
Mid-term exam - 20 points.