Очевидный ответ: вообще эта программа совсем по другому поводу, но если вдруг есть интерес не только к CS, то...


Вспомнил еще несколько хороших книг:

* Шень, Программирование в теоремах и задачах
* Lewis-Papadimitriou, Elements of the theory of computation (должна сильно пересекаться с Sipser'ом)
* Dasgupta-Papadimitriou-Vazirani, Algorithms

С этого, вместе с Sipser'ом, а также второй частью Верещагина-Шеня ("Вычислимые функции"), разумно и начинать.

По сложности есть

* Китаев-Шень-Вялый, Классические и квантовые вычисления
* Arora-Barak, Computational complexity