標籤:離散對象

組合數學(combinatorial mathematics),又稱為離散數學。廣義的組合數學就是離散數學,狹義的組合數學是圖論、代數結構、數理邏輯等的總稱。但這只是不同學者在叫法上的區別。總之,組合數學是一門研究離散對象的科學。隨著計算機科學的日益發展,組合數學的重要性也日漸凸顯,因為計算機科學的核心內容是使用演算法處理離散數據。狹義的組合數學主要研究滿足一定條件的組態(也稱組合模型)的存在、計數以及構造等方面的問題。 組合數學的主要內容有組合計數、組合設計、組合矩陣、組合優化(最佳組合)等。

1簡介

現代數學可以分為兩大類:一類是研究連續對象的,如分析、方程等,另一類就是研究離散對象的組合數學。組合數學不僅在基礎數學研究中具有極其重要的地位,在其它的學科中也有重要的應用,如計算機科學、編碼和密碼學、物理、化學、生物等學科中均有重要應用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合數學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦,就是因為計算機被人編寫了程序,而程序就是演算法,在絕大多數情況下,計算機的演算法是針對離散的對象,而不是在作數值計算。正是因為有了組合演算法才使人感到,計算機好像是有思維的。
組合數學不僅在軟體技術中有重要的應用價值,在企業管理,交通規劃,戰爭指揮,金融分析等領域都有重要的應用。在美國有一家用組合數學命名的公司,他們用組合數學的方法來提高企業管理的效益,這家公司辦得非常成功。此外,試驗設計也是具有很大應用價值的學科,它的數學原理就是組合設計。用組合設計的方法解決工業界中的試驗設計問題,在美國已有專門的公司開發這方面的軟體。

2國外狀況

組合數學在國外早已成為十分重要的學科,甚至可以說是計算機科學的基礎。一些大公司,如IBM,AT&T都有全世界最強的組合研究中心。Microsoft 的Bill Gates近來也在提倡和支持計算機科學的基礎研究。例如,Bell實驗室的有關線性規劃演算法的實現,以及有關計算機網路的演算法,由於有明顯的商業價值,顯然是沒有對外公開的。美國已經有一種趨勢,就是與新的演算法有關的軟體是可以申請專利的。如果照這種趨勢發展,世界各國對組合數學和計算機演算法的投入和競爭必然日趨激烈。美國政府也成立了離散數學及理論計算機科學中心DIMACS(與Princeton大學,Rutgers大學,AT&T 聯合創辦的,設在Rutgers大學),該中心已是組合數學及理論計算機科學的重要研究陣地。美國國家數學科學研究所(Mathematical Sciences Research Institute,由陳省身先生創立)在1997年選擇了組合數學作為研究專題,組織了為期一年的研究活動。日本的NEC公司還在美國的設立了研究中心,理論計算機科學和組合數學已是他們重要的研究課題,該中心主任R. Tarjan即是組合數學的權威。美國重要的國家實際室(Los Alamos國家實驗室,以造出第一顆原子彈著稱於世),從曼哈頓計劃以來一直重視應用數學的研究,包括組合數學的研究。不僅如此,該實驗室最近還在積極充實組合數學方面的研究實力。美國另外一個重要的國家實驗室Sandia國家實驗室有一個專門研究組合數學和計算機科學的機構,主要從事組合編碼理論和密碼學的研究,在美國政府以及國際學術界都具有很高的地位。
由於生物學中的DNA的結構和生物現象與組合數學有密切的聯繫,各國對生物信息學的研究都很重視,這也是組合數學可以發揮作用的一個重要領域。由於DNA就是組合數學中的一個序列結構,美國科學院院士,近代組合數學的奠基人Rota教授預言,生物學中的組合問題將成為組合數學的一個前沿領域。
傳統的計算機演算法可以分為兩大類,一類是組合演算法,一類是數值演算法(包括計算數學和與處理各種信息數據有關的信息學)。近年來計算機演算法又多了一類:那就是符號計算演算法。吳文俊院士開創的機器證明方法就屬於符號計算,引起了國際上的高度評價,被稱為吳方法。而國際上還有專門的符號計算雜誌。符號演算法和吳方法跟代數組合學也有十分密切的聯繫。組合數學,數值計算(包括計算數學,科學計算,非線性科學,和與處理各種信息數據有關的信息學)和統計學可能是應用最廣的數學分支,而組合數學的價值甚至不亞於統計學和數值計算。由於數學機械化近年來的發展和在計算機科學中的重要性,把數學機械化,科學計算和組合數學組合起來,就可以說是中國信息產業的基礎。組合數學家H. Wilf和D. Zeilberger1998因為在組合恆等式的機械化證明方面的成果,獲得1998年美國數學會的Steele獎。
Thomson Science公司創刊的一份電子刊物《離散數學和理論計算機科學》即是一個很好的說明。它的內容涉及離散數學和計算機科學的眾多方面。由於計算機軟體的促進和需求,組合數學已成為一門既廣博又深奧的學科,需要很深的數學基礎,逐漸成為了數學的主流分支。
除上述以外,歐洲也在積極發展組合數學,英國、法國、德國、荷蘭、丹麥、奧地利、瑞典、義大利、西班牙等國家都建立了各種形式的組合數學研究中心。近幾年,南美國家也在積極推動組合數學的研究。澳大利亞,紐西蘭也組建了很強的組合數學研究機構。值得一提的是亞洲的發達國家也十分重視組合數學的研究。日本有組合數學研究中心,並且從美國引進人才,不僅支持日本國內的研究,還出資支持美國的有關課題的研究,這樣使日本的組合數學這幾年的發展極為迅速。台灣、香港兩地也從美國引進人才,大力發展組合數學。新加坡,韓國,馬來西亞也在積極推動組合數學的研究和人才培養。台灣的數學研究中心也正在考慮把組合數學作為重點方向來發展。

