离散数学 第4版PDF电子书下载

第1章 逻辑和证明 1

1.1 命题 1

1.2 条件命题和逻辑等价 6

1.3 量词 15

1.4 证明 26

*1.5 归结证明 32

1.6 数学归纳法 36

问题求解之角：数学归纳法 45

1.8 复习 48

1.7 小结 48

1.9 自测题 49

第2章 数学的语言 51

2.1 集合 51

2.2 序列（有序组）和串 59

2.3 数字系统 67

2.4 关系 74

问题求解之角：关系 84

2.5 等价关系 85

问题求解之角：等价关系 91

2.6 关系矩阵 94

*2.7 关系数据库 98

2.8 函数 104

2.9 小结 113

2.10 复习 113

2.11 自测题 116

第3章 算法 119

3.1 引言 119

3.2 算法的表示方法 120

3.3 欧氏算法 126

3.4 递归算法 130

3.5 算法的复杂度 137

问题求解之角：算法的设计与分析 152

3.6 欧氏算法分析 156

*3.7 RSA公用密码系统 159

3.8 小结 162

3.9 复习 163

3.10 自测题 164

第4章 记数方法和分类原理 166

4.1 基本原理 166

注：标有*号的节、表示该节可忽略不失连续性。 167

问题求解之角：计数 173

4.2 排列和组合 175

问题求解之角：组合 187

4.3 产生排列和组合的算法 189

4.4 广义的排列和组合 195

4.5 二项式系数和组合恒等式 200

4.6 鸽巢原理 205

4.7 小结 210

4.8 复习 210

4.9 自测题 210

5.1 引言 212

第5章 递推关系 212

5.2 求解递推关系 224

问题求解之角：递推关系 233

5.3 递推关系在算法分析方面的应用 236

5.4 小结 249

5.5 复习 249

5.6 自测题 249

第6章 图论 252

6.1 引言 252

6.2 路径和回路 263

问题求解之角：图 276

6.3 哈密尔顿回路和旅行推销员问题 277

6.4 最短路径算法 285

6.5 图的表示 292

6.6 图的同构 298

6.7 平面图 306

*6.8 方块游戏 314

6.9 小结 321

6.10 复习 321

6.11 自测题 322

第7章 树 326

7.1 引言 326

7.2 树的术语和特征 335

问题求解之角：树 340

7.3 生成树 342

7.4 最小生成树 350

7.5 二叉树 358

7.6 树的遍历 365

7.7 决策树和排序的最短时间 372

7.8 树的同构 379

*7.9 游戏树 390

7.10 小结 401

7.11 复习 401

7.12 自测题 402

第8章 网络模型和Petri网 407

8.1 网络模型 407

8.2 最大流量算法 413

8.3 最大流量最小切割定理 423

8.4 匹配 427

问题求解之角：匹配 433

8.5 Petri网 434

8.6 小结 444

8.7 复习 444

8.8 自测题 445

9.1 组合线路 448

第9章 布尔代数和组合线路 448

9.2 组合线路的性质 457

9.3 布尔代数 463

9.4 布尔函数和线路组合 470

9.5 应用 476

9.6 小结 486

9.7 复习 486

9.8 自测题 487

第10章 自动机，文法和语言 490

10.1 时序线路和有限状态机 490

10.2 有限状态自动机 498

10.3 语言和文法 506

10.4 非确定有限状态自动机 516

10.5 语言和自动机之间的关系 524

10.6 小结 531

10.7 复习 531

10.8 自测题 532

第11章 计算几何 535

11.1 最接近点对问题 535

*11.2 最接近点对问题的下界 540

11.3 计算凸包的算法 542

11.4 小结 551

11.5 复习 551

11.6 自测题 551

附录A：矩阵 553

附录B：参考文献 559

附录C：部分习题的提示和答案 565

附录D：符号表 677