推荐几本有关算法（偏可计算理论）的书

huangyhg

===================国内的======================
1. 计算复杂性导论 堵丁柱 2002年 高教版。
其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等
。此外，本书还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。
这是一本很好的书了。值得一看。50多rmb.
2.陆钟万 面向计算机科学的数理逻辑 （第二版） 第二版在第一版中加了不少注释。精干，逻辑也不错。
3.莫绍揆 数理逻辑导论 这本书比较老了。我手中的是图书馆1965年版的。经典图书之一。
4.莫绍揆 数理逻辑概貌 科普图书。 如果不打算做深入研究的话，可以看看。通俗易懂。
5.莫绍揆 递归论 递归论的必读书。不过比较困难。建议先看数理逻辑。我在看第二遍而已。：（
6.公理集合论导引 科学出版社 忘了是谁写的了。好像是张xx.
7.初等数论 潘承洞 潘成彪兄弟 北大出版社
8.逻辑 语言 计算 马希文 商务印书馆.这是本文集. 可以看看.做自然语言理解的应该看看,上面有中文
自然语言方面内容.
===================国外的==================================================================================
国外的算法书经典当属:
1.The art of computer programming. Knuth. 这三卷书堪称计算机科学的史诗.国防工业大出版社印的是中文翻译版:
98.*rmb * 3.清华印的是英文影音版:85.00*3 rmb.个人觉得看影印版较好.中文翻译中有些名词不太顺.可能和我之前看的
入门书有关.书后写着:如果你看完这三卷书,请给我发简历--Bill Gates.

2.Introduction to Algorithm. Corman(好像是这样写).三个作者的名字缩写是:CLRS.
内容非常全.而且很好懂,很有逻辑,例子多.必读经典.高教影印版,50rmb，不贵。

这两本是很好的算法书了.
下面说说哲学方面的.我看的书不多,只能说下面一些了:
3.歌德儿,埃舍尔,巴赫---集异壁之大成 候世达 商务印书馆 。 这是一本奇特的书。
将理论计算机和音乐（巴赫的赋格）埃舍尔的画结合起来了。非常有哲理。入门的时候
看是一个味道，对理论计算机有一定了解后在看，又是一个味道。：）。ps:中文翻译
也很用功。很好。 85.00rmb。不太好买到了吧。
4.数学哲学 商务印书馆(2002) 36.00rmb。商务印书馆印了很多好书。这也是一本。上面收录
了很多论文集。如hilbert的论无限。经典好书。不过看之前需要对数理逻辑有了解。

说说自动机方面的：
5. Introduction to Automata Theory,Language,and Computation. Prentice Hall/Pearson. 这本书清华有印第二版.
个人觉得第二版的内容在深度上和广度上似乎不如1979年第一版.我们上学期用的自动机教材就是这一本.不过是1979年
的第一版.国内翻印的,科学出版社.只是不再印了.我们用的是胶印盗版.. 课后的习题很有难度.上学期狂作了1-8章的
大约50多道题.就没再作了.没时间.

6.可计算性与数理逻辑 电子工业 英文影印版 38rmb. 好书.上面有将数理逻辑一些较深入的内容.

7.计算理论导论 机工 这本就比较浅显一些.如果看5觉得困难的话,可以看这本.

8.可计算性 复杂性 语言 --- 理论计算机科学基础 Davis等. 这是我在图书馆借的. 清华 好像是87年出的.好像没有再版了.
也是很好的入门书.内容很全.都是introduction性质的。 说说Davis,这家伙很牛.曾经和别人合作解决了丢番图方程(也是Hiblert的23个问题).

上面说的5,7,8 是国外很多大学（standford, cornell）的可计算性， 自动机的教材。


说说，递归论/集合论（关于这方面，北大bbs数学版精华区内有个很好的书单）方面的：

9.Soarse R.I. Recursively enumerable sets and degrees, Springer-Verlag, 1987 现代递归论的必读教材
10. Nigel Cutland. Computability, an introduction to recursive function theory / Cambridge University Press, 1980.
递归论的很好的入门教材。学校的图书馆应该有。
11. Rogers H.Jr Theory of recursive functions and effective computability, McGraw Hill, 1967
同样很经典。如果你经常读paper的话，会在references理经常看到它的。
12.Jech T.J. Set Theory, Pure and Applied Mathematics, Academic Press, 1978
集合论中最经典的入门读物，98年出了修订版。据说现在要去Berkeley都Ph.D.首先得把这本书看完。
13.Kunen K. Set Theory, North Holland, 1980 好书

其他的书：
布鲁迪 组合数学（3th ed.） 机工 这本书机工有中文翻译和影印版两本。 上学期哦们的课用的是中文版。还不错。推荐。读起来很有意思，
而且书中还涉及了很多东西，如Ramsey定理（6个人中必有三个人互相认识或者互相不认识：））， Polya计数法这么困难的内容讲得很清晰。