Student's Portal

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# at The End of The Course The Students Will Know# 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. Understand and Apply The Concept of Reduction Between Problems.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

234247 - Algorithms 1

Course with no extra credit

46002 - Design and Analysis of Algorithms 97447 - Intro. to Computability and Complexity 106843 - Theory of Computation C 214912 - Computational Models For Teachers 237343 - Theory of Computation

Course with no extra credit (contained)

94250 - Introduction to Computability

• Computational complexity - Papadimitriou, Christos H.
• Computers and intractability : a guide to the theory of Np-Completeness - Garey, Michael R.
• Introduction to automata theory, languages, and computation - Hopcroft, John E.
• Introduction to automata theory, languages, and computation / John E. Hopcroft, Jeffrey D. Ullman. - Hopcroft, John E.
• Introduction to automata theory, languages, and computation / John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. - Hopcroft, John E.
• Introduction to the theory of computation - Sipser, Michael
• Introduction to the theory of computation / Michael Sipser. - Sipser, Michael
• Introduction to the theory of computation / Michael Sipser. - Sipser, Michael
• מבוא לתורת החישוביות - גולדרייך, עודד