Faculty of Information Technology, BUT

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

Czech, English

Completion

Credit+Examination (written)

Time span

39 hrs lectures, 12 hrs exercises, 14 hrs projects

Assessment points

75 exam, 20 half-term test, 5 projects

Department

Lecturer

Instructor

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.

Generic 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.

Prerequisite kwnowledge 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.

Syllabus - others, projects and individual work of students

  • 5 homeworks during semester

Progress assessment

Homeworks - 5 points.
Mid-term exam - 20 points.
Back to top