組合數學的歷史、方法及在生活中的應用.doc

組合數學的歷史、方法及在生活中的應用摘 要:組合數學從數千年前開始萌芽，經歷了著名的幻方問題和楊輝三角，直到萊布尼茨正式提出這一科學門類。組合數學也稱為組合分析或者組合學. 簡單地說, 組合數學是“按照一定的規(guī)則（模式)來安排一些離散個體”.組合數學在基礎理論方面和生活應用方面都發(fā)揮著越來越重要的作用, 如在計算機科學、編碼和密碼學、物理、化學、生物等學科中均有重要應用。本文從對組合數學歷史、基本內容和基本思想,結合具體的應用舉例介紹組合數學。關鍵詞:組合數學;歷史起源；基本方法；生活應用一、組合數學的歷史。組合數學是一個古老而又年輕的數學分支。最早起源于幻方問題。據傳說，大禹在4000多年前(2200B.C.)就觀察到神龜背上的幻方.1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。之后，希臘文寫在羊皮紙上的阿基米德手稿副本，距今約1000年。2003年，科學家借助現代科技手段初步破譯了這篇論文, 結論是這篇論文解決的是組合數學問題十四巧板。中國最早的組合數學理論可追溯到宋朝時期的”賈憲三角”, 后來被楊輝引用, 所以普遍稱之為”楊輝三角”, 這在西方是1654年由帕斯卡提出，但比中國晚了400多年。最后是組合數學的正式提出。1666年萊布尼茲所著論組合的藝術一書問世，這是組合數學的第一部專著。書中首次使用了組合論（Combinatorics）一詞。一切推理和發(fā)現，不管是否用語言描述，都能歸結為如數，字，聲，色這些元素經過某種組合的有序集合。2、 組合數學的基本內容與方法組合數學最早是同數論和概率論交叉在一起的.本世紀五十年代以來,特別是由于計算機科學的巨大發(fā)展,促使組合數學成為一支富有生命力的新興數學分支.與傳統的數學課程相比,組合數學研究的主要是一些離散事物之間所存在的某些數學關系,包括計數性問題、存在性問題、最優(yōu)化問題以及構造性問題等,其內容主要是枚舉和計數.組合學中研究最多的主要是計數問題,該問題通常出現在所有的數學分支之中.計算機科學通常需要研究有關算法的內容,就必須估計出算法所需的存儲單元和運算量,即分析算法的空間復雜性和時間復雜性.關于組合數學的基本方法有一下幾種：排列與組合、母函數與遞推關系、容斥原理、反演公式、鴿巢原理、Plya計數定理、區(qū)組設計與編碼理論等內容.僅僅知道方法是遠遠不夠的，組合數學的一些相關思想也是非常重要的，這里總結一下幾條。首先是組合對應法，在組合數學的學習中經常使用此法,可以毫不夸張的說貫穿于組合數學始終,并且該思想極易理解.設有一集合,要確定其元素個數,若直接求的元素個數則相對困難,我們可另找一集合,若在集與集間可建立一一對應的關系,并能確定中的元素個數,那么也能得到種元素的個數.其次是組合分析法，或稱組合解釋法,此法對組合數學的初學者來說相對重要一些,它與代數演算法有明顯的區(qū)別,其思想主要是給組合數以確定的現實意義,對提出的問題給以組合解釋.這種方法的特點是相對直觀,便于理解和記憶,富有啟發(fā)性,類似于我們在連續(xù)型數學學習中常說的“幾何意義”.第三是分類法在組合數學中使用頻率也較高.此方法的基本思想是:設有某一集合,根據某一準則(具體問題具體確定),將分成若干兩兩不交子集之并.最后，是放球模型法，此法是把很多組合問題用放球模型來模擬,盡管組合數學中處理問題的方法不帶一般性,但利用此法能解決不少組合問題. 3、 組合數學在生活中的應用 組合數學是十分貼近于人們的生活的，因此組合問題在生活中非常常見。這樣一個簡單的組合數學問題：一個船夫要把一只狼，一只羊和一棵白菜運過河。而當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個，問人怎樣才能把三者都運過河。下面介紹幾種組合數學中的著名問題。中國郵差問題：由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項式復雜度算法：先求出度為奇數的點，用匹配算法算出這些點間的連接方式，然后再用歐拉路徑算法求解。、 信息檢索是計算機科學中一個基本而又重要的問題。如何組織數據, 使用什么樣的查找方法, 對檢索的效率有很大的影響。所熟知的在有序表結構上的二分搜索算法是一種很有效的方法, 那么二分搜索是最好的算法嗎?Yao 4 利用Ramsey 數對這一問題作了肯定的回答。 地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？四色定理是一個著名的數學定理。它指出，如果將平面分成一些鄰接的區(qū)域，那么可以用不多于四種顏色來給這些區(qū)域染色，使得每兩個鄰接區(qū)域染的顏色都不一樣。盡管四色定理最初提出是和地圖染色工作有關，但四色定理本身對地圖著色工作并沒有特別的意義。人們發(fā)現，要證明寬松一點的“五定理”（即“只用五種顏色就能為所有地圖染色”）很容易，但四色問題卻出人意料地異常困難。曾經有許多人發(fā)表了四色問題的證明或反例，但都被證實是錯誤的。1977年，數學家Kenneth Appl和Wolfgang Haken借助電子計算機首次得到了一個完全的證明，四色問題也終于成為了四色定理。這是首個主要由計算機證明的定理。這個證明一開始并不為許多數學家接受，因為不少人認為這個證明無法用人手直接驗證。盡管隨著計算機的普及，數學界對計算機輔助證明更能接受，但仍有數學家對四色定理的證明存疑。 是否存在穩(wěn)定婚姻的問題：假如能找到兩對夫婦（如張（男）-李（女）和趙（男）-王（女），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那么這樣就可能有潛在的不穩(wěn)定性。組合數學的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩(wěn)定情況出現（當然這只是理論上的結論）。這種組合數學的方法卻有 一個實際的用途：美國的醫(yī)院在確定錄取住院醫(yī)生時，他們將考慮申請者的志愿的先后次序，同時也給申請排序。按這樣的 次序考慮出的總的方案將沒有醫(yī)院和申請者兩者同時后悔的情況。 實際上，高考學生的最后錄取方案也可以用這種方法。組合數學還可用于金融分析：組合數學還可用于金融分析，投資方案的確定，怎樣找出好的投資組合以降低投資風險。南開大學組合數學研究中心開發(fā)出了金沙股市風險分析系統現已投放市場，為短線投資者提供了有效的風險防范工具。 總之，組合數學無處不在，它的主要應用就是在各種復雜關系中找出最優(yōu)的方案。所以組合數學完全可以看成是一門量化的關系學，一門量化了的運籌學，一門量化了的管理學。參考資料 4 A. C. Yao. Should T ables Be Sorted J . ACM, 1981, 28.1 陳家.組合數學在計算機科學中的應用J.成都信息工程學院學報,2006(21):94-97.2 陳永川.話說組合數學J.科學中國人,2003(5):15-17.6 左光紀.組合數學的科學藝術表現J.青海