《離散數學：英文版》是2021年機械工業出版社出版的圖書。
基本介紹
- 中文名：離散數學：英文版
- 作者：[美]約翰·A.多西,[美]艾伯特·D.奧托,[美]勞倫斯·E.思朋斯等
- 出版社：機械工業出版社
- 出版時間：2021年
- ISBN： 9787111671831
本書充分考慮到初學者的需要，內容、例題、習題都經過精心的挑選和組織，講解細緻，循序漸進，實例貼近日常生活或計算機套用。本書注重算法，且算法描述獨立於某種具體的程式語言。教師可根據學生的層次和興趣來靈活拓展和組織講解內容。
本書可作為計算機專業或其他相關專業的離散數學教材或教學參考書，也可作為自學者的參考用書
第1章 組合問題與組合技術引論1
1.1 工程完成時間的問題2
1.2 匹配問題10
1.3 背包問題16
1.4 算法及其效率23
歷史註記35
補充習題37
計算機題39
推薦讀物40
第2章 集合、關係和函式41
2.1 集合運算41
2.2 等價關係47
*2.3 偏序關係54
2.4 函式65
2.5 數學歸納法76
2.6 套用84
歷史註記93
補充習題95
計算機題98
推薦讀物98
第3章 編碼理論99
3.1 同餘100
3.2 歐幾里得算法106
3.3 RSA方法113
3.4 檢錯碼和糾錯碼122
3.5 矩陣碼132
3.6 單糾錯矩陣碼140
歷史註記147
補充習題149
計算機題152
推薦讀物153
第4章 圖154
4.1 圖及其表示154
4.2 通路和迴路164
4.3 短通路和距離181
4.4 圖著色193
4.5 有向圖和有向多重圖202
歷史註記219
補充習題220
計算機題226
推薦讀物227
第5章 樹228
5.1 樹的性質228
5.2 生成樹238
5.3 深度優先搜尋253
5.4 根樹266
5.5 二叉樹和遍歷274
5.6 二叉樹和二叉搜尋樹287
歷史註記306
補充習題308
計算機題311
推薦讀物312
第6章 匹配313
6.1 相異代表系313
6.2 圖中的匹配319
6.3 匹配算法327
6.4 算法的套用337
6.5 匈牙利方法346
歷史註記354
補充習題355
計算機題357
推薦讀物357
第7章 網路流358
7.1 流和割358
7.2 流增廣算法369
7.3 流小割定理382
7.4 流和匹配389
歷史註記397
補充習題397
計算機題400
推薦讀物401
第8章 計數技術402
8.1 帕斯卡三角形和二項式定理402
8.2 3個基本原理406
8.3 排列和組合416
8.4 允許重複的排列和組合421
8.5 機率428
*8.6 容斥原理434
*8.7 排列和r組合的生成445
歷史註記452
補充習題453
計算機題456
推薦讀物457
第9章 遞推關係與生成函式458
9.1 遞推關係458
9.2 疊代法470
9.3 常係數線性差分方程482
*9.4 用遞推關係分析算法的效率494
9.5 用生成函式計數506
9.6 生成函式的代數513
歷史註記523
補充習題524
計算機題527
推薦讀物528
第10章 組合電路和有限狀態機529
10.1 邏輯門529
10.2 構造組合電路538
10.3 卡諾圖546
10.4 有限狀態機560
歷史註記569
補充習題570
計算機題573
推薦讀物573
附錄A 邏輯和證明簡介574
A.1 命題和聯結詞574
A.2 邏輯等價583
A.3 證明的方法587
歷史註記593
補充習題594
推薦讀物596
附錄B 矩陣597
歷史註記604
附錄C 本書中的算法607
參考文獻613
奇數號習題答案618
圖片來源658
Contents
1AN INTRODUCTION TO COMBINATORIAL PROBLEMS AND TECHNIQUES1
1.1 The Time to Completea Project 2
1.2 A Matching Problem 10
1.3 A Knapsack Problem 16
1.4 Algorithms and Their Efficiency 23
Historical Notes 35
Supplementary Exercises 37
Computer Projects 39
Suggested Readings 40
2 SETS, RELATIONS, AND FUNCTIONS 41
2.1 Set Operations 41
2.2 Equivalence Relations 47
2.3* Partial Ordering Relations 54
2.4 Functions 65
2.5 Mathematical Induction 76
2.6 Applications 84
Historical Notes 93
Supplementary Exercises 95
Computer Projects 98
Suggested Readings 98
3 CODING THEORY 99
3.1 Congruence 100
3.2 The Euclidean Algorithm 106
3.3 The RSA Method 113
3.4 Error-Detecting and Error-Correcting Codes 122
3.5 Matrix Codes 132
3.6 Matrix Codes that Correct All Single-Digit Errors 140
Historical Notes 147
Supplementary Exercises 149
Computer Projects 152
Suggested Readings 153
4 GRAPHS 154
4.1 Graphs and Their Representations 154
4.2 Pathsand Circuits 164
4.3 Shortest Paths and Distance 181
4.4 Coloringa Graph 193
4.5 Directed Graphs and Multigraphs 202
Historical Notes 219
Supplementary Exercises 220
Computer Projects 226
Suggested Readings 227
5 TREES 228
5.1 Properties of Trees 228
5.2 Spanning Trees 238
5.3 Depth-First Search 253
5.4 Rooted Trees 266
5.5 Binary Trees and Traversals 274
5.6 Optimal Binary Trees and Binary Search Trees 287
Historical Notes 306
Supplementary Exercises 308
Computer Projects 311
Suggested Readings 312
6 MATCHING 313
