Discrete Mathematics:Fifth Edition

第1章 逻辑与证明 1
1.1 命题 1
本节复习 5
练习 5
1.2 条件命题与逻辑等价 7
本节复习 11
练习 11
1.3 量词 13
本节复习 22
练习 22
1.4 证明 25
本节复习 30
练习 30
1.5 归结证明 33
本节复习 35
练习 35
1.6 数学归纳法 36
本节复习 40
练习 40
问题求解：数学归纳法 44
注释 46
本章复习 46
本章自测题 48
上机练习 49
第2章 数学语言 50
2.1 集合 50
本节复习 55
练习 56
2.2 序列和字符串 58
本节复习 62
练习 62
2.3 数系 67
本节复习 72
练习 72
2.4 关系 74
本节复习 78
练习 78
问题求解：关系 81
2.5 等价关系 82
本节复习 85
练习 85
问题求解：等价关系 87
2.6 关系矩阵 89
本节复习 92
练习 92
2.7 关系数据库 93
本节复习 96
练习 96
2.8 函数 98
本节复习 105
练习 106
注释 111
本章复习 111
本章自测题 113
上机练习 115
第3章 算法 117
3.1 简介 117
本节复习 118
练习 118
3.2 算法的表示 118
本节复习 122
练习 122
3.3 Euclid算法 123
本节复习 126
练习 126
3.4 递归算法 127
本节复习 131
练习 131
3.5 算法的复杂性 132
本节复习 141
练习 142
问题求解：算法的设计和分析 146
3.6 Euclidean算法分析 149
本节复习 152
练习 152
3.7 RSA公钥密码系统 152
本节复习 154
练习 154
注释 154
本章复习 155
本章自测题 156
上机练习 157
第4章 计数方法和鸽笼原理 159
4.1 基本原理 159
本节复习 163
练习 163
问题求解：计数 165
4.2 排列与组合 167
本节复习 173
练习 173
问题求解：组合 176
4.3 排列组合生成算法 179
本节复习 182
练习 182
4.4 离散概率简介 183
本节复习 184
练习 184
4.5 离散概率论 186
本节复习 192
练习 193
4.6 广义的排列和组合 194
本节复习 197
练习 197
4.7 二项式系数和组合恒等式 199
本节复习 202
练习 202
4.8 鸽笼原理 204
本节复习 205
练习 205
注释 207
本章复习 207
本章自测题 208
上机练习 210
第5章 递归关系 211
5.1 简介 211
本节复习 217
练习 217
5.2 解递归关系 222
本节复习 228
练习 228
问题求解：递归关系 231
5.3 在分析算法中的应用 234
本节复习 240
练习 240
注释 246
本章复习 246
本章自测题 246
上机练习 247
第6章 图论 249
6.1 简介 249
本节复习 255
练习 256
6.2 路径和回路 260
本节复习 265
练习 266
问题求解：图 270
6.3 Hamilton回路和旅行商问题 271
本节复习 275
练习 276
6.4 最短路径算法 278
本节复习 282
练习 282
6.5 图的表示 283
本节复习 286
练习 286
6.6 图的同构 289
本节复习 292
练习 292
6.7 平面图 296
本节复习 299
练习 300
6.8 Instant Insanity问题 303
本节复习 305
练习 306
注释 308
本章复习 309
本章自测题 310
上机练习 313
第7章 树 314
7.1 简介 314
本节复习 319
练习 319
7.2 树的术语和性质 322
本节复习 325
练习 325
问题求解：树 326
7.3 生成树 327
本节复习 332
练习 332
7.4 最小生成树 334
本节复习 337
练习 337
7.5 二叉树 340
本节复习 344
练习 344
7.6 树的遍历 345
本节复习 349
练习 349
7.7 决策树和最短时间排序 351
本节复习 356
练习 356
7.8 树的同构 357
本节复习 362
练习 362
7.9 博弈树 365
本节复习 369
练习 369
注释 373
本章复习 373
本章自测题 375
上机练习 378
第8章 网络模型 379
8.1 简介 379
本节复习 382
练习 382
8.2 最大流算法 384
本节复习 390
练习 390
8.3 最大流最小割定理 392
本节复习 394
练习 394
8.4 匹配 395
本节复习 398
练习 398
问题求解：匹配 399
注释 401
本章复习 401
本章自测题 402
上机练习 403
第9章 Boole代数与组合电路 404
9.1 组合电路 404
本节复习 408
练习 408
9.2 组合电路的性质 411
本节复习 413
练习 413
9.3 Boole代数 416
本节复习 419
练习 420
问题求解：Boole代数 420
9.4 Boole函数与电路综合 422
本节复习 425
练习 425
9.5 应用 429
本节复习 433
练习 434
注释 436
本章复习 437
本章自测题 437
上机练习 440
第10章 自动机、文法和语言 441
10.1 时序电路和有限状态机 441
本节复习 444
练习 444
10.2 有限状态自动机 447
本节复习 450
练习 451
10.3 语言和文法 453
本节复习 458
练习 459
10.4 不确定有限状态自动机 461
本节复习 464
练习 464
10.5 语言和自动机之间的关系 466
本节复习 470
练习 470
注释 471
本章复习 472
本章自测题 473
上机练习 475
第11章 计算几何 476
11.1 最小距点对问题 476
本节复习 479
练习 480
11.2 最小距点对问题的下界 480
本节复习 481
练习 481
11.3 计算凸包的一种算法 482
本节复习 488
练习 488
注释 489
本章复习 489
本章自测题 489
上机练习 490
附录A 矩阵 491
附录B 代数学回顾 495
部分习题答案与提示 505