Course details

Computability and Complexity

VSL Acad. year 2003/2004 Winter semester 6 credits

Current academic year

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.

Details ...

Guarantor

Janoušek Vladimír, doc. Ing., Ph.D. (DITS)

Language of instruction

Czech

Completion

Examination

Time span

Department

Faculty of Information Technology (FIT)

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

Back to top