組合數(shù)學(xué)在計(jì)算機(jī)中的應(yīng)用

1、目錄摘要.11.組合數(shù)學(xué)概述.12.組合數(shù)學(xué)在生活中的應(yīng)用.13.組合數(shù)學(xué)與計(jì)算機(jī)軟件.13.1信息時(shí)代的組合數(shù)學(xué).23.2組合數(shù)學(xué)在計(jì)算機(jī)軟件的應(yīng)用.23.3組合數(shù)學(xué)與計(jì)算機(jī)軟件的關(guān)系.23.4組合數(shù)學(xué)在國(guó)外軟件業(yè)的發(fā)展?fàn)顩r.24 Ramsey 數(shù)在計(jì)算機(jī)科學(xué)中的應(yīng)用.34.1Ramsey 定理和Ramsey 數(shù).34.2信息檢索.3參考文獻(xiàn).5組合數(shù)學(xué)在計(jì)算機(jī)中的應(yīng)用摘要：介紹了組合數(shù)學(xué)的概念、起源與研究的主要內(nèi)容,分析了組合數(shù)學(xué)的特點(diǎn)以及其在生活中的應(yīng)用,闡述了組合數(shù)學(xué)與計(jì)算機(jī)軟件的聯(lián)系,并著重通過兩個(gè)例子說明了Ramsey 數(shù)在計(jì)算機(jī)科學(xué)的信息檢索中的重要應(yīng)用。關(guān)鍵詞：組合數(shù)學(xué);組合算

2、法;Ramsey 數(shù);信息檢索;1：組合數(shù)學(xué)概述組合數(shù)學(xué)，又稱為離散數(shù)學(xué)，但有時(shí)人們也把組合數(shù)學(xué)和圖論加在一起算成是離散數(shù)學(xué)。組合數(shù)學(xué)是計(jì)算機(jī)出現(xiàn)以后迅速發(fā)展起來的一門數(shù)學(xué)分支。計(jì)算機(jī)科學(xué)就是算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就是組合數(shù)學(xué)。組合數(shù)學(xué)的發(fā)展改變了傳統(tǒng)數(shù)學(xué)中分析和代數(shù)占統(tǒng)治地位的局面。現(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對(duì)象的，如分析、方程等，另一類就是研究離散對(duì)象的組合數(shù)學(xué)。組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科中也有重要的應(yīng)用，如計(jì)算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科

3、中均有重要應(yīng)用。微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。計(jì)算機(jī)之所以可以被稱為電腦，就是因?yàn)橛?jì)算機(jī)被人編寫了程序，而程序就是算法，在絕大多數(shù)情況下，計(jì)算機(jī)的算法是針對(duì)離散的對(duì)象，而不是在作數(shù)值計(jì)算。正是因?yàn)橛辛私M合算法才使人感到，計(jì)算機(jī)好象是有思維的。2：組合數(shù)學(xué)在生活中的應(yīng)用在日常生活中我們常常遇到組合數(shù)學(xué)的問題。如果你仔細(xì)留心一張世界地圖，你會(huì)發(fā)現(xiàn)用一種顏色對(duì)一個(gè)國(guó)家著色，那么一共只需要四種顏色就能保證每?jī)蓚€(gè)相鄰的國(guó)家的顏色不同。這樣的著色效果能使每一個(gè)國(guó)家都能清楚地顯示出來。但要證明這個(gè)結(jié)論確是一個(gè)著名的世界難題，最終借助計(jì)算

4、機(jī)才得以解決，最近人們才發(fā)現(xiàn)了一個(gè)更簡(jiǎn)單的證明。當(dāng)你裝一個(gè)箱子時(shí)，你會(huì)發(fā)現(xiàn)要使箱子盡可能裝滿不是一件很容易的事，你往往需要做些調(diào)整。從理論上講，裝箱問題是一個(gè)很難的組合數(shù)學(xué)問題，即使用計(jì)算機(jī)也是不容易解決的。航空調(diào)度和航班的設(shè)定也是組合數(shù)學(xué)的問題。怎樣確定各個(gè)航班以滿足 不同旅客轉(zhuǎn)機(jī)的需要，同時(shí)也使得每個(gè)機(jī)場(chǎng)的航班起落分布合理。此外，在一些航班有延誤等特殊情況下，怎樣作最合理的調(diào)整，這些都是 組合數(shù)學(xué)的問題。組合數(shù)學(xué)在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融分析等領(lǐng)域都有重要的應(yīng)用。在美國(guó)有一家用組合數(shù)學(xué)命名的公司，他們用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，這家公司辦得非常成功。此外，試驗(yàn)設(shè)計(jì)也是具

