2007-01-12 23:36:16
来自: clkrst
具体数学：计算机科学基础（英文版.第2版）的评论
具体数学(Concrete Mathematics)，从字面上它和传统的“抽象数学”对立。序里面说，名字其实是连续(CONtinuous)和离散(disCRETE)的融合。不过名字不重要，内容主要是说在计算机科学领域内遇到的问题和传统数学常常不太合拍，传统数学的方法和理念往往不容易用来解决计算机问题，所以这个学科主要致力如何解决计算机问题，为计算机算法奠定一个数学基础，或者说给出一些可用的数学手段／方法。具体数学最早是上个世纪70年代，由著名的牛人Donald E. Knuth在斯坦福开设的一门课，这本书等于是这门课的讲义吧。
书写的很有意思，第一章讲recurrence，用了几个经典问题，写的还是挺吸引人的，呵呵。最后那个约瑟夫环问题，我看了后，的确是佩服的很。一般来说这个问题的程序的写法是模拟求解，复杂度是O(n*n)，我自己推导过一个递推的方法，可以把复杂度降到O(n)，而这本书里直接给出了这个问题的解公式，强悍。
这书的序里说，如有人发现书中的错误，无论是数学上的，还是历史常识上的，或者是排版上的，都可以和作者联系，每个错误的第一个发现者将被奖励2.56美元，呵呵，典型的Knuth风格啊。
再说句题外话，书的封底上有作者照片，三个作者站成一行，摆出同样的姿势，很酷也很有趣。不过我的第一感觉是人种差异好大，亚洲人和欧美人个头是大不同啊，呵呵。
具体数学：计算机科学基础（英文版.第2版）的评论
具体数学(Concrete Mathematics)，从字面上它和传统的“抽象数学”对立。序里面说，名字其实是连续(CONtinuous)和离散(disCRETE)的融合。不过名字不重要，内容主要是说在计算机科学领域内遇到的问题和传统数学常常不太合拍，传统数学的方法和理念往往不容易用来解决计算机问题，所以这个学科主要致力如何解决计算机问题，为计算机算法奠定一个数学基础，或者说给出一些可用的数学手段／方法。具体数学最早是上个世纪70年代，由著名的牛人Donald E. Knuth在斯坦福开设的一门课，这本书等于是这门课的讲义吧。
书写的很有意思，第一章讲recurrence，用了几个经典问题，写的还是挺吸引人的，呵呵。最后那个约瑟夫环问题，我看了后，的确是佩服的很。一般来说这个问题的程序的写法是模拟求解，复杂度是O(n*n)，我自己推导过一个递推的方法，可以把复杂度降到O(n)，而这本书里直接给出了这个问题的解公式，强悍。
这书的序里说，如有人发现书中的错误，无论是数学上的，还是历史常识上的，或者是排版上的，都可以和作者联系，每个错误的第一个发现者将被奖励2.56美元，呵呵，典型的Knuth风格啊。
再说句题外话，书的封底上有作者照片，三个作者站成一行，摆出同样的姿势，很酷也很有趣。不过我的第一感觉是人种差异好大，亚洲人和欧美人个头是大不同啊，呵呵。
本评论版权属于作者clkrst，并受法律保护。除非评论正文中另有声明，没有作者本人的书面许可任何人不得转载或使用整体或任何部分的内容。
在哪儿买这本书? · · · · · ·
作者: 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)
clkrst的其他评论 · · · · · ·
- (评什么是数学)
- (评物理世界奇遇记)
- (评渴望生活-凡高的故事)
- (评居里夫人传)
2007-01-12 23:54:36 無機客
看了你的评论，也想找来看看了，赚点刀刀也好啊2007-02-08 12:33:03 Linn
作者给出的方法只需要把变量的二进制移位，那么实现中根本不需要循环，何来O(log(n))？应该是常数时间复杂度2007-02-13 21:23:33 clkrst
如果是三进制，四进制。。。n进制呢？数字的进制转换是O(log(n))的，移位可以不需要时间。2007-02-14 00:27:04 Linn
Joesphus problem和进制没有关系，求解J(n)只需要把n的二进制表示移位。而后面和进制相关的部分是从Joesphus problem引申出来的一个求解递归关系的solution，和Joesphus problem没关系了已经。2007-02-14 23:19:41 clkrst
如果就是例子中的那个原始约瑟夫问题，二进制是够的，但通常的约瑟夫问题中是每m个人出局，那个m是变量，不一定是2，比如是每三个人划掉一个，这时候是否还依然是二进制移位呢？2007-02-15 00:58:03 Linn
一般说Joesphus problem就是指第二个人出局，如果说第n个人出局，那应该是Joesphus problem的扩展。实际上书里并没有给出你所说的第n个人出局的解，书里有个计算J(19)=1258的例子，其中J(19)=J(201(3进制))=1258(10进制)。其递归关系为：（d=3,c=10）
f(1)=34
f(2)=5
f(3n)=10f(n)+76
f(3n+1)=10f(n)-2
f(3n+2)=10f(n)+8
按照你的说法，一个第3个人出局的19人的Joesphus problem的解是1258？显然是不对的。
书里在给出Joesphus problem的递归关系后，求解这个递归关系得到了Joesphus problem的解，然后作者说我们是否可以扩展这个得出的递归关系呢，然后作者把这个递归关系扩展成了带有变量的，后面的内容也就是求解这个带有变量的递归关系。但是注意，这个带有变量的递归关系并不是说所有的变量取值都符合Joesphus problem的要求，比如在第一章最后的J(19)的递归关系显然不符合Joesphus problem的要求。也就是说如果要求解第n个人出局的Joesphus problem，这个递归关系要从新推导，而这个新的推导得从头开始。
2007-02-16 19:57:08 clkrst
恩，你说的对，最后的那个公式的确不是约瑟夫问题的通解公式，所以对于原始约瑟夫问题，复杂度 是 O(1)；对于通常的约瑟夫问题，书上没有给出解答。上面的评论也修改了一下，谢谢你的细心和耐心，顺祝新春快乐。
2007-02-16 23:12:12 Linn
新年快乐！2009-08-30 13:25:04 song
我看完第一章，有了一个浅薄的认知就是一些替推公式是可以有个close-form的
汗~
忘记了高中数学数学归纳法那一大堆的求f(n)的方法了。
> 我来回应