Title:  Computability and Complexity 

Code:  VSL 

Ac.Year:  ukončen 2005/2006 

Sem:  Winter 

Language of Instruction:  Czech, English 

Public info:  http://www.fit.vutbr.cz/study/courses/VSL/public/ 

Credits:  6 

Completion:  credit+exam (written) 

Type of instruction:  Hour/sem  Lectures  Seminar Exercises  Laboratory Exercises  Computer Exercises  Other 

Hours:  39  12  0  0  14 

 Exams  Tests  Exercises  Laboratories  Other 

Points:  75  20  0  0  5 



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

Lecturer:  Češka Milan, prof. RNDr., CSc. (DITS) Janoušek Vladimír, doc. Ing., Ph.D. (DITS) 
Instructor:  Janoušek Vladimír, doc. Ing., Ph.D. (DITS) Křivka Zbyněk, Ing., Ph.D. (DIFS) 

Faculty:  Faculty of Information Technology BUT 

Department:  Department of Intelligent Systems FIT BUT 

Prerequisites:  

Followups:  


Learning objectives: 

  To learn mathematical models of computation and theory of computability and complexity. 
Description: 

  Mathematical models of computation and computing systems, Turing
machines. Multitape and nondeterministic Turing machines. Turing
machines as language acceptors. Decidability. Universal Turing machine.
Halting problem, Post correspondence problem. Computability, primitive
recursive functions, partial recursive functions. TuringChurch 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. NPlanguages, NPproblems. NPcompletness. 
Knowledge and skills required for the course: 

  Formal languages theory basics. 
Subject specific learning outcomes and competencies: 

  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 competencies: 

  Understanding theoretical and practical limits of arbitrary computational systems. 
Syllabus of lectures: 


 Mathematical models of computation and computing systems,
 Turing machines.
 Multitape and nondeterministic Turing machines.
 Turing machines as language acceptors.
 Decidability.
 Universal Turing machine. Halting problem, Post correspondence problem.
 Computability, primitive recursive functions, partial recursive functions.
 TuringChurch 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.
 NPlanguages, NPproblems. NPcompletness.

Syllabus  others, projects and individual work of students: 


 5 homeworks during semester

Fundamental literature: 


 Martin, J.C.: Introduction to Languages and the Theory of Computation, McGrawHill, Inc., 1991.
 Saloma, A.: Computation and Automata, Cambridge University Press, 1985.

Study literature: 


 Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.

Progress assessment: 

  Homeworks  5 points. Midterm exam  20 points.

