第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.3Euclid算法 123
本节复习 126
练习 126
3.4递归算法 127
本节复习 131
练习 131
3.5算法的复杂性 132
本节复习 141
练习 142
问题求解：算法的设计和分析 146
3.6Euclidean算法分析 149
本节复习 152
练习 152
3.7RSA公钥密码系统 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
注释 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.3Hamilton回路和旅行商问题 271
本节复习 275
练习 276
6.4最短路径算法 278
本节复习 282
练习 282
6.5图的表示 283
本节复习 286
练习 286
6.6图的同构 289
本节复习 292
练习 292
6.7平面图 296
本节复习 299
练习 300
6.8InstantInsanity问题 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.4Boole函数与电路综合 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.1最小距点对问题 476
第11章 计算几何 476
本节复习 479
练习 480
11.2最小距点对问题的下界 480
本节复习 481
练习 481
11.3计算凸包的一种算法 482
练习 488
本节复习 488
注释 489
本章 复习 489
本章 自测题 489
上机练习 490
附录A矩阵 491
附录B代数学回顾 495
部分习题答案与提示 505