本書充分考慮到初學者的需要，內容、例題、習題都經過精心的挑選和組織，講解細致，循序漸進，實例貼近日常生活或計算機應用。本書注重算法，且算法描述獨立于某種具體的編程語言。教師可根據(jù)學生的層次和興趣來靈活拓展和組織講解內容。
如今，數(shù)學的應用越來越多地涉及離散而非連續(xù)的模型，其主要原因是現(xiàn)代社會越來越多地用到計算機。本書適用于一學期的離散數(shù)學入門課程。
預備知識
雖然按照本書講授的課程只要求很少的數(shù)學預備知識，但還是要求學生至少達到修讀過兩年高中數(shù)學所應具有的水平，包括解題和運算的技能以及抽象思維的能力。
方法
本書強調算法并以此貫穿全書。算法用文字表述，不需要具體編程語言的知識。
主題的選擇
本書主題的選擇基于多個專業(yè)組織的建議，包括MAA（美國數(shù)學協(xié)會）一年級和二年級離散數(shù)學課程制定工作組的建議、NCTM（National Council of Teachers of Mathematics，美國數(shù)學教師理事會）的“學校數(shù)學教育的原則與標準”和CBMS（Conference Board of the Mathematical Sciences，美國數(shù)學科學聯(lián)合會）對數(shù)學教學的建議等。
靈活性
雖然本書是針對一學期的課程設計的，但是本書所包含的材料多于一個學期所能覆蓋的內容。因此，教師可以根據(jù)學生的特定需求和興趣方便地選擇主題。本書以前的版本在從計算機科學專業(yè)的一年級課程到數(shù)學專業(yè)的高年級課程等許多課程中用過，并得到了良好的反映�，F(xiàn)在的這個版本仍然為教師提供了靈活性，以適用于各種不同專業(yè)學生的課程。
第5版的變動
第5版的主要變動是新增了一章—第3章，討論同余、歐幾里得算法及相關的數(shù)論方面的內容、RSA公鑰密碼技術、檢錯碼和糾錯碼（包括矩陣碼）。本書其余內容與這一章不相關，所以可由教師根據(jù)需要進行取舍。學習矩陣碼的內容要求熟悉矩陣，所以在學習編碼理論這一章之前，不熟悉矩陣的學生需要先閱讀附錄B。（詳見下面的“章節(jié)獨立性”和“課程設置建議”。）
另外，新版本在表述的清晰性方面有所改進，對離散數(shù)學的新進展也給予了關注。
習題
本書的習題安排錯落有致，靈活性強。每節(jié)后都有大量簡單的計算題和算法題，其中大多數(shù)習題有助于學生針對離散數(shù)學的概念和算法進行全面練習，這對數(shù)學基礎較弱的學生尤其重要；另一些習題拓展了正文中的材料，或者引入了正文中未論述過的新概念。帶*號的習題是更具挑戰(zhàn)性的問題。教師應根據(jù)課程和學生水平從中挑選。奇數(shù)號計算題的答案附在本書末尾。在每一章的末尾，有一組補充習題，用來溫習各章最重要的概念和技術，以及探討正文中未討論的新概念。
章節(jié)獨立性
在采用本書進行教學時，各章的順序可以靈活地安排。下圖顯示了各章的依賴關系。其中，虛線表示第6章僅與第4章的前幾節(jié)內容相關。本書只假定讀者具有高中幾何課程對于邏輯與證明的熟練程度，而對那些偏好更形式化處理的讀者提供了一個附錄（附錄A），可以將它作為獨立的單元在任何時候講授，也可以與第9章一起講授。僅在3.5～3.6節(jié)和第4章討論鄰接矩陣時，要求熟悉矩陣（附錄B）。
第1章和第2章實質上是導論。第1章給出本書所處理的離散問題的樣例，應很快講授完。該章只是提出某些問題，而在本書的后面才給出解答。1.4節(jié)包含對復雜性的討論，可以略過它，或者推遲到學生有更多算法經驗時再講授。在這一節(jié)中，教師可以只講解與學生關系最密切的示例算法。
第2章復習各種基本主題，包括集合、關系、函數(shù)和數(shù)學歸納法。該章可以講授得稍快些，這取決于學生的數(shù)學背景和課程的層次。對于數(shù)學背景較好的學生，第2章的很多內容應該可以讓他們自學。如上圖所示，除了第5章和第7章依賴于第4章，以及第6章與第4章前幾節(jié)的內容相關外，其余各章均彼此獨立。
為配合新的第3章，同余的內容從第2章中移出。與第4版一樣，這個內容（見第5版的3.1節(jié)）可以在講完2.2節(jié)（等價關系）以后的任何時候學習。
課程設置建議
下面的表格給出了三個課程設置范例。課程A的重點是圖論及其應用，涵蓋了第4～7章的大部分內容。課程B涉及圖論較少，更強調計數(shù)技術。課程C的重點是計算機科學專業(yè)的學生所感興趣的論題。
課程A課程B課程C
章課時數(shù)章課時數(shù)章課時數(shù)
141（跳過1.4節(jié)）314
252525
4646附錄B1
575636
668846
749556
88附錄A395
94附錄A3
104
本書適用于各種層次的“離散數(shù)學”課程。比如，計算復雜性是一個很重要的主題，本書對許多算法的復雜性給予了關注。但是，這是一個較難的主題，其論述深度應當與課程的層次和學生的基礎相吻合。
計算機題
各章結尾均給出一組計算機題，這些計算機題與該章的內容、算法等相關。本書刻意用普通的術語來敘述計算機題，以便適應使用各種計算系統(tǒng)和語言的學生。
致謝
我們衷心地感謝下列審閱本書的數(shù)學家：米勒斯維爾大學的Dorothee Blum、威斯康星大學麥迪遜分校的Richard Brualdi、佛羅里達州立大學的John L. Bryant、波特蘭州立大學的 Richard Crittenden、喬治梅森大學的Klaus Fischer、東得克薩斯州立大學的Dennis Grantham、Clemson大學的William R. Hare、東密歇根大學的Christopher Hee、佛羅里達大西洋大學的Frederick Hoffman、佛羅里達國際大學的Julian L. Hook、Broome社區(qū)學院的Carmelita Keyes、 Macalester學院的Richard K. Molnar、普度大學Calumet分校的Catherine Murphy、佛羅里達大學的Charl
出版者的話
譯者序
前言
致學生
離散數(shù)學紀年表
第1章 組合問題與組合技術引論1
1.1 工程完成時間的問題1
1.1.1 問題1
1.1.2 分析2
1.1.3 關鍵路徑分析3
1.1.4 一個建筑的例子4
1.2 匹配問題7
1.2.1 問題7
1.2.2 分析7
1.2.3 排列8
1.2.4 航空公司問題解決方案的實用性9
1.3 背包問題11
1.3.1 問題11
1.3.2 分析12
1.3.3 回顧實驗問題14
1.4 算法及其效率15
1.4.1 算法的比較15
1.4.2 多項式求值16
1.4.3 子集生成算法19
1.4.4 冒泡排序21
歷史注記24
補充習題25
計算機題27
推薦讀物27
第2章 集合、關系和函數(shù)28
2.1 集合運算28
2.2 等價關系32
*2.3 偏序關系37
2.3.1 偏序和全序37
2.3.2 哈斯圖40
2.3.3 拓撲排序41
2.4 函數(shù)44
2.5 數(shù)學歸納法52
2.6 應用58
歷史注記65
補充習題66
計算機題69
推薦讀物69
第3章 編碼理論70
3.1 同余70
3.2 歐幾里得算法75
3.2.1 最大公約數(shù)75
3.2.2 歐幾里得算法75
3.2.3 歐幾里得算法的效率77
3.2.4 擴展的歐幾里得算法77
3.3 RSA方法79
3.3.1 指數(shù)取模80
3.3.2 RSA方法的解密83
3.3.3 RSA方法的可行性85
3.4 檢錯碼和糾錯碼86
3.5 矩陣碼93
3.5.1 矩陣碼93
3.5.2 編碼的校驗矩陣94
3.6 單糾錯矩陣碼99
3.6.1 校驗矩陣行譯碼法100
3.6.2 漢明碼101
歷史注記105
補充習題106
計算機題109
推薦讀物109
第4章 圖110
4.1 圖及其表示110
4.1.1 圖的概念和表示110
4.1.2 圖的其他表示112
4.1.3 同構113
4.2 通路和回路117
4.2.1 多重圖、通路和回路117
4.2.2 歐拉回路和歐拉通路119
4.2.3 哈密頓回路和哈密頓通路122
4.3 最短通路和距離129
4.3.1 廣度優(yōu)先搜索算法129
4.3.2 帶權圖131
4.3.3 通路的數(shù)目134
4.4 圖著色138
4.5 有向圖和有向多重圖144
4.5.1 有向圖145
4.5.2 有向圖的表示145
4.5.3 有向多重圖146
4.5.4 有向歐拉回路和有向歐拉通路148
4.5.5 有向哈密頓回路和有向哈密頓通路149
歷史注記155
補充習題156
計算機題160
推薦讀物161
第5章 樹162
5.1 樹的性質162
5.2 生成樹168
5.2.1 生成樹169
5.2.2 廣度優(yōu)先搜索法169
5.2.3 最小生成樹和最大生成樹171
5.2.4 普里姆算法的證明174
5.3 深度優(yōu)先搜索179
5.3.1 深度優(yōu)先搜索法179
5.3.2 回溯183
5.4 根樹188
5.5 二叉樹和遍歷193
5.5.1 表達式樹193
5.5.2 前序遍歷195
5.5.3 后序遍歷197
5.5.4 中序遍歷199
5.6 最優(yōu)二叉樹和二叉搜索樹202
5.6.1 最優(yōu)二叉樹202
5.6.2 二叉搜索樹208
歷史注記215
補充習題216
計算機題219
推薦讀物220
第6章 匹配221
6.1 相異代表系221
6.1.1 相異代表系221
6.1.2 霍爾定理222
6.2 圖中的匹配225
6.2.1 匹配225
6.2.2 偶圖的矩陣227
6.2.3 覆蓋227
6.3 匹配算法231
6.3.1 獨立集算法的應用示例231
6.3.2 將算法運用于最大獨立集233
6.3.3 獨立集算法234
6.3.4 課程分配235
6.4 算法的應用239
6.4.1 柯尼希定理240
6.4.2 霍爾定理的證明241
6.4.3 瓶頸問題242
6.5 匈牙利方法245
6.5.1 匈牙利算法245
6.5.2 匈牙利算法的證明247
6.5.3 不是方陣的矩陣248
6.5.4 最大和獨立集249
歷史注記250
補充習題251
計算機題252
推薦讀物253
第7章 網(wǎng)絡流254
7.1 流和割254
7.2 流增廣算法261
7.3 最大流最小割定理269
7.4 流和匹配274
歷史注記280
補充習題280
計算機題283
推薦讀物283
第8章 計數(shù)技術284
8.1 帕斯卡三角形和二項式定理284
8.2 3個基本原理287
8.3 排列和組合293
8.4 允許重復的排列和組合297
8.5 概率302
*8.6 容斥原理306
*8.7 排列和r組合的生成315
8.7.1 排列的詞典序枚舉315
8.7.2 r組合的詞典序枚舉317
歷史注記320
補充習題321
計算機題323
推薦讀物324
第9章 遞推關系與生成函數(shù)325
9.1 遞推關系325
9.2 迭代法333
9.3 常系數(shù)線性差分方程341
9.3.1 一階常系數(shù)線性差分方程341
9.3.2 二階線性齊次差分方程344
*9.4 用遞推關系分析算法的效率350
9.4.1 順序查找算法和冒泡排序算法的效率…350
9.4.2 分治算法的效率352
9.4.3 排序算法的效率357
9.5 用生成函數(shù)計數(shù)359
9.5.1 生成函數(shù)360
9.5.2 形式冪級數(shù)361
9.6 生成函數(shù)的代數(shù)365
歷史注記372
補充習題373
計算機題375
推薦讀物376
第10章 組合電路和有限狀態(tài)機377
10.1 邏輯門377
10.2 構造組合電路383
10.3 卡諾圖388
10.4 有限狀態(tài)機397
10.4.1 奇偶校驗機398
10.4.2 有限狀態(tài)機399
10.4.3 帶輸出的有限狀態(tài)機400
歷史注記404
補充習題405
計算機題407
推薦讀物408
附錄A 邏輯和證明簡介409
附錄B 矩陣425
附錄C 本書中的算法432
參考文獻436
奇數(shù)號習題答案440
書單推薦
