離散數學與組合數學（第5版）

《離散數學與組合數學（第5版）》是2007年4月17日清華大學出版社出版的圖書，作者是Ralph Grimaldi。

基本介紹

• 中文名：離散數學與組合數學（第5版）
• 作者：Ralph Grimaldi
• 類別：參考書
• 原作品：DISCRETE MATHEMATICS
• 譯者：林永鋼等
• 出版社：清華大學出版社
• 出版時間：2007年4月17日
• 定價：98 元
• 裝幀：平裝
• ISBN：9787302144168

圖書簡介

離散數學是大學計算機科學與技術專業最重要的必修課程之一，是研究離散量的結構及其相互關係的數學學科，是現代數學的一個重要分支。由於計算機是一個離散結構，它只能處理離散的或者離散化了的數量關係，因此，無論是計算機科學本身，還是與計算機科學及其套用密切相關的現代科學研究領域，都面臨著如何為離散結果建立相應數學模型的問題；又如何將已用連續數量關係建立起來的數學模型進行離散化的問題，從而可由計算機加以處理。因此，隨著計算機科學的發展，離散數學作為計算機科學的一種數學工具，其作用顯得更加重要。同時，離散數學也是許多計算機科學與技術專業課程的基礎：其基本概念、基本理論和基本方法大量地套用在數據結構、作業系統、人工智慧、計算機網路、編譯原理、算法設計與分析等課程中。 組合數學是隨著計算機科學的蓬勃發展而完善起來的，並且已經成為一門極富生命力的數學分支。許多理論學科和套用學科向組合數學提出了大量的具有理論和實際意義的課題，促使它產生許多新理論，如區組設計、組合最佳化、組合算法等。同時，組合數學也是研究圖論、密碼學、編碼理論、算法複雜性的基本數學工具。

國內外所有高校的計算機科學與技術專業都開設了針對本科的離散數學與組合數學課程。R.P.Grimaldi教授具有極其豐富的教學理論和實踐經驗，他的這本《離散數學與組合數學》（DiscreteandCombinatorialMathematics）一書選材廣泛，敘述深入淺出，推理嚴謹，習題豐富，其英文版現已出到第5版，為美國、澳大利亞、加拿大、英格蘭、新加坡、南非、瑞典等國家的眾多大學採用。

圖書目錄

第一部分離散數學基礎/ 1

第1章計數基本原理/3

1.1加法原理與乘法原理/3

1.2排列/5

練習1.1和1.2/9

1.3組合： 二項式定理/12

練習1.3組合：二項式定理/21

1.4可重複組合/24

練習1.4可重複組合/31

1.5Catalan數（可選）/33

練習1.5Catalan數（可選）/36

1.6本章小結和歷史回顧/37

補充練習1/38

第2章邏輯基礎/42

2.1基本聯結詞與真值表/42

練習2.1基本聯結詞與真值表/48

2.2邏輯等價： 邏輯定律/49

練習2.2邏輯等價：邏輯定律/58

2.3邏輯蘊涵命題： 推理規則/59

練習2.3邏輯蘊涵命題：推理規則/74

2.4量詞的套用/76

練習2.4量詞的套用/87

2.5量詞、定義和定理證明/91

練習2.5量詞、定義和定理證明/101

2.6本章小結和歷史回顧/103

補充練習2/104

第3章集合論/107

3.1集合與子集/107

練習3.1集合與子集/117

3.2集合運算與集合論定律/119

練習3.2集合運算與集合論定律/128

3.3計數與文氏圖/129

練習3.3計數與文氏圖/131

3.4機率初步/132

練習3.4機率初步/136

3.5機率公理（可選）/137

練習3.5機率公理（可選）/144

3.6條件機率： 獨立（可選）/145

練習3.6條件機率：獨立（可選）/152

3.7離散隨機變數（可選）/154

練習3.7離散隨機變數（可選）/163

3.8本章小結和歷史回顧/164

補充練習3/167

第4章整數的性質： 數學歸納法/171

4.1良序原理： 數學歸納法/171

