離散數學紀年錶
譯者序
譯者簡介
前言
緻學生
離散數學紀年錶
第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章 集閤、關係和函數 28
2.1 集閤運算 28
2.2 等價關係 32
*2.3 偏序關係 37
2.3.1 偏序和全序 37
2.3.2 哈斯圖 40
2.3.3 拓撲排序 41
2.4 函數 44
2.5 數學歸納法 52
2.6 應用 58
曆史注記 65
補充習題 66
計算機題 69
推薦讀物 69
第3章 編碼理論 70
3.1 同餘 70
3.2 歐幾裏得算法 75
3.2.1 最大公約數 75
3.2.2 歐幾裏得算法 75
3.2.3 歐幾裏得算法的效率 77
3.2.4 擴展的歐幾裏得算法 77
3.3 RSA方法 79
3.3.1 指數取模 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 廣度優先搜索算法 129
4.3.2 帶權圖 131
4.3.3 通路的數目 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 廣度優先搜索法 169
5.2.3 最小生成樹和最大生成樹 171
5.2.4 普裏姆算法的證明 174
5.3 深度優先搜索 179
5.3.1 深度優先搜索法 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 最優二叉樹和二叉搜索樹 202
5.6.1 最優二叉樹 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章 網絡流 254
7.1 流和割 254
7.2 流增廣算法 261
7.3 最大流最小割定理 269
7.4 流和匹配 274
曆史注記 280
補充習題 280
計算機題 283
推薦讀物 283
第8章 計數技術 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章 遞推關係與生成函數 325
9.1 遞推關係 325
9.2 迭代法 333
9.3 常係數綫性差分方程 341
9.3.1 一階常係數綫性差分方程 341
9.3.2 二階綫性齊次差分方程 344
*9.4 用遞推關係分析算法的效率 350
9.4.1 順序查找算法和冒泡排序算法
的效率… 350
9.4.2 分治算法的效率 352
9.4.3 排序算法的效率 357
9.5 用生成函數計數 359
9.5.1 生成函數 360
9.5.2 形式冪級數 361
9.6 生成函數的代數 365
曆史注記 372
補充習題 373
計算機題 375
推薦讀物 376
第10章 組閤電路和有限狀態機 377
10.1 邏輯門 377
10.2 構造組閤電路 383
10.3 卡諾圖 388
10.4 有限狀態機 397
10.4.1 奇偶校驗機 398
10.4.2 有限狀態機 399
10.4.3 帶輸齣的有限狀態機 400
曆史注記 404
補充習題 405
計算機題 407
推薦讀物 408
附錄A 邏輯和證明簡介 409
附錄B 矩陣 425
附錄C 本書中的算法 432
參考文獻 436
奇數號習題答案 440
· · · · · · (收起)