1、目錄摘要.11.組合數學概述.12.組合數學在生活中的應用.13.組合數學與計算機軟件.13.1信息時代的組合數學.23.2組合數學在計算機軟件的應用.23.3組合數學與計算機軟件的關系.23.4組合數學在國外軟件業的發展狀況.24 Ramsey 數在計算機科學中的應用.34.1Ramsey 定理和Ramsey 數.34.2信息檢索.3參考文獻.5組合數學在計算機中的應用摘要：介紹了組合數學的概念、起源與研究的主要內容,分析了組合數學的特點以及其在生活中的應用,闡述了組合數學與計算機軟件的聯系,并著重通過兩個例子說明了Ramsey 數在計算機科學的信息檢索中的重要應用。關鍵詞：組合數學;組合算

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

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

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

5、有很大應用價值的學科，它的數學原理就是組合設計。用組合設計的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟件。最近，德國一位著名組合數學家利用組合數學方法研究藥物結構，為制藥公司節省了大量的費用，引起了制藥業的關注。總之，組合數學無處不在，它的主要應用就是在各種復雜關系中找出最優的方案。所以組合數學完全可以看成是一門量化的關系學，一門量化了的運籌學，一門量化了的管理學。3：組合數學與計算機軟件隨著計算機網絡的發展，計算機的使用已經影響到了人們的工作，生活，學習，社會活動以及商業活動，而計算機的應用根本上是通過軟件來實現的。3.1信息時代的組合數學現代數學可以分為兩大類:一類

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

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

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

9、軟件和第二次開發，那么我們在應用軟件這個領域也會讓國外的企業搶去很大的市場。如果我們現在在信息技術的數學基礎上，大力支持和投入，那將是亡羊補牢，猶未為晚；只要我們能搶回信息技術的數學基地，那么我們還有可能在軟件產業的競爭中，扭轉局面，甚至反敗為勝。吳文俊院士開創和領導的數學機械化研究，為中國在信息技術領域占領了一個重要的陣地，有了雄厚的數學基礎，自然就有了軟件開發的競爭力。這樣的陣地多幾個，我們的軟件產業就會產生新的局面。值得注意的是，印度有很好的統計和組合數學基礎，這可能也是印度的軟件產業近幾年有很大發展的原因。3.4組合數學在國外軟件業的發展狀況縱觀全世界軟件產業的情況，易見一個奇特的現象

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

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

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

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

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