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