Title:

Computability and Complexity

Code:VSL
Ac.Year:ukončen 2003/2004
Term:Winter
Study plans:
ProgramBranchYearDuty
EI-BC-3VTB2nd Stage/1st YearElective
EI-MSC-3VTN2ndCompulsory
EI-MSC-5VTI2nd Stage/2nd YearCompulsory
Language:Czech, English
Public info:http://www.fit.vutbr.cz/study/courses/VSL/public/
Credits:6
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:39120014
 ExaminationTestsExercisesLaboratoriesOther
Points:7520005
Guarantee: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
Faculty:Faculty of Information Technology BUT
Prerequisites: 
Theoretical Computer Science 1 (TI1), DITS
Follow-ups:
Parallel and Distributed Algorithms (PDA), FIT
 
Learning objectives:
To learn mathematical models of computation and theory of computability and complexity.
Description:
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.
Learning outcomes and competences:
Understanding theoretical and practical limits of arbitrary computational systems.
Syllabus of lectures:
  1. Mathematical models of computation and computing systems,
  2. Turing machines.
  3. Multi-tape and non-deterministic Turing machines.
  4. Turing machines as language acceptors.
  5. Decidability.
  6. Universal Turing machine. Halting problem, Post correspondence problem.
  7. Computability, primitive recursive functions, partial recursive functions.
  8. Turing-Church thesis.
  9. Algorithmic complexity, problem complexity.
  10. Asymptotic aproximation of complexity.
  11. Complexity in the context of various model of computation, polynomialy bound models.
  12. Deterministic decidability in polynomial time.
  13. NP-languages, NP-problems. NP-completness.
Syllabus - others, projects and individual work of students:
  1. 5 homeworks during semester
Fundamental literature:
  1. Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
  2. Saloma, A.: Computation and Automata, Cambridge University Press, 1985.
Study literature:
  1. Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.