5、有很大應(yīng)用價(jià)值的學(xué)科，它的數(shù)學(xué)原理就是組合設(shè)計(jì)。用組合設(shè)計(jì)的方法解決工業(yè)界中的試驗(yàn)設(shè)計(jì)問題，在美國(guó)已有專門的公司開發(fā)這方面的軟件。最近，德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，引起了制藥業(yè)的關(guān)注?？傊M合數(shù)學(xué)無處不在，它的主要應(yīng)用就是在各種復(fù)雜關(guān)系中找出最優(yōu)的方案。所以組合數(shù)學(xué)完全可以看成是一門量化的關(guān)系學(xué)，一門量化了的運(yùn)籌學(xué)，一門量化了的管理學(xué)。3：組合數(shù)學(xué)與計(jì)算機(jī)軟件隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，計(jì)算機(jī)的使用已經(jīng)影響到了人們的工作，生活，學(xué)習(xí)，社會(huì)活動(dòng)以及商業(yè)活動(dòng)，而計(jì)算機(jī)的應(yīng)用根本上是通過軟件來實(shí)現(xiàn)的。3.1信息時(shí)代的組合數(shù)學(xué)現(xiàn)代數(shù)學(xué)可以分為兩大類:一類

6、是研究連續(xù)對(duì)象,如分析、方程等,另一類就是研究離散對(duì)象的組合數(shù)學(xué)。計(jì)算機(jī)科學(xué)就是算法的科學(xué),而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù),研究離散對(duì)象的科學(xué)恰恰就是組合數(shù)學(xué)。因此,在信息時(shí)代的今天,組合數(shù)學(xué)就是信息時(shí)代的數(shù)學(xué)。3.2組合數(shù)學(xué)在計(jì)算機(jī)軟件的應(yīng)用隨著計(jì)算機(jī)科學(xué)的發(fā)展,組合數(shù)學(xué)也在迅猛發(fā)展,而組合數(shù)學(xué)在理論方面的推進(jìn)也促進(jìn)計(jì)算機(jī)科學(xué)的發(fā)展。計(jì)算機(jī)軟件空前發(fā)展的今天要求有相應(yīng)的數(shù)學(xué)基礎(chǔ),組合數(shù)學(xué)作為大多數(shù)計(jì)算機(jī)軟件設(shè)計(jì)的理論基礎(chǔ),它的重要性也就不言而喻。組合數(shù)學(xué)在計(jì)算機(jī)方面的應(yīng)用極其廣泛。計(jì)算機(jī)軟件與各種算法的研究分不開,為了衡量一個(gè)算法的效率,必須估計(jì)用此算法解答具有給定長(zhǎng)的輸入(問題) 時(shí)需要

7、多少步(例如算術(shù)運(yùn)算、二進(jìn)制比較、程序調(diào)用等的次數(shù)) 。這要求對(duì)算法所需的計(jì)算量及存儲(chǔ)單元數(shù)進(jìn)行估算,這就是計(jì)數(shù)問題的內(nèi)容,而組合數(shù)學(xué)分析主要研究?jī)?nèi)容就是計(jì)數(shù)和枚舉的方法和理論。3.3組合數(shù)學(xué)與計(jì)算機(jī)軟件的關(guān)系我國(guó)在軟件上的落后，要說出根本的原因可能并不是很簡(jiǎn)單的事，除了技術(shù)和科學(xué)上的原因外，可能還跟我們的文化，管理水平，教育水平，思想素質(zhì)等諸多因素有關(guān)。除去這些人文因素以外，一個(gè)最根本的原因就是我國(guó)的信息技術(shù)的數(shù)學(xué)基礎(chǔ)十分薄弱，這個(gè)問題不解決，我們就難成為軟件強(qiáng)國(guó)。然而問題決不是這么簡(jiǎn)單，信息技術(shù)的發(fā)展已經(jīng)涉及到了很深的數(shù)學(xué)知識(shí)，而數(shù)學(xué)本身也已經(jīng)發(fā)展到了很深、很廣的程度并不是單憑幾個(gè)聰明的頭

