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