2008-03-07 16:55:26
来自: etone
具体数学：计算机科学基础（英文版.第2版）的评论
我一直认为，评价一本专业书籍，不仅要知道它讲了什么，也要清楚它没讲什么。有了这样的信息，人们才会知道这本书是不是他要的；而且除了这本书他还需要什么。这比仅仅把它作为“经典”而向人推荐，更有帮助。
一本好的专业书不但要清晰的呈现美丽的结果，也要为人们指出通向这些结果的道路。也就是解决问题的一般途径。Polya所著的那本经典读物，可以很好的概括之："how to solve it"。
用这个统一的标准去衡量，《具体数学》是很优秀的。这本书就是专门为了上课而写，就是为了让原本无知的学生能够掌握一般的解题思路。这一点它作的非常好。
讲解是一流的。那么就让我们来看看内容，看看《具体数学》讲了什么，更重要的，它没讲什么。
用一句话粗暴的归纳：讲的是技巧，没有讲结构。
如果从数学分支去概括，《具体数学》所涉及的内容基本上没有超出计数组合数学（enumerative combinatorics）和分析组合数学（analytic combinatorics）的范围，间或涉及一点数论和离散概率内容，但对这些内容的取舍依然具有很强的组合数学趣味。
与组合数学的专著相比，《具体数学》对这些论题的阐述，处处都在强调“演算”的技巧；但基本忽略了一般的(general)数学定理、抽象的(abstract)数学体系。可谓“具体”的实至名归。
这样选择，是出于计算机科学专业需求的考虑。《具体数学》中的数学，是计算机科学所做之事（例如算法分析）的“工具”，但并非是计算机科学的“主题”。因此计算机科学专业的学生，毋须在这些数学体系上做文章，但若掌握了娴熟的演算技巧，却的确可以事半功倍。
计算机科学的数学工具箱——这就是《具体数学》要扮演的角色。在这个角色上，它是独一无二的。
但数学之于计算机科学，并非时时刻刻都是工具而已，很多时候也可能成为主题本身。这样的内容就是《具体数学》所没有涉及到的。
计算机科学有个俗气的时髦外表，点缀着各种新鲜而短命的技术词汇，但也有个朴素而美丽的硬核，就是计算机科学的理论根基（theoretical foundations）。《具体数学》为我们展示了这个硬核的一面：分析和演算；却也有意的忽视了另一面：结构(structures)和刻画(characterizations)。
而这部分没有被《具体数学》覆盖的内容，对于计算机科学而言已不再仅仅是工具，而可以影响到我们对计算本身的认识。
任何形式的计算(computation)，都受限于具体的计算模型(computational model)。也因这样的限制，问题和算法，作为数学对象，都有了各自的结构。计算的界限也因此产生。怎样刻画这些结构，关系到人类对于计算本质的认识，而这也是理论计算机科学永恒的主题。从这个意义上说，理论计算机科学基本上就是在研究组合数学：面对算法或问题这么个离散对象，对性质的分析，对结构的刻画。《具体数学》的内容是前者，而后者从风格上则是完全不同的另一类东西了。
并不是每一个计算机科学专业的人都有必要去关注这些内容，毕竟大多数学习计算机的人是为了谋得更好的生活，而不是为了探索未知。这也是为什么《具体数学》展现着精巧和实用，却藏起了美丽和永恒。因为后者会吓跑很多人，也难免耽误一些人。《具体数学》的英文副标题更诚实："A Foundation for Computer Science"，声明这只是计算机科学的基础之一。到了中文，那个“a”就被含糊掉了，整个就成了全部“计算机科学基础”。
但愿这只是个翻译上的瑕疵，而不是我们实际的选择：精巧实用尚存一席之地，美丽和永恒已被彻底遗忘。
具体数学：计算机科学基础（英文版.第2版）的评论
我一直认为，评价一本专业书籍，不仅要知道它讲了什么，也要清楚它没讲什么。有了这样的信息，人们才会知道这本书是不是他要的；而且除了这本书他还需要什么。这比仅仅把它作为“经典”而向人推荐，更有帮助。
一本好的专业书不但要清晰的呈现美丽的结果，也要为人们指出通向这些结果的道路。也就是解决问题的一般途径。Polya所著的那本经典读物，可以很好的概括之："how to solve it"。
用这个统一的标准去衡量，《具体数学》是很优秀的。这本书就是专门为了上课而写，就是为了让原本无知的学生能够掌握一般的解题思路。这一点它作的非常好。
讲解是一流的。那么就让我们来看看内容，看看《具体数学》讲了什么，更重要的，它没讲什么。
用一句话粗暴的归纳：讲的是技巧，没有讲结构。
如果从数学分支去概括，《具体数学》所涉及的内容基本上没有超出计数组合数学（enumerative combinatorics）和分析组合数学（analytic combinatorics）的范围，间或涉及一点数论和离散概率内容，但对这些内容的取舍依然具有很强的组合数学趣味。
与组合数学的专著相比，《具体数学》对这些论题的阐述，处处都在强调“演算”的技巧；但基本忽略了一般的(general)数学定理、抽象的(abstract)数学体系。可谓“具体”的实至名归。
这样选择，是出于计算机科学专业需求的考虑。《具体数学》中的数学，是计算机科学所做之事（例如算法分析）的“工具”，但并非是计算机科学的“主题”。因此计算机科学专业的学生，毋须在这些数学体系上做文章，但若掌握了娴熟的演算技巧，却的确可以事半功倍。
计算机科学的数学工具箱——这就是《具体数学》要扮演的角色。在这个角色上，它是独一无二的。
但数学之于计算机科学，并非时时刻刻都是工具而已，很多时候也可能成为主题本身。这样的内容就是《具体数学》所没有涉及到的。
计算机科学有个俗气的时髦外表，点缀着各种新鲜而短命的技术词汇，但也有个朴素而美丽的硬核，就是计算机科学的理论根基（theoretical foundations）。《具体数学》为我们展示了这个硬核的一面：分析和演算；却也有意的忽视了另一面：结构(structures)和刻画(characterizations)。
而这部分没有被《具体数学》覆盖的内容，对于计算机科学而言已不再仅仅是工具，而可以影响到我们对计算本身的认识。
任何形式的计算(computation)，都受限于具体的计算模型(computational model)。也因这样的限制，问题和算法，作为数学对象，都有了各自的结构。计算的界限也因此产生。怎样刻画这些结构，关系到人类对于计算本质的认识，而这也是理论计算机科学永恒的主题。从这个意义上说，理论计算机科学基本上就是在研究组合数学：面对算法或问题这么个离散对象，对性质的分析，对结构的刻画。《具体数学》的内容是前者，而后者从风格上则是完全不同的另一类东西了。
并不是每一个计算机科学专业的人都有必要去关注这些内容，毕竟大多数学习计算机的人是为了谋得更好的生活，而不是为了探索未知。这也是为什么《具体数学》展现着精巧和实用，却藏起了美丽和永恒。因为后者会吓跑很多人，也难免耽误一些人。《具体数学》的英文副标题更诚实："A Foundation for Computer Science"，声明这只是计算机科学的基础之一。到了中文，那个“a”就被含糊掉了，整个就成了全部“计算机科学基础”。
但愿这只是个翻译上的瑕疵，而不是我们实际的选择：精巧实用尚存一席之地，美丽和永恒已被彻底遗忘。
本评论版权属于作者etone，并受法律保护。除非评论正文中另有声明，没有作者本人的书面许可任何人不得转载或使用整体或任何部分的内容。
在哪儿买这本书? · · · · · ·
作者: Ronald Graham, Donald E.Knuth, Oren Patashnik
副标题: 计算机科学基础
isbn: 7111105761
书名: 具体数学：计算机科学基础（英文版.第2版）
页数: 657
定价: 49.0
出版社: 机械工业出版社
装帧: 平装
出版年: 2002-08-01
又名: Concrete Mathematics A Foundation for Computer Science(Second Edition)
2008-04-20 22:53:57 Charor
刚看了四章,我也非常喜欢这本书.2008-10-04 07:19:40 crypto
写的很棒，我指的是etone的书评2008-11-16 18:45:21 Fantasybei
那结构和刻画这方面有啥好书嘛?2009-03-04 21:05:46 张云天
无论是刻画还是characterizations,在计算机科学与技术这个领域中，我还是第一次听说 -- 你大可以忽略这个词。结构，我想，作者主要是指数据结构吧。
2009-04-05 20:54:59 foo
2009-03-04 21:05:46 张云天结构，我想，作者主要是指数据结构吧。
----------------
汗，明显不是。
2009-04-06 08:30:09 张云天
那你说是什么？我不知道什么时候结构、刻化成了计算机科学的理论根基了，发正我搞计算机搞了近10年，这种说法还是头一回听说。我怀疑楼主, 是不是真懂不懂计算机啊?
2009-04-06 16:26:42 foo
受不了了，哪门学科没有结构啊？Lss不还在读Sipser的计算理论嘛，读完再说吧。
2009-04-06 16:53:58 张云天
扯你妈的蛋。有结构就成理论基础了？不懂别乱喷。2009-04-06 17:32:51 foo
这跟在计算机领域待了10年还是20年没关系，真的没关系。如果你有兴趣，可以去看看theory of computation, complexity theory之类的。 只是别指望能对写代码，找工作有什么帮助。
2009-04-06 17:35:03 疯凰
ls用词注意点吧，讨论的话没必要用一些不必要的语言吧。我觉得 结构还是蛮重要的 （我指的是 数据结构）
2009-04-06 21:08:18 张云天
数据结我也觉得重要。关于用词注意不注意的问题，对于认真发贴的人当然用词需要注意，对于啥都不懂还装十三，还动不动就拿些英文书来推荐的人就不用注意了。2009-04-06 21:12:52 疯凰
哦，这样的啊^^ 没有啦，好像这个是他研究的东西 （那个characterizations），所以就发到这里来了。可能没有写得仔细点吧，呵呵呵呵2009-04-06 21:21:19 foo
"任何形式的计算(computation)，都受限于具体的计算模型(computational model)。也因这样的限制，问题和算法，作为数学对象，都有了各自的结构。计算的界限也因此产生。怎样刻画这些结构，关系到人类对于计算本质的认识，而这也是理论计算机科学永恒的主题。"计算总是在某个数学上well-defined的计算模型上定义的。有限状态自动机,下推自动机,确定性图灵机,非确定性图灵机,lambda演算，诸如此类。有些问题是某些计算模型能处理的，有些超出了它们的界限。在此基础上，问题可被划分为不同的类。这些类之间的关系是什么，性质是什么，就是所谓'结构'——这里说的结构当然不是数据结构，后者只关心数据如何存储，抽象的层次还没有这么高。
我用浅显的语言解释了一下，希望有些人自重。
2009-04-06 21:35:13 张云天
我希望有些人明白，抄这么一段东西出来。丝毫说明不了什么，“结构”“刻化”就成了计算机科学的理论基础。就这段文字看来，“结构”“刻化”和我随便敲的这段文字当中的，任何两个词语一样，没什么特殊意义和专业术语意义。
2009-04-06 21:38:35 foo
这段话又不是论证，只是说明，让你有个概念。至于为什么是基础，举个例子，计算理论给出结论说你没办法写个编译器能够把任一程序都优化到最短，那么这件事诸位就可以放弃了，即便是世界上最优秀的程序员也不可能做到，因为它是理论上不可行的。
2009-04-06 22:29:23 张云天
哦，我明白了。原来计算理论告诉了我们结构和刻化是计算机科学的基础，那么即使是世界上最优秀的大脑也证明不了结构和刻化原来不是计算机科学的基础啊。2009-04-07 11:17:33 etone
好久不来，想不到竟然还吵起来了。如果不知道文中的“结构”和“刻画”究竟指什么，其实也不必深究了。理论计算机科学虽然重要，但并不是每个人都有必要弄清楚，没听说过这些也正说明所从事的领域不需要了解这些。这也很正常，毕竟术业有专攻。
RE foo:
你所总结的：“计算总是在某个数学上well-defined的计算模型上定义的。有限状态自动机,下推自动机,确定性图灵机,非确定性图灵机,lambda演算，诸如此类。有些问题是某些计算模型能处理的，有些超出了它们的界限。在此基础上，问题可被划分为不同的类。这些类之间的关系是什么，性质是什么，就是所谓 '结构'——这里说的结构当然不是数据结构，后者只关心数据如何存储，抽象的层次还没有这么高。”
我很同意你的看法，你所提到的“结构”也正是计算复杂度的一个核心领域“结构复杂度”(structural complexity theory)命名的由来。
除了这种宏观上的结构之外，理论计算机科学领域还涉及到很多具体的数学结构，这简直不胜枚举，例如判定树(decision tree)、扩展图(expander graph)，以及各种各样的组合数学结构等等。许多理论计算机科学的重要问题，都可以归结为构造某种符合特定性质的数学结构，例如，去随机化 (derandomization)和纠错码(error-correcting code)的一些核心问题，都可以归结为扩展图的构造问题。
关于“刻画”，可能研究数学的人更熟悉这个说法。简言之，一个数学刻画就是为了说明这样的问题：“我们定义出来的某个东西，它究竟是什么？”
其实我们对它并不陌生。例如我们都知道：基于比较的排序，这个问题的复杂度是Ω(n log n)。证明这个下界的方法是通过判定树：任何一个基于比较的排序算法，它都是一棵判定树，而判定树的高度就是算法的时间复杂度——这就是一个 characterization。通过这样的刻画，我们回答了这个问题“什么是基于比较的排序？”("What is comparison-based sorting?") 从而证明了排序的复杂度——这不是某个具体算法的效率，而是关于所有解决这个问题的算法的一般规律。
正如foo同学前面提到的，理论计算机科学研究well-defined的模型中的计算。类似上面的"What is comparison-based sorting?"的问题，人们也在问“What is computation?”或者具体点的“What is Turing computation?”。但为了回答这些问题，仅仅知道模型的定义是远远不够的。人们不断的尝试用我们能讲的清楚的结构去刻画 computation。但据我所知，人类离回答这些问题还有很长一段距离。图灵机是一个很general也很robust的计算模型，因此Church -Turing thesis用图灵机来定义computation。但定义归定义，图灵机本身很难用来刻画计算，因为它透露出来的关于计算的结构性信息少之又少，甚至可以说图灵机仅仅就是个定义而已。人们曾经一度寄希望于等价的模型circuit complexity，相比于图灵机，circuit具有非常清晰的结构，这似乎意味着它能把什么是计算说得更清楚一些。但1994年的一个重要发现 “natural proofs”宣告人们无法通过circuit complexity得到几乎任何有意义的结果。
目前，人们仍然没有办法刻画清楚广义的计算，没办法说清楚computation作为一个数学对象，它具有什么样的结构。对于那些被我们猜想很难的问题，例如NP完全问题，人们猜想它们的复杂度是超过任何多项式时间的，可实际已经证明出的最高的复杂度，猜猜看是什么呢？哈哈，是Ω(n)。也就是说，关于广义的计算和算法，人们唯一能确定的，就是它至少要把输入读完，除此之外几乎一无所知。这正是因为，人类尚不知道怎么去刻画广义的计算，说不清楚计算具有什么样的结构。这个艰巨的任务，是理论计算机科学的一个使命，也将会是一场持久战。
2009-04-07 12:53:42 foo
例如NP完全问题，人们猜想它们的复杂度是超过任何多项式时间的，可实际已经证明出的最高的复杂度，猜猜看是什么呢？哈哈，是Ω(n)。不大理解。你刚刚说排序是\omega(nlogn)的啊？或者广义这里并不是一般的意思？一般的问题至少不会比一个特殊的问题更容易。
当然排序不是判定问题，但在我记忆中，有的判定问题，比如判断n个数里是否有重复的数，也可以用algebraic decision tree证明是\omega(nlogn)的吧。
2009-04-07 13:10:42 foo
我知道了. 这里是按输入长度算的, 所以数字按binary存储, 就只能是Ω(n)了.2009-04-07 13:28:50 etone
to foo:这个Ω(n log n)的下界，是comparison-based sorting algorithms的下界，如果不给算法加任何限制的话，我们无法得到大于Ω(n)的下界。这跟是不是判定问题关系不大。
实际上，现在已知的非平凡的下界，几乎每一个都是对计算模型做了额外的假设或限制，例如sorting、MST等问题的下界，人们假设算法都是comparison-based的（相应的计算模型是pointer machine），单带图灵机上的palindrome问题的下界（这个下界完全依赖于“单带”是个强制性的额外假设）；或者干脆就是information-theoretical bound，忽略computation的代价，即只要读取了input里面足以计算出结果的信息位就算完成了计算，例如query complexity of boolean functions和quantum query complexity等等。
图灵机（尤指RAM图灵机，而非单带图灵机）及其等价模型上的无额外条件的下界，只存在于屈指可数的几个非常特殊的问题。对于人们熟悉的NP完全问题，例如K-CLIQUE，它最好的已知下界就是Ω(n)。
你可以选一个问题尝试去分析一下，例如K-CLIQUE的一个instance，判定输入图里面有没有1000-clique，即点数为1000的完全子图。看上去应该不可能有O(n)的算法吧(n是输入大小，而非结点数)，但不对算法做任何额外假设的话，能证明不存在O(n)的算法吗？
如果你能证明这样一个下界，这将会是一个break-through。
2009-04-09 17:40:59 张云天
白痴。2009-05-17 11:33:52 风清云淡
搞研究的和做工程碰到一起那就是：秀才遇到兵有理说不清;-)2009-07-29 18:05:42 wwj_douban
coder2009-10-05 15:00:09 B166ER
看评论总是那么有趣，让人对事对人看的很清晰2009-12-05 14:32:17 designer
作者看待现代数学明显带有结构主义的情节。组合数学是结构主义最不屑的，当然也是最让结构主义感到无能为力的，因为他无法使组合数学统一于它所谓的结构。如果这都解决了，三大数学流派不早就一统了。楼主不必不屑组合数学，今日之组合数学非昨日之组合数学，它早已称为现代数学发展最快且不可或缺的分支，而不是昨日的弃子。不要抱怨，总是拿“结构”说事，谁又规定了数学必须有结构了？带着结构注意的傲慢，却看不出你对结构主义的有什么独特的见解，注定你看不到数学的全局与未来。
这是结构主义最大的硬伤，固执，自以为是，不知从哪来的自信，从不审视自己为什么多少年没发展，导致对于新兴的数学分支只能手足无措，而不会融入。
一个曾经彻底的结构主义者的忠告
2009-12-16 23:06:49 J&C
"我一直认为，评价一本专业书籍，不仅要知道它讲了什么，也要清楚它没讲什么。"明显没学过数理化的思维～
看见这一句，下面的就没什么好看的了。
> 我来回应