有人要,就貼一下吧.
具體數(shù)學(xué)之我見
SA02011108 孫偉峰 研究方向；移動計算及網(wǎng)絡(luò)
0． 序
本學(xué)期上了課程《具體數(shù)學(xué)》(－Graham and Knuth[1]）。雖說上課時候兢兢業(yè)業(yè)，課后完成習(xí)題，但是到目前為止還沒有找到特別好的點進行深入的研究，誠惶誠恐，暫且寫一些對該課程的感受及粗淺的想法，希望能夠“蒙混過關(guān)”。
1． Graham and Knuth
對Ronald L.Graham并不是特別了解，但是對高納德（Donald.E.Knuth）卻是崇敬有加。TAOCP（ ）[2,3,4] 的三卷，排版軟件TeX，Metafont， KMP算法，36歲獲得圖靈獎，應(yīng)該說是數(shù)學(xué)界和計算機界舉足輕重的人物。有感于他的思維，是如此的發(fā)散跳躍，而且經(jīng)常能夠聯(lián)系一些看似毫不相干的事情， 一個小小的游戲，都會研究的特別深入，且善于從平常事件中找到自認為有意思的事情進行分析研究。比如說書中的整函數(shù)部分的輪盤賭問題，擲骰子問題，以及他 最喜歡的ladders游戲問題[5]等。也許就是要幻想吧，科學(xué)都是想出來的，據(jù)說數(shù)理邏輯這門學(xué)科，就是一個哲學(xué)家在無所事事的時候，想出了這么一套 謂詞表示方法的離散數(shù)學(xué)的一個分支。拓展知識面，培養(yǎng)發(fā)散性思維，將一個領(lǐng)域中的解決方法應(yīng)用到另外一個領(lǐng)域中，也許會取得意想不到的效果。比如說現(xiàn)在我 們實驗室的一個自然科學(xué)基金項目：市場經(jīng)濟模型的資源調(diào)度，就是要將經(jīng)濟學(xué)之中那些經(jīng)過時間、社會考驗的成熟的定律應(yīng)用到網(wǎng)格的資源調(diào)度上面來。在基于角 色的資源調(diào)度中，每個網(wǎng)格節(jié)點就是一個市場的實體，具有提供資源和請求資源的功能，而各個實體之間的行為、關(guān)系，則可通過經(jīng)濟學(xué)中的消費者和資源提供者之 間的關(guān)系來進行操作，尋找網(wǎng)格資源當(dāng)中的價值規(guī)律。在網(wǎng)絡(luò)研究中，TCP的慢啟動算法也廣泛得到了應(yīng)用，比如說QoS調(diào)度中尋找最大可獲得服務(wù)質(zhì)量的算 法，在無線網(wǎng)絡(luò)鏈路層中根據(jù)擁塞情況對發(fā)包進行調(diào)整的發(fā)包規(guī)則等。所以說，要有象Knuth一樣的思維，兼容包并，從實際到理論，才也許會起到意想不到的 效果。
2． 具體數(shù)學(xué)—計算機科學(xué)基礎(chǔ)
2.1 什么是具體數(shù)學(xué)
在計算機系的學(xué)習(xí)當(dāng)中，數(shù)學(xué)相關(guān)的課程我們學(xué)了很多。從大一時候的高等數(shù)學(xué)導(dǎo)論，到后面的離散數(shù)學(xué)系列，包括代數(shù)結(jié)構(gòu)、圖論、數(shù)理邏輯、概率論和數(shù)理統(tǒng) 計、隨機函數(shù)、組合數(shù)學(xué)，以及線形代數(shù)、數(shù)值分析、復(fù)變函數(shù)、數(shù)理方程等，都是從理論上去闡述數(shù)學(xué)的意義或者是數(shù)學(xué)和計算機的理論關(guān)系。當(dāng)然，圖論等課程 中也涉及到一些具體算法的問題，如TSP問題、著色問題等。但是為博士生開設(shè)的具體數(shù)學(xué)課程，想要解決的是對于具體的問題，如何運用抽象的方法去解決，也 就是理論如何應(yīng)用于實際的問題。也有這樣一種說法，即具體數(shù)學(xué)是計算機科學(xué)的基礎(chǔ)，因為計算機學(xué)科就是從數(shù)學(xué)分支出來的Engineering。具體數(shù)學(xué) 本身是對TAOCP第一部的擴展，比較注重在計算機科學(xué)領(lǐng)域內(nèi)數(shù)學(xué)知識的應(yīng)用，包括離散數(shù)學(xué)和連續(xù)數(shù)學(xué)都有涉及，這點在書的結(jié)構(gòu)上就能看的出來。簡單來 說，具體數(shù)學(xué)這們課程就是講數(shù)學(xué)在計算機學(xué)中如何應(yīng)用，在計算機學(xué)中如何用數(shù)學(xué)來解決問題，是數(shù)學(xué)和計算機學(xué)的結(jié)合。
2.2 對本書的理解
從內(nèi)容上來說，大部分還是熟悉的。遞歸、求和、整函數(shù)、數(shù)論、二項系數(shù)、離散概率都是在以前的課程中曾經(jīng)涉及過的，特殊數(shù)在組合數(shù)學(xué)中有過組合意義上的解 釋，母函數(shù)也有一些接觸，而漸進的一些概念，是算法課程中的復(fù)雜度分析要應(yīng)用到的。但是從講的形式來說，卻是很不一樣的。
2.2.1 遞歸
在對遞歸問題的解釋沒有從概念上講什么是遞歸，也不是側(cè)重寫遞歸方程的方法，而是通過三個具體的問題漢諾塔、直線對平面的劃分和Josephus三個問題來對遞歸進行感性的解釋。
Josephus問題是個經(jīng)典問題，在計算機中用程序解決這個問題的方法也有多種，但是該書中從兩個角度教我們?nèi)绾螐睦碚撋仙A，并且對算法進行改進。從 最簡單的逢二殺一Josephus問題，對應(yīng)到了2進制表示，并且發(fā)現(xiàn)這個問題的有趣的性質(zhì)，從而對Josephus問題的求解只通過簡單的二進制移位操 作就可以實現(xiàn)。后來又將該問題擴展到不同進制Josephus方程類的一般形式。因為問題涉及到的域是整數(shù)域，在整函數(shù)部分，描述了編程解決 Josephus問題，并對算法進行了簡化，用比較簡單的循環(huán)語句就較快的解決逢三殺一的Josephus問題。算法對逢二殺一的Josephus問題， 應(yīng)用移位操作，會更快的得到結(jié)果，這是具體編程的問題了。Josephus問題在數(shù)學(xué)上的解決，在計算機學(xué)科上涉及到了2進制和算法編寫的問題。這對我們 來說是一個工具，問題是如何構(gòu)造具體問題使之對應(yīng)于Josephus問題，Josephus的應(yīng)用，書上并沒有提到。
在令牌環(huán)網(wǎng)絡(luò)中某些條件下的尋路是可以用到Josephus問題的：對令牌的分發(fā)問題，在N節(jié)點的令牌環(huán)網(wǎng)絡(luò)中，若m個相鄰的節(jié)點屬于一組，我們所希望的 是各個組輪流一個節(jié)點受到服務(wù)，這就演化為逢m殺一的Josephus問題。對有此種要求的網(wǎng)絡(luò)，要設(shè)計一個令牌的分發(fā)算法，并對令牌進行修改。在令牌后 附加計算Josephus數(shù)所需要的n值和N值，每一個節(jié)點在處理的時候要識別改造過后的令牌，并在受到服務(wù)后計算下一個n值和N值，保持 Josephus數(shù)在一個計數(shù)器中，每經(jīng)過一個節(jié)點，計數(shù)器減1，只有當(dāng)計數(shù)器為0時，節(jié)點才能獲得令牌。這樣，保證了下一個能使用令牌的節(jié)點是 Josephus問題中的解。另外，因為令牌要循環(huán)進行分發(fā)，在Josephus問題到了最后一個后，要對令牌附加消息中的n和N進行重新賦值。如果不用 如此的處理方法，只在令牌上設(shè)置一個計數(shù)器，每隔m個節(jié)點服務(wù)一次，會出現(xiàn)有的節(jié)點獲得不了服務(wù)的問題，要解決這個問題，就需要在節(jié)點上也設(shè)置一個計數(shù) 器，受過一次服務(wù)，計數(shù)器加1。以初始值0為例，每個節(jié)點的計數(shù)器都為0，受過一次服務(wù)的節(jié)點中的計數(shù)器變?yōu)?，則該節(jié)點再收到令牌，則不接受這個令牌， 把令牌傳遞給后繼節(jié)點。這同樣也有一個問題，即當(dāng)所有節(jié)點都受到過一次服務(wù)，計數(shù)器都為1之后，如何讓節(jié)點得知接受令牌，讓計數(shù)器從1變?yōu)?。這個新的問 題就又要求令牌進一步判斷是不是所有的節(jié)點都服務(wù)到一次，有會增加復(fù)雜度。用Josephus數(shù)解決該問題的方法有如下缺點：擴展令牌，增大令牌的負荷； 令牌環(huán)中的節(jié)點要進行計算（雖然計算量不大）；最大的缺點則是必須知道令牌環(huán)上所有節(jié)點的數(shù)目N。如果不知道N，而以一個大的數(shù)N’代替N，那么將出現(xiàn)什 么結(jié)果呢？是不是能夠找到一個大素數(shù)N’,使得用N’來代替N，同樣能夠遍歷到所有的節(jié)點呢？現(xiàn)在的感覺是不行，因為對N’個節(jié)點，總可以有N’-N=m －1,這樣，編號為1的節(jié)點在第二輪就又被重新編號，而這個節(jié)點，應(yīng)該是已經(jīng)被殺死過的。
在對等網(wǎng)絡(luò)的P2P研究中，有一種叫Pastry網(wǎng)絡(luò)，是根據(jù)對節(jié)點編號進行Hash形成一個環(huán)，是否用Josephus數(shù)會得到更好DHT呢？這種 Hash方法，在對分組提供服務(wù)的情況下，可以快速的找到所要尋找的那一類資源，但是這種每類節(jié)點數(shù)目都大致相同的實際服務(wù)，好像還是太少了些。感覺 Josephus數(shù)在實際網(wǎng)絡(luò)應(yīng)用中最大的問題，就是需要確切的知道初始N值。
2.2.2 和
本章新的知識是離散數(shù)域有限演算的部分，引入了新的算子，和實數(shù)域的有限演算對應(yīng)起來，引入了差分算子對應(yīng)微分算子，不定和算子來對應(yīng)積分算子。為了對應(yīng) 有限域多項式求導(dǎo)的規(guī)律，還引入了下降階乘冪和上升階乘冪，并擴展到負數(shù)。對分部積分的規(guī)律也有所對應(yīng)?？梢娬麛?shù)域和實數(shù)域的運算是有對應(yīng)的。要找到規(guī)律 進行擴展，并創(chuàng)造新的一套對應(yīng)規(guī)則，重要的是觀察和尋找令人滿意的特性。此部分中，為什么引入階層冪、如何引入、以及階層冪在負數(shù)上的擴展方式，給了我們 很好的啟發(fā)。
2.2.3 整函數(shù)和數(shù)論
關(guān)于整函數(shù)和模的介紹并不難，但是通過輪盤賭的實際例子，才讓我知道如何實際應(yīng)用區(qū)間、通過上整下整的范圍轉(zhuǎn)換來計算實際問題。以前確實并沒有體會到這種“學(xué)以致用”。
數(shù)論部分中涉及到Stern-Brocot數(shù)，本身該數(shù)是構(gòu)造有理數(shù)的一種手段，但是這種樹的有趣之處是可以用LR兩種操作的字符串來表示，L和R分別對 應(yīng)由單位矩陣經(jīng)過一次簡單運算的2×2矩陣，這同編譯中的詞法分析仿佛有著一定的聯(lián)系。每一個字符串，經(jīng)過詞法分析（比如LR(0)分析），可以對應(yīng)著一 系列的LR操作，再將此串對應(yīng)Stern-Brocot的LR序列，一個串就可以存儲為一個數(shù)，這在壓縮上是有用的。在串的匹配方面，也許也存在著特殊的 形式。
在介紹莫比烏斯函數(shù)的時候，有一個反演定律，課堂上老師曾經(jīng)說過可以對應(yīng)于網(wǎng)絡(luò)流量。感覺還不是很清楚，如果將節(jié)點的流入定義為1，流出定義為－1，沒有 流量定義為0，這樣通過控制節(jié)點發(fā)送接受數(shù)據(jù)，可以得到莫比烏斯函數(shù)序列，并利用莫比烏斯函數(shù)的反演原理，也許可以觀察到流量的某些特征。再比如在檢測網(wǎng) 絡(luò)病毒時，如果知道病毒的特征碼，并且這段特征碼很長，如果能夠通過反演找到較短的對應(yīng)序列，也許會減輕測量檢測的負擔(dān)。同樣是網(wǎng)絡(luò)安全方面的問題，d作 為密鑰，將一段數(shù)據(jù)分成若干小部分加密，解密的時候就通過莫比烏斯函數(shù)進行解開，也許會增加可靠性。至于將反演定理中的g（m）用特殊函數(shù)進行研究，要看 具體應(yīng)用是否有對應(yīng)某個具體函數(shù)。
2.2.4 二項系數(shù)和特殊數(shù)
二項系數(shù)是我們久已熟悉的東西，但是沒有感覺到和計算機的緊密聯(lián)系，倒是書中提到合流超幾何級數(shù)在工程中有著重要的應(yīng)用，也許是和計算相關(guān)的東西吧，不太明白，看來以后還要好好理解才是。
特殊數(shù)中有一些是組合數(shù)學(xué)中涉及到的，甚至Stirling數(shù)，Euler數(shù)就是從組合意義上得來的有趣的數(shù)列。調(diào)和數(shù)在物理上得到的特別廣的應(yīng)用，書上 也舉了一些例子。同樣，F(xiàn)ibonacci數(shù)列也是特別有用的數(shù)列之一，課上老師也提到了廣義Fibonacci數(shù)，這種Fibonacci數(shù)可以在組播 算法中得到應(yīng)用，對組播產(chǎn)生的包進行理論分析，得出組播中的包在網(wǎng)絡(luò)中的分布及數(shù)目、對網(wǎng)絡(luò)的影響，可以在組播的算法上給出指導(dǎo)。
2.2.5 母函數(shù)、離散概率和漸進
母函數(shù)，是解題的方法，是解題的一種工具。關(guān)鍵是如何找出對應(yīng)的特殊序列。
和以前學(xué)過的離散概率不同，本書的離散概率側(cè)重于用概率母函數(shù)解決問題，并用擲硬幣的例子來詳細說明。但是感覺和計算機相關(guān)最多的是式（8.73）的推 導(dǎo)，書上卻沒有提到。如果時間充足，應(yīng)該仔細講一下，如何發(fā)現(xiàn)這么“有趣”的公式，而Knuth就在這方面有很強的能力，著名的KMP算法，就可以說明這 一點。
漸進是算法分析中的重要部分，特別在分析時間復(fù)雜度和空間復(fù)雜度的時候。我們在寫科技論文時，對提出模型的分析也是要用到漸進來簡化的。在CMU博士的面 試題中，經(jīng)常會出現(xiàn)Back-of-Envelope Calculation的問題，也就是沒有任何信息的情況下，進行數(shù)量級估算，也可以說是一種粗粒度的漸進。
3． 總結(jié)和建議
學(xué)過了具體數(shù)學(xué)的課程，知道了數(shù)學(xué)對計算機學(xué)科的指導(dǎo)意義，體會到了深層次研究的復(fù)雜，更是覺得前人們思想的深邃以及科學(xué)研究的從淺入深。本篇文章總結(jié)了一下自己對本課程的看法以及一些不成熟的想法，希望以后能發(fā)現(xiàn)新的研究點或完善上面的一些基本想法。
個人感覺，自己欠缺的是如何建模的問題，還有就是如何將這些數(shù)學(xué)公式應(yīng)用到實際當(dāng)中的問題。雖然書上有一些例子，但是感覺還是不夠多，而用數(shù)學(xué)手段對數(shù)學(xué) 公式的證明描述，對我們來說顯得太多了。如果說以前沒有接觸到這些數(shù)學(xué)知識，這種組織會對數(shù)學(xué)和計算機水平都有提高。而作為面向博士生的課程，感覺還是應(yīng) 該多側(cè)重于應(yīng)用的例子，模型的建立方面，至少在我來說，我是想了解這些東西的。
文中的錯誤之處，請老師批評指正。
參考文獻
[1] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik; Concrete Mathematics, Second Edition, 1994
[2] Donald E. Knuth, The Art of Computer Programming, Vol 1 : Fundamental Algorithms, Addison-Wesley, 1973
[3] Donald E. Knuth, The Art of Computer Programming, Vol 2 : Seminumerical Algorithms, Addison-Wesley, 1973
[4] Donald E. Knuth, The Art of Computer Programming, Vol 3 : Sorting and searching, Addison-Wesley, 1973
[5] Donald E. Knuth, The Stanford GraphBase : A Platform for Combinatorial Computing, Addison-Wesley, 1993