練習4.1良序原理：數學歸納法/183

4.2遞歸定義/185

練習4.2遞歸定義/193

4.3除法算法： 素數/195

練習4.3除法算法：素數/203

4.4最大公因子： 歐幾里德算法/204

練習4.4最大公因子：歐幾里德算法/209

4.5算術基本原理/210

練習4.5算術基本原理/213

4.6本章小結和歷史回顧/214

補充練習4/216

第5章關係和函式/219

5.1笛卡爾積和關係/220

練習5.1笛卡爾積和關係/223

5.2函式： 普通函式和一對一函式/223

練習5.2函式：普通函式和一對一函式/228

5.3到上函式： 第二類Stirling數/230

練習5.3到上函式：第二類Stirling數/235

5.4特殊函式/236

練習5.4特殊函式/240

5.5鴿巢原理/241

練習5.5鴿巢原理/244

5.6函式複合和逆函式/246

練習5.6函式複合和逆函式/253

5.7計算複雜性/255

練習5.7計算複雜性/258

5.8算法分析/259

練習5.8算法分析/264

5.9本章小結和歷史回顧/266

補充練習5/268

第6章語言： 有限狀態機/272

6.1語言： 字元串的集合理論/272

練習6.1語言：字元串的集合理論/280

6.2有限狀態機： 初步認識/281

練習6.2有限狀態機：初步認識/286

6.3有限狀態機： 再次認識/287

練習6.3有限狀態機：再次認識/292

6.4本章小結和歷史回顧/293

補充練習6/294

第7章關係： 再次認識/297

7.1再論關係： 關係的性質/297

練習7.1再論關係：關係的性質/302

7.2計算機識別： 零么矩陣和有向圖/303

練習7.2計算機識別：零麼矩陣和有向圖/311

7.3偏序： 哈斯圖/313

練習7.3偏序：哈斯圖/320

7.4等價關係與劃分/322

練習7.4等價關係與劃分/325

7.5有限狀態機： 最小化過程/326

練習7.5有限狀態機：最小化過程/330

7.6本章小結和歷史回顧/331

補充練習7/333

第二部分計數的深入主題/ 337

第8章容斥原理/3398.1容斥原理的概念/339

練習8.1容斥原理的概念/348

8.2容斥原理的推廣/350

練習8.2容斥原理的推廣/353

8.3錯排： 都不在正確位置/353

練習8.3錯排：都不在正確位置/354

8.4車多項式/355

8.5帶禁止位置的排列/357

練習8.4車多項式和8.5帶禁止位置的排列/360

8.6本章小結和歷史回顧/361

補充練習8/362

第9章生成函式/364

9.1一些啟發性例子/364

練習9.1一些啟發性例子/366

9.2定義與例子： 計算技巧/367

練習9.2定義與例子：計算技巧/378

9.3整數的拆分/380

練習9.3整數的拆分/382

9.4指數生成函式/383

練習9.4指數生成函式/386

9.5求和運算元/387

練習9.5求和運算元/388

9.6本章小結和歷史回顧/388

補充練習9/390

第10章遞推關係/392

10.1一階線性遞推關係/392

練習10.1一階線性遞推關係/399

10.2二階線性齊次常係數遞推關係/400

練習10.2二階線性齊次常係數遞推關係/410

10.3非齊次遞推關係/412

練習10.3非齊次遞推關係/421

10.4生成函式方法/422

練習10.4生成函式方法/426

10.5一種特殊的非線性遞推關係（可選）/427

練習10.5一種特殊的非線性遞推關係（可選）/431

10.6分治算法（可選）/434

練習10.6分治算法（可選）/440

10.7本章小結和歷史回顧/442

補充練習10/443

第三部分圖論及其套用/ 449

第11章圖論簡介/451

11.1定義和例子/451

練習11.1定義和例子/455

11.2子圖、補圖和圖的同構/457

練習11.2子圖、補圖和圖的同構/463

11.3頂點度： 歐拉跡和歐拉閉跡/465

練習11.3頂點度：歐拉跡和歐拉閉跡/470

