Basic Information
Recursive and Primitive Recursive Functions, Turing Machines. Equivalence Between Several Models, Church's Thesis, Universal Machine, Undecidable Problems, Deterministic and Nondeterministic Machines, The Class P and Np-completeness, Cook's Theorem._ Learning Outcomes# By The End of The Course, The Student Will# 1. Be Familiar With Models of Computation, in Particular The Turing Machine Model. 2. Distinguish Between Decidable and Undecidable Problems. 3. Be Familiar With The Concept of Efficient Computation (in Time Or Memory), and Be Able to Classify Problems Into Those That Can Be Solved Efficiently Or That Are "computationally Hard". 4. Undersand and Apply The Concept of Reduction Between Problems.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
Course with no extra credit
236343 - Theory of Computation 46002 - Design and Analysis of Algorithms 97447 - Intro. to Computability and Complexity 106843 - Theory of Computation C 214912 - Computational Models For Teachers
Course with no extra credit (contained)
94250 - Introduction to Computability