离散数学（英文版·原书第5版）

图书标准信息

• 作者 [美]约翰·A. 多西（John A. Dossey）；[美]艾
• 出版社 机械工业出版社
• 出版时间 2021-02
• 版次 1
• ISBN 9787111671831
• 定价 99.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 676页
• 字数 750千字

【内容简介】

本书充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。

  本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书

【目录】

第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

6.1 Sys