Title:  Computability and Complexity 

Code:  VSL 

Ac.Year:  ukončen 2004/2005 

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

Links: 

 20040922: Autumn/winterterm exam period will be expired on Fri 20050204. Miloš Eysselt, Assistant Manager of Study Affairs. 
Progress assessment: 

  Homeworks  5 points. Midterm exam  20 points.

Exam prerequisites: 

  At least 50 precent of midterm exam points (10 pionts).

