Course details

Computability and Complexity

VSL Acad. year 2004/2005 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.

Guarantor

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

Language of instruction

Czech

Completion

Credit+Examination

Time span

  • 39 hrs lectures
  • 12 hrs exercises
  • 14 hrs projects

Department

Department of Intelligent Systems (UITS)

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

There are no prerequisites

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

There are no checked study.

Back to top