3花絮

中國郵差問題
由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次,怎樣行走走過的路程最短?這是一個NP完全問題。由中國組合數學家管梅谷教授提出,著名組合數學家,J. Edmonds和他的合作者給出了一個解答。
河洛圖
中國古代的河洛圖上記載了三階幻方,即把從一到九這九個數按三行三列的隊行排列,使得每行,每列,以及兩條對角線上的三個數之和都是一十五。組合數學中有許多象幻方這樣精巧的結構。1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。(題圖)
過河問題
在中小學的數學遊戲中,有這樣一個問題,一個船夫要把一隻狼,一隻羊和一棵白菜運過河。問題是當人不在場時,狼要吃羊,羊要吃白菜,而他的船每趟只能運其中的一個。他怎樣才能把三者都運過河呢?這就是一個很典型、很簡單的組合數學問題。
管理調度問題
我們還會遇到更複雜的調度和安排問題。例如,在生產原子彈的曼哈頓計劃中,涉及到很多工序,許多人員的安排,很多元件的生產,怎樣安排各種人員的工作,以及各種工序間的銜接,從而使整個工期的時間儘可能短?這些都是組合數學典型例子。又比如,假日飯店的管理中,也嚴格規定了有關的工序,如清潔工的第一步是換什麼,清洗什麼,第二步又做什麼,總之,他進出房間的次數應該最少。既然,這樣一個簡單的工作都需要講究工序,那麼一個複雜的工程就更不用說了。
鋪地磚問題
我們知道,用形狀相同的方型磚塊可以把一個地面鋪滿(不考慮邊緣的情況),但是如果用不同形狀,而又非方型的磚塊來鋪一個地面,能否鋪滿呢?這不僅是一個與實際相關的問題,也涉及到很深的組合數學問題。
基本信息
書名:
組合數學 (原書第4版) (2-1)
出 版 社:
機械工業出版社
作者:
Richard A.Brualdi
適用學科:
電子信息
書號:
978-7-111-15360-3
出版時間:
2005-02-01
定價:
45.00元
圖書目錄
出版者的話
專家指導委員會
譯者序
前言
第1章 什麼是組合數學
1.1 例:棋盤的完美覆蓋
1.2 例:切割立方體
1.3 例:幻方
1.4 例:四色問題
1.5 例:36軍官問題
1.6 例:最短路徑問題
1.7 例:nim取子遊戲
1.8 練習題
第2章 鴿巢原理
2.1 鴿巢原理:簡單形式
2.2 鴿巢原理:加強形式
2.3 ramsey定理
2.4 練習題
第3章 排列與組合
3.1 四個基本的計數原理
.3.2 集合的排列
3.3 集合的組合
3.4 多重集的排列
3.5 多重集的組合
3.6 練習題
第4章 生成排列和組合
4.1 生成排列
4.2 排列中的逆序
4.3 生成組合
4.4 生成卜組合
4.5 偏序和等價關係
4.6 練習題
第5章 二項式係數
5.1 pascal公式
5.2 二項式定理
5.3 一些恆等式
5.4 二項式係數的單峰性
5.5 多項式定理
5.6 牛頓二項式定理
5.7 再論偏序集
5.8 練習題
第6章 容斥原理及應用
6.1 容斥原理
6.2 具有重複的組合
6.3 錯位排列
6.4 帶有禁止位置的排列
6.5 另外的禁排位置問題
6.6 莫比烏斯反演
6.7 練習題
第7章 遞推關係和生成函數
7.1 一些數列
7.2 線性齊次遞推關係
7.3 非齊次遞推關係
7.4 生成函數
7.5 遞歸和生成函數
7.6 一個幾何的例子
7.7 指數生成函數
7.8 練習題
第8章 特殊計數序列
8.1 catalan數
8.2 差分序列和stirling數
8.3 分拆數
8.4 一個幾何問題
8.5 格路徑和schroder數
8.6 練習題
第9章 二分圖中的匹配
9.1 一般問題表述
9.2 匹配
9.3 互異代表系統
9.4 穩定婚姻
9.5 練習題
第10章 組合設計
10.1 模運算
10.2 區組設計
10.3 steiner三元系統
10.4 拉丁方
10.5 練習題
第11章 圖論導引
11.1 基本性質
11.2 歐拉跡
11.3 hamilton路徑和hamilton圈
11.4 二分多重圖
11.5 樹
11.6 shannon開關遊戲
11.7 再論樹
11.8 練習題
第12章 有向圖及網路
12.1 有向圖
12.2 網路
12.3 練習題
第13章 再論圖
13.1 色數
13.2 平面和平面圖
13.3 五色定理
13.4 獨立數和團數
13.5 連通性
13.6 練習題
第14章 polya計數法
14.1 置換群與對稱群
14.2 burnside定理
14.3 polya計數公式
14.4 練習題
練題的答案與提示
參考文獻
索引