8、腦去想想就行了，而更重要的是需要集體的合作和力量，就象軟件的開發(fā)需要多方面的人員的合作。美國(guó)的軟件之所以能領(lǐng)先，其關(guān)鍵就在于在數(shù)學(xué)基礎(chǔ)上他們有很強(qiáng)的實(shí)力，有很多杰出的人才。一般人可能會(huì)認(rèn)為數(shù)學(xué)是一門純粹的基礎(chǔ)科學(xué)，1+1的解決可能不會(huì)有任何實(shí)際的意義。如果真是這樣，一門純粹學(xué)科的發(fā)展落后幾年，甚至十年，關(guān)系也不大。然而中國(guó)的軟件產(chǎn)業(yè)的發(fā)展已向數(shù)學(xué)基礎(chǔ)提出了急切的需求：網(wǎng)絡(luò)算法和分析，信息壓縮，網(wǎng)絡(luò)安全，編碼技術(shù)，系統(tǒng)軟件，并行算法，數(shù)學(xué)機(jī)械化和計(jì)算機(jī)推理，等等。此外，與實(shí)際應(yīng)用有關(guān)的還有許多許多需要數(shù)學(xué)基礎(chǔ)的算法，如運(yùn)籌規(guī)劃，金融工程，計(jì)算機(jī)輔助設(shè)計(jì)等。如果我們的軟件產(chǎn)業(yè)還是把眼光一直盯在應(yīng)用

9、軟件和第二次開發(fā)，那么我們?cè)趹?yīng)用軟件這個(gè)領(lǐng)域也會(huì)讓國(guó)外的企業(yè)搶去很大的市場(chǎng)。如果我們現(xiàn)在在信息技術(shù)的數(shù)學(xué)基礎(chǔ)上，大力支持和投入，那將是亡羊補(bǔ)牢，猶未為晚；只要我們能搶回信息技術(shù)的數(shù)學(xué)基地，那么我們還有可能在軟件產(chǎn)業(yè)的競(jìng)爭(zhēng)中，扭轉(zhuǎn)局面，甚至反敗為勝。吳文俊院士開創(chuàng)和領(lǐng)導(dǎo)的數(shù)學(xué)機(jī)械化研究，為中國(guó)在信息技術(shù)領(lǐng)域占領(lǐng)了一個(gè)重要的陣地，有了雄厚的數(shù)學(xué)基礎(chǔ)，自然就有了軟件開發(fā)的競(jìng)爭(zhēng)力。這樣的陣地多幾個(gè)，我們的軟件產(chǎn)業(yè)就會(huì)產(chǎn)生新的局面。值得注意的是，印度有很好的統(tǒng)計(jì)和組合數(shù)學(xué)基礎(chǔ)，這可能也是印度的軟件產(chǎn)業(yè)近幾年有很大發(fā)展的原因。3.4組合數(shù)學(xué)在國(guó)外軟件業(yè)的發(fā)展?fàn)顩r縱觀全世界軟件產(chǎn)業(yè)的情況，易見一個(gè)奇特的現(xiàn)象

10、：美國(guó)處于絕對(duì)的壟斷地位。造成這種現(xiàn)象的一個(gè)根本的原因就是計(jì)算機(jī)科學(xué)在美國(guó)的飛速發(fā)展。當(dāng)今計(jì)算機(jī)科學(xué)界的最權(quán)威人士很多都是研究組合數(shù)學(xué)出身的。美國(guó)最重要的計(jì)算機(jī)科學(xué)系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的組合數(shù)學(xué)家。計(jì)算機(jī)科學(xué)通過對(duì)軟件產(chǎn)業(yè)的促進(jìn)，帶來了巨大的效益，這已是不爭(zhēng)之事實(shí)。組合數(shù)學(xué)在國(guó)外早已成為十分重要的學(xué)科，甚至可以說是計(jì)算機(jī)科學(xué)的基礎(chǔ)。一些大公司，如IBM，AT&T都有全世界最強(qiáng)的組合研究中心。Microsoft 的Bill Gates近來也在提倡和支持計(jì)算機(jī)科學(xué)的基礎(chǔ)研究。例如，Bell實(shí)驗(yàn)室的有關(guān)線性規(guī)劃算法的實(shí)現(xiàn)，以及有關(guān)

11、計(jì)算機(jī)網(wǎng)絡(luò)的算法，由于有明顯的商業(yè)價(jià)值，顯然是沒有對(duì)外公開的。美國(guó)已經(jīng)有一種趨勢(shì)，就是與新的算法有關(guān)的軟件是可以申請(qǐng)專利的。如果照這種趨勢(shì)發(fā)展，世界各國(guó)對(duì)組合數(shù)學(xué)和計(jì)算機(jī)算法的投入和競(jìng)爭(zhēng)必然日趨激烈。美國(guó)政府也成立了離散數(shù)學(xué)及理論計(jì)算機(jī)科學(xué)中心DIMACS（與Princeton大學(xué)，Rutgers大學(xué)，AT&T 聯(lián)合創(chuàng)辦的，設(shè)在Rutgers大學(xué)），該中心已是組合數(shù)學(xué)理論計(jì)算機(jī)科學(xué)的重要研究陣地。美國(guó)國(guó)家數(shù)學(xué)科學(xué)研究所（Mathematical Sciences Research Institute，由陳省身先生創(chuàng)立）在1997年選擇了組合數(shù)學(xué)作為研究專題，組織了為期一年的研究活動(dòng)。日本的NE

