- 换个角度看问题 - 捐款之争其实是文理之争 [2011/09]
- 也说说中医信仰和基督教的相似之处(ZT) [2011/09]
- 关于“鼠类” [2011/09]
- (转贴)西方的人文教育是导致目前其金融危机的最根本原因 [2011/09]
- Today is Dennis Ritchie Day [2011/10]
- 做习题的境界(ZT) [2011/11]
- 不要拒绝科学(ZT) [2011/11]
- 美国男女收入差别的原因之一 [2011/09]
- 有图有真相,美国在走下坡路 [2011/09]
- Steve Jobs, John McCarthy, Dennis Ritchie: three of a kind, and don’t forget it [2011/11]
- ZT 换帅的后果很显著------评评国足的失球 [2011/09]
做过算法分析的老大们都知道,求和是门诡异的艺术,不然Concrete Mathematics里也不至于花大量篇幅讨论各式让人眼花缭乱的技巧,比如第二章,比如第五章。对求和不熟的老大可以试一试求解下面的例子体验一下。

Knuth的《编程的艺术》第
一卷里有道题目(1.2.6.63):开发出可以简化带二项式系数求和公式的程序。这道题的难度在1968年的初版中被定为50,意思是虽然很多牛人前赴
后继,但仍未完全解决的研究问题。费马大定理也是书中的一道习题,难度系数也是50(97年的新版TAOCP里改成45了,因为Andrew
Wiles在1994年搞定这坨定理,让无数民科肝肠寸断)。高难度的问题从来就是牛人们的内固醇。这道用计算机求和的题目让组合数学的牛人Doron Zeilberger和Herbert Wilf high得不行。于是1991年,著名的Zeilberger-Wilf理论问世乐。这套理论使得我们可以用程序找出求和公式的封闭解,或者证明一个求和公式没有封闭解。端的威力巨大。有了这套理论,上述公式的求和变成下面的机械步骤:
- 到这个网址下载EKHAD库。
- 在Maple里载入这个库。
- 定义F(n, k),也就是求和符合后的项。
- 调用zeil(F(n,k),k,n,N).
- 结果出来老。收工回家。老婆孩子热炕头。该干嘛干嘛。
而这一切,都归功于A=B里总结的几个关键定理。这套定理把求和公式转换为某个复杂的递归表达式,而处理递归正是计算机的拿手好戏。想知道细节的,去读这本书吧,嘿嘿。
书的序言是Knuth写的。那句传布甚广关于科学和艺术的铿锵引言就是从这里来的:Science is what we
understand well enough to explain to a computer. Art is everything else
we do.... Science advances whenever an Art becomes a Science. And the
state of the Art advances too, because people always leap into new
territory once they have understood more about the old.

