lambda

https://big5.backchina.com/?307321

做習題的境界(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理論問世樂。這套理論使得我們可以用程序找出求和公式的封閉解，或者證明一個求和公式沒有封閉解。端的威力巨大。有了這套理論，上述公式的求和變成下面的機械步驟：

到這個網址下載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.