本書充分考慮到初學(xué)者的需要，內(nèi)容、例題、習(xí)題都經(jīng)過精心的挑選和組織，講解細(xì)致，循序漸進，實例貼近日常生活或計算機應(yīng)用。本書注重算法，且算法描述獨立于某種具體的編程語言。教師可根據(jù)學(xué)生的層次和興趣來靈活拓展和組織講解內(nèi)容。
如今，數(shù)學(xué)的應(yīng)用越來越多地涉及離散而非連續(xù)的模型，其主要原因是現(xiàn)代社會越來越多地用到計算機。本書適用于一學(xué)期的離散數(shù)學(xué)入門課程。
預(yù)備知識
雖然按照本書講授的課程只要求很少的數(shù)學(xué)預(yù)備知識，但還是要求學(xué)生至少達到修讀過兩年高中數(shù)學(xué)所應(yīng)具有的水平，包括解題和運算的技能以及抽象思維的能力。
方法
本書強調(diào)算法并以此貫穿全書。算法用文字表述，不需要具體編程語言的知識。
主題的選擇
本書主題的選擇基于多個專業(yè)組織的建議，包括MAA（美國數(shù)學(xué)協(xié)會）一年級和二年級離散數(shù)學(xué)課程制定工作組的建議、NCTM（National Council of Teachers of Mathematics，美國數(shù)學(xué)教師理事會）的“學(xué)校數(shù)學(xué)教育的原則與標(biāo)準(zhǔn)”和CBMS（Conference Board of the Mathematical Sciences，美國數(shù)學(xué)科學(xué)聯(lián)合會）對數(shù)學(xué)教學(xué)的建議等。
靈活性
雖然本書是針對一學(xué)期的課程設(shè)計的，但是本書所包含的材料多于一個學(xué)期所能覆蓋的內(nèi)容。因此，教師可以根據(jù)學(xué)生的特定需求和興趣方便地選擇主題。本書以前的版本在從計算機科學(xué)專業(yè)的一年級課程到數(shù)學(xué)專業(yè)的高年級課程等許多課程中用過，并得到了良好的反映�，F(xiàn)在的這個版本仍然為教師提供了靈活性，以適用于各種不同專業(yè)學(xué)生的課程。
第5版的變動
第5版的主要變動是新增了一章—第3章，討論同余、歐幾里得算法及相關(guān)的數(shù)論方面的內(nèi)容、RSA公鑰密碼技術(shù)、檢錯碼和糾錯碼（包括矩陣碼）。本書其余內(nèi)容與這一章不相關(guān)，所以可由教師根據(jù)需要進行取舍。學(xué)習(xí)矩陣碼的內(nèi)容要求熟悉矩陣，所以在學(xué)習(xí)編碼理論這一章之前，不熟悉矩陣的學(xué)生需要先閱讀附錄B。（詳見下面的“章節(jié)獨立性”和“課程設(shè)置建議”。）
另外，新版本在表述的清晰性方面有所改進，對離散數(shù)學(xué)的新進展也給予了關(guān)注。
習(xí)題
本書的習(xí)題安排錯落有致，靈活性強。每節(jié)后都有大量簡單的計算題和算法題，其中大多數(shù)習(xí)題有助于學(xué)生針對離散數(shù)學(xué)的概念和算法進行全面練習(xí)，這對數(shù)學(xué)基礎(chǔ)較弱的學(xué)生尤其重要；另一些習(xí)題拓展了正文中的材料，或者引入了正文中未論述過的新概念。帶*號的習(xí)題是更具挑戰(zhàn)性的問題。教師應(yīng)根據(jù)課程和學(xué)生水平從中挑選。奇數(shù)號計算題的答案附在本書末尾。在每一章的末尾，有一組補充習(xí)題，用來溫習(xí)各章最重要的概念和技術(shù)，以及探討正文中未討論的新概念。
章節(jié)獨立性
在采用本書進行教學(xué)時，各章的順序可以靈活地安排。下圖顯示了各章的依賴關(guān)系。其中，虛線表示第6章僅與第4章的前幾節(jié)內(nèi)容相關(guān)。本書只假定讀者具有高中幾何課程對于邏輯與證明的熟練程度，而對那些偏好更形式化處理的讀者提供了一個附錄（附錄A），可以將它作為獨立的單元在任何時候講授，也可以與第9章一起講授。僅在3.5～3.6節(jié)和第4章討論鄰接矩陣時，要求熟悉矩陣（附錄B）。
第1章和第2章實質(zhì)上是導(dǎo)論。第1章給出本書所處理的離散問題的樣例，應(yīng)很快講授完。該章只是提出某些問題，而在本書的后面才給出解答。1.4節(jié)包含對復(fù)雜性的討論，可以略過它，或者推遲到學(xué)生有更多算法經(jīng)驗時再講授。在這一節(jié)中，教師可以只講解與學(xué)生關(guān)系最密切的示例算法。
第2章復(fù)習(xí)各種基本主題，包括集合、關(guān)系、函數(shù)和數(shù)學(xué)歸納法。該章可以講授得稍快些，這取決于學(xué)生的數(shù)學(xué)背景和課程的層次。對于數(shù)學(xué)背景較好的學(xué)生，第2章的很多內(nèi)容應(yīng)該可以讓他們自學(xué)。如上圖所示，除了第5章和第7章依賴于第4章，以及第6章與第4章前幾節(jié)的內(nèi)容相關(guān)外，其余各章均彼此獨立。
為配合新的第3章，同余的內(nèi)容從第2章中移出。與第4版一樣，這個內(nèi)容（見第5版的3.1節(jié)）可以在講完2.2節(jié)（等價關(guān)系）以后的任何時候?qū)W習(xí)。
課程設(shè)置建議
下面的表格給出了三個課程設(shè)置范例。課程A的重點是圖論及其應(yīng)用，涵蓋了第4～7章的大部分內(nèi)容。課程B涉及圖論較少，更強調(diào)計數(shù)技術(shù)。課程C的重點是計算機科學(xué)專業(yè)的學(xué)生所感興趣的論題。
課程A課程B課程C
章課時數(shù)章課時數(shù)章課時數(shù)
141（跳過1.4節(jié)）314
252525
4646附錄B1
575636
668846
749556
88附錄A395
94附錄A3
104
本書適用于各種層次的“離散數(shù)學(xué)”課程。比如，計算復(fù)雜性是一個很重要的主題，本書對許多算法的復(fù)雜性給予了關(guān)注。但是，這是一個較難的主題，其論述深度應(yīng)當(dāng)與課程的層次和學(xué)生的基礎(chǔ)相吻合。
計算機題
各章結(jié)尾均給出一組計算機題，這些計算機題與該章的內(nèi)容、算法等相關(guān)。本書刻意用普通的術(shù)語來敘述計算機題，以便適應(yīng)使用各種計算系統(tǒng)和語言的學(xué)生。
致謝
我們衷心地感謝下列審閱本書的數(shù)學(xué)家：米勒斯維爾大學(xué)的Dorothee Blum、威斯康星大學(xué)麥迪遜分校的Richard Brualdi、佛羅里達州立大學(xué)的John L. Bryant、波特蘭州立大學(xué)的 Richard Crittenden、喬治梅森大學(xué)的Klaus Fischer、東得克薩斯州立大學(xué)的Dennis Grantham、Clemson大學(xué)的William R. Hare、東密歇根大學(xué)的Christopher Hee、佛羅里達大西洋大學(xué)的Frederick Hoffman、佛羅里達國際大學(xué)的Julian L. Hook、Broome社區(qū)學(xué)院的Carmelita Keyes、 Macalester學(xué)院的Richard K. Molnar、普度大學(xué)Calumet分校的Catherine Murphy、佛羅里達大學(xué)的Charl
出版者的話
譯者序
前言
致學(xué)生
離散數(shù)學(xué)紀(jì)年表
第1章 組合問題與組合技術(shù)引論1
1.1 工程完成時間的問題1
1.1.1 問題1
1.1.2 分析2
1.1.3 關(guān)鍵路徑分析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
補充習(xí)題25
計算機題27
推薦讀物27
第2章 集合、關(guān)系和函數(shù)28
2.1 集合運算28
2.2 等價關(guān)系32
*2.3 偏序關(guān)系37
2.3.1 偏序和全序37
2.3.2 哈斯圖40
2.3.3 拓?fù)渑判?1
2.4 函數(shù)44
2.5 數(shù)學(xué)歸納法52
2.6 應(yīng)用58
歷史注記65
補充習(xí)題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
補充習(xí)題106
計算機題109
推薦讀物109
第4章 圖110
4.1 圖及其表示110
4.1.1 圖的概念和表示110
4.1.2 圖的其他表示112
4.1.3 同構(gòu)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 帶權(quán)圖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
補充習(xí)題156
計算機題160
推薦讀物161
第5章 樹162
5.1 樹的性質(zhì)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
補充習(xí)題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 獨立集算法的應(yīng)用示例231
6.3.2 將算法運用于最大獨立集233
6.3.3 獨立集算法234
6.3.4 課程分配235
6.4 算法的應(yīng)用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
補充習(xí)題251
計算機題252
推薦讀物253
第7章 網(wǎng)絡(luò)流254
7.1 流和割254
7.2 流增廣算法261
7.3 最大流最小割定理269
7.4 流和匹配274
歷史注記280
補充習(xí)題280
計算機題283
推薦讀物283
第8章 計數(shù)技術(shù)284
8.1 帕斯卡三角形和二項式定理284
8.2 3個基本原理287
8.3 排列和組合293
8.4 允許重復(fù)的排列和組合297
8.5 概率302
*8.6 容斥原理306
*8.7 排列和r組合的生成315
8.7.1 排列的詞典序枚舉315
8.7.2 r組合的詞典序枚舉317
歷史注記320
補充習(xí)題321
計算機題323
推薦讀物324
第9章 遞推關(guān)系與生成函數(shù)325
9.1 遞推關(guān)系325
9.2 迭代法333
9.3 常系數(shù)線性差分方程341
9.3.1 一階常系數(shù)線性差分方程341
9.3.2 二階線性齊次差分方程344
*9.4 用遞推關(guān)系分析算法的效率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
補充習(xí)題373
計算機題375
推薦讀物376
第10章 組合電路和有限狀態(tài)機377
10.1 邏輯門377
10.2 構(gòu)造組合電路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
補充習(xí)題405
計算機題407
推薦讀物408
附錄A 邏輯和證明簡介409
附錄B 矩陣425
附錄C 本書中的算法432
參考文獻436
奇數(shù)號習(xí)題答案440
書單推薦