12、C公司還在美國(guó)的設(shè)立了研究中心，理論計(jì)算機(jī)科學(xué)和組合數(shù)學(xué)已是他們重要的研究課題，該中心主任R. Tarjan即是組合數(shù)學(xué)的權(quán)威。除上述以外，歐洲也在積極發(fā)展組合數(shù)學(xué)，英國(guó)、法國(guó)、德國(guó)、荷蘭、丹麥、奧地利、瑞典、意大利、西班牙等國(guó)家都建立了各種形式的組合數(shù)學(xué)研究中心。近幾年，南美國(guó)家也在積極推動(dòng)組合數(shù)學(xué)的研究。澳大利亞，新西蘭也組建了很強(qiáng)的組合數(shù)學(xué)研究機(jī)構(gòu)。值得一提的是亞洲的發(fā)達(dá)國(guó)家也十分重視組合數(shù)學(xué)的研究。日本有組合數(shù)學(xué)研究中心，并且從美國(guó)引進(jìn)人才，不僅支持日本國(guó)內(nèi)的研究，還出資支持美國(guó)的有關(guān)課題的研究，這樣使日本的組合數(shù)學(xué)這幾年的發(fā)展極為迅速。臺(tái)灣、香港兩地也從美國(guó)引進(jìn)人才，大力發(fā)展組合數(shù)學(xué)

13、。新加坡，韓國(guó)，馬來西亞也在積極推動(dòng)組合數(shù)學(xué)的研究和人才培養(yǎng)。臺(tái)灣的數(shù)學(xué)研究中心也正在考慮把組合數(shù)學(xué)作為重點(diǎn)方向來發(fā)展。世界各地對(duì)組合數(shù)學(xué)的如此鐘愛顯然是有原因的，那就是沒有組合數(shù)學(xué)就沒有計(jì)算機(jī)科學(xué)，沒有計(jì)算機(jī)軟件。4 Ramsey 數(shù)在計(jì)算機(jī)科學(xué)中的應(yīng)用4.1Ramsey 定理和Ramsey 數(shù)眾所周知,若有n +1 只鴿子同時(shí)飛進(jìn)n 個(gè)鴿巢中,則一定有某個(gè)鴿巢中至少飛進(jìn)兩只鴿,這就是有名的鴿巢原理(也叫抽屜原理) 。它非常簡(jiǎn)單,其正確性也顯而易見,但卻有很廣泛的應(yīng)用。鴿巢原理有如下重要的推廣:Ramsey 定理設(shè)q1 , q2 , , qn ; t 是正整數(shù),且qi=t ( i =1 ,

14、2 , , n) ,則存在最小的正整數(shù)r (記作r ( q1 ,q2 , qn ; t) 使得:對(duì)任意m 元集合s ,若m E r ,當(dāng)把S 的所有t 元子集放到n 個(gè)盒子里時(shí),那么存在某個(gè)i (1 =N ( n) 成立。據(jù)此定理,對(duì)充分大的m ,就信息檢索來說,用有序表結(jié)構(gòu)是最有效的方法。利用下述兩個(gè)引理,立即可得此定理的證明。引理1 若m =2 n -1 , n =2 ,對(duì)于按置換排序的表結(jié)構(gòu)。無論采用何種策略,在最壞情形下要確定x 是否在S 中至少需要log2 ( n +1 ) 次檢查。引理2 給定n ,存在數(shù)N ( n) 具有下述性質(zhì):若m =N ( n) ,且給定一個(gè)( m , n) 2表結(jié)構(gòu),則存在有2 n -1個(gè)鍵的集合K ,使得對(duì)應(yīng)于K 的n 元子集的表形成按置換排序的表結(jié)構(gòu)。參考文獻(xiàn)【1】楊驊飛. 組合數(shù)學(xué)及其應(yīng)用M. 北京:北京理工大學(xué)出版社,1992.【2】楊振生. 組合數(shù)學(xué)及其算法M. 合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,1997.【