4其他信息

圖書簡介
本書是作者多年教學和研究成果的結晶,系統地研究了組合計數、組合設計以及相關數學理論。全書分為10章: 集合與函數,排列組合與多項式定理,整除性理論,數論函數,不定方程,同餘式,線性遞歸方程與母函數,鴿巢原理和Ramsey(拉姆齊)定理,Burnside(伯恩賽德)引理和Pólya(波利亞)定理,相異代表組和區組設計。
本書可以作為計算機科學與技術、數學、密碼學和其他相關專業研究生和本科生的教材使用,也可作為廣大師生和工程技術人員的自學用書或參考書。

目錄

第1章集合與函數
1.1集合論基礎
1.1.1集合的基本概念
1.1.2集合的代數運算及性質
1.1.3集合的運算性質
1.2函數、置換的循環分解
1.2.1函數的基本概念和一般性質
1.2.2置換的循環分解
1.3集合的基數、對合映射不動點定理
1.4集合上的二元關係
1.4.1二元關係的基本概念
1.4.2幾種特殊的簡單二元關係
1.4.3等價關係、商集
1.5容斥原理及應用
1.5.1容斥原理
1.5.2錯位排列問題
1.5.3容斥原理應用舉例
1.6Abel恆等式
1.7習題
第2章排列組合與多項式定理
2.1排列組合及其性質
2.1.1無重複排列和無限可重複排列
2.1.2無重複組合及其性質、多項式反演定理
2.1.3無重複有序分組、無重複無序分組
2.1.4無限可重複分組、無限可重複組合、多項式定理
2.1.5有限可重複組合與有限可重複排列
2.2排列組合應用舉例
2.3Stirling公式
2.3.1Wallis公式
2.3.2Stirling公式
2.4習題
第3章整除性理論
3.1整數的整除性
3.2最大公約數和最小公倍數
3.3連分數
3.3.1實數的連分數表示
3.3.2實數的近似分數
3.3.3近似分數的既約性
*3.3.4近似分數的誤差估計
3.3.5整數線性組合ax-by=1的生成
3.4素數、二平方定理、算術基本定理
3.5習題
第4章數論函數
4.1[x]與{x}
4.2積性函數
4.3因子數τ(n)與因子和S(n)
4.4Euler函數?(n)
4.5M?bius函數和M?bius反演定理
4.5.1M?bius函數及其性質
4.5.2M?bius反演定理
4.5.3圓排列問題
4.6習題
第5章不定方程
5.1二元一次不定方程
5.2三元一次不定方程
5.3勾股數定理
5.4習題
第6章同餘式
6.1同餘式的定義與性質
6.2完全剩餘系和縮剩餘系
6.3一元一次同餘方程
6.4一元一次同餘方程和方程組、中國剩餘定理
*6.5一元多項式同餘方程
6.6習題
第7章線性遞歸方程與母函數
7.1遞歸方程
7.1.1線性遞歸方程解的結構、降階定理
7.1.2常係數齊次線性遞歸方程的通解
7.1.3常係數非齊次線性遞歸方程的求解
7.1.4線性遞歸方程求解舉例
7.2Fibonacci數列
7.2.1Fibonacci問題的求解
7.2.2Fibonacci數列的性質
7.2.3Fibonacci數列在優選法中的應用
7.3母函數及其性質
7.3.1母函數的定義
7.3.2母函數的一般性質
7.4錯位排列和禁位排列
7.4.1錯位排列問題
*7.4.2棋盤多項式與禁位排列
*7.5正整數分拆和Ferrers圖
7.5.1正整數分拆
7.5.2Ferrers圖
7.6Stirling數
7.6.1第一類Stirling數
7.6.2第二類Stirling數
7.6.3Stirling反演定理
7.7Catalan數
7.8Bernoulli數
7.9習題
第8章鴿巢原理和Ramsey定理
8.1鴿巢原理
*8.2無向完全圖的著色問題
8.3Ramsey定理
*8.4Ramsey數的性質
8.5習題
第9章Burnside引理和Pólya定理
9.1群的基本知識
9.1.1半群、亞群、元素的階
9.1.2群、陪集、Lagrange定理
9.2Burnside引理和Pólya定理
9.2.1Burnside引理
9.2.2簡化的Pólya定理
*9.2.3Pólya基本定理
9.3習題
第10章相異代表組和區組設計
10.1相異代表組
10.2公共代表組
10.3完全區組設計與拉丁方
10.4有限域基礎
10.5正交拉丁方
*10.6均衡不完全區組設計(BIBD)
10.6.1BIBD的概念
10.6.2三連組系
10.6.3對稱BIBD
10.6.4由對稱BIBD構造其他BIBD
10.7Hadamard矩陣
10.8習題
參考文獻
上一篇[影響]    下一篇 [《1812序曲》]

相關評論

同義詞:暫無同義詞