Faculty of Information Technology, BUT

Course details

Computability and Complexity

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

Course Web Pages

2004-09-22: Autumn/winter-term exam period will be expired on Fri 2005-02-04.
Miloš Eysselt, Assistant Manager of Study Affairs.

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.

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.

Exam prerequisites

At least 50 precent of mid-term exam points (10 pionts).
Back to top