做习题的境界(ZT)

作者:lambda  于 2011-11-9 12:22 发表于 最热闹的华人社交网络--贝壳村

通用分类:网络文摘|已有6评论

就是把习题当成项目来做。十年寒窗。半世煎熬。习题做完,世界随之改变。例子:A = B这本200来页的书(免费下载。作者是好心银啊),解决了《编程的艺术》 上一道难度系数为50的习题:自动化多维几何级数的求和。如果有封闭解,则自动找到该解。不然自动证明无解。这好比20年前Wolfman的 Mathematica搞定自动积分,号称机器不能积的,人肉也不用想。又好比优化编译器生成人肉编译器们望尘莫及的全局优化代码。众多老大多年积累引为 自豪的技巧转眼成为自娱自乐的玩具,价值可比1949年太祖登位前的法币。技巧贬值事小,附着于技巧上的汗水,骄傲,地位,以及掌控未来的安全感也烟消云 散恐怕更有杀伤力。所以愤怒和抵制情绪就象巴普洛夫狗的唾液一样自然分泌。一将功成万骨枯。世界就这么残酷。工业革命萌芽时疯狂打砸自动纺织机器的英国纺 织工人们想必早有体会。历史上喜剧也总在重演。我们至少已经看过机器语言高手们对汇编的鄙视,汇编语言高手们对C的不屑,C语言高手们对使用垃圾收集器的 愤怒。靠,又扯远了。还是说回这本书。
 
做过算法分析的老大们都知道,求和是门诡异的艺术,不然Concrete Mathematics里也不至于花大量篇幅讨论各式让人眼花缭乱的技巧,比如第二章,比如第五章。对求和不熟的老大可以试一试求解下面的例子体验一下。
 
Knuth的《编程的艺术》第 一卷里有道题目(1.2.6.63):开发出可以简化带二项式系数求和公式的程序。这道题的难度在1968年的初版中被定为50,意思是虽然很多牛人前赴 后继,但仍未完全解决的研究问题。费马大定理也是书中的一道习题,难度系数也是50(97年的新版TAOCP里改成45了,因为Andrew Wiles在1994年搞定这坨定理,让无数民科肝肠寸断)。高难度的问题从来就是牛人们的内固醇。这道用计算机求和的题目让组合数学的牛人Doron Zeilberger和Herbert Wilf high得不行。于是1991年,著名的Zeilberger-Wilf理论问世乐。这套理论使得我们可以用程序找出求和公式的封闭解,或者证明一个求和公式没有封闭解。端的威力巨大。有了这套理论,上述公式的求和变成下面的机械步骤:
  1. 到这个网址下载EKHAD库。
  2. 在Maple里载入这个库。
  3. 定义F(n, k),也就是求和符合后的项。
  4. 调用zeil(F(n,k),k,n,N).      
  5. 结果出来老。收工回家。老婆孩子热炕头。该干嘛干嘛。       
 
而这一切,都归功于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.
                 

高兴

感动

同情

搞笑

难过

拍砖

支持
4

鲜花

刚表态过的朋友 (4 人)

发表评论 评论 (6 个评论)

1 回复 翰山 2011-11-13 07:19
还有这么强悍的文章?
回复 lambda 2011-11-13 10:33
翰山: 还有这么强悍的文章?
俺也是看了以后很是震撼,不得不转。
回复 柳絮闻雁 2011-11-13 22:41
很深奥!看不懂!
回复 lambda 2011-11-14 01:11
柳絮闻雁: 很深奥!看不懂!
俺也是当故事读
1 回复 柳絮闻雁 2011-11-14 01:51
lambda: 俺也是当故事读
编程序领域的
回复 liuxiaoyu 2012-1-13 11:16
我直接看晕了

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

关于本站 | 隐私政策 | 免责条款 | 版权声明 | 联络我们 | 刊登广告 | 转手机版 | APP下载

Copyright © 2001-2013 海外华人中文门户:倍可亲 (http://www.backchina.com) All Rights Reserved.

程序系统基于 Discuz! X3.1 商业版 优化 Discuz! © 2001-2013 Comsenz Inc. 更新:GMT+8, 2020-8-12 20:12

倍可亲服务器位于美国圣何塞、西雅图和达拉斯顶级数据中心,为更好服务全球网友特统一使用京港台时间

返回顶部