Introduction to the Theory of Computation
(אלגוריתמים
וחישוביות 2)
This course covers the basic topics in the theory of computation from a
programming perspective.
Topic summary:
Programming language concepts; the computational power of a programming
language; metaprogramming; equivalence of languages of different styles,
leading to Church's thesis and the concept of a
reasonable complete programming language.
Computable and uncomputable functions; decidability; semidecidability;
the classes R and RE, reducions, Rice's theorem.
Models for complexity; time complexity, the classes P, EXP
and NP. NP-hardness and NPC.
Literature
The textbook that best matches the course is (not surprisingly) my own
(here's its
library card).
Additional literature includes:
Computability and Complexity from a Programming
Perspective by
Neil D. Jones.
Algorithmics by
David Harel (also available in Hebrew, by Open
University Press).