11.4平面圖/473

練習11.4平面圖/483

11.5哈密頓路徑和哈密頓圈/486

練習11.5哈密頓路徑和哈密頓圈/491

11.6圖著色和色多項式/493

練習11.6圖著色和色多項式/497

11.7本章小結和歷史回顧/499

補充練習11/501

第12章樹/506

12.1定義、性質和例子/506

練習12.1定義、性質和例子/509

12.2根樹/511

練習12.2根樹/522

12.3樹和排序/525

練習12.3樹和排序/528

12.4帶權樹和前綴碼/528

練習12.4帶權樹和前綴碼/532

12.5重連通分支和關節點/532

練習12.5重連通分支和關節點/538

12.6本章小結和歷史回顧/539

補充練習12/540

第13章最最佳化和匹配/545

13.1Dijkstra最短路徑算法/545

練習13.1Dijkstra最短路徑算法/550

13.2最小生成樹： Kruskal算法和Prim算法/551

練習13.2最小生成樹：Kruskal算法和Prim算法/554

13.3運輸網路： 最大流最小割定理/555

練習13.3運輸網路：最大流最小割定理/566

13.4匹配定理/567

練習13.4匹配定理/573

13.5本章小結和歷史回顧/574

補充練習13/576

第四部分現代套用代數/ 579

第14章環和模算術/581

14.1環結構： 定義和例子/581

練習14.1環結構：定義和例子/585

14.2環性質和子結構/586

練習14.2環性質和子結構/590

14.3整數模n/592

練習14.3整數模n/600

14.4環同態與環同構/602

練習14.4環同態與環同構/608

14.5本章小結和歷史回顧/608

補充練習14/611

第15章布爾代數和開關函式/614

15.1開關函式： 析取範式與合取範式/614

練習15.1開關函式：析取範式與合取範式/620

15.2門網路： 乘積最小和與卡諾圖/621

練習15.2門網路: 乘積最小和與卡諾圖/628

15.3進一步的套用： 無關情況/629

練習15.3進一步的套用：無關情況/632

15.4布爾代數的結構（可選）/633

練習15.4布爾代數的結構（可選）/640

15.5本章小結和歷史回顧/640

補充練習15/641

第16章群、編碼理論和Polya計數法/644

16.1定義、例子和基本性質/644

練習16.1定義、例子和基本性質/649

16.2同態、同構和循環群/650

練習16.2同態、同構和循環群/653

16.3陪集和拉格朗日定理/653

練習16.3陪集和拉格朗日定理/654

16.4RSA密碼系統（可選）/655

練習16.4RSA密碼系統（可選）/657

16.5編碼理論基礎/657

練習16.5編碼理論基礎/661

16.6Hamming距/661

16.7奇偶校驗與生成矩陣/664

練習16.6Hamming距和16.7奇偶校驗與生成矩陣/667

16.8群碼： 利用陪集首項解碼/668

16.9Hamming矩陣/671

練習16.8群碼：利用陪集首項解碼和16.9Hamming矩陣/672

16.10計數與等價： Burnside定理/673

練習16.10計數與等價：Burnside定理/677

16.11循環指標/678

練習16.11循環指標/680

16.12方案清單： Polya計數法/681

練習16.12方案清單：Polya計數法/684

16.13本章小結和歷史回顧/685

補充練習16/687

第17章有限域和組合設計/690

17.1多項式環/690

練習17.1多項式環/696

17.2不可約多項式： 有限域/697

練習17.2不可約多項式：有限域/702

17.3拉丁方/704

練習17.3拉丁方/707

17.4有限幾何和仿射平面/708

練習17.4有限幾何和仿射平面/711

17.5區組設計和射影平面/711

練習17.5區組設計和射影平面/714

17.6本章小結和歷史回顧/715

補充練習17/717

附錄1指數函式與對數函式/719

附錄2矩陣、矩陣運算和行列式/727

附錄3可數集與不可數集/739

奇數練習答案與提示/749

中英文名詞對照表/870

ⅩⅦ記號