离散数学结构 理论与应用 theory and applications 翻译版PDF电子书下载

目录 1

第一章 集合论、逻辑与算法基础 1

1.1 集合 1

1.1.1　文氏图 6

1.1.2　集合运算 7

1.1.3　有序对与笛卡儿叉积 14

1.1.4　集合的计算机表示 15

课堂练习 18

本节小结 21

习题1.1 22

1.2　数理逻辑 25

1.2.1　非 26

1.2.2　合取 27

1.2.3　析取 28

1.2.4　蕴涵 29

1.2.5　双向蕴涵 30

1.2.6　命题公式（公式） 31

课堂练习 37

本节小结 40

习题1.2 41

1.3　论证有效性 43

1.3.1 一些有效论证形式 45

课堂练习 48

本节小结 51

习题1.3 51

1.4　量词与一阶逻辑 53

1.4.1　谓词求非 57

1.4.2　其他推理规则 58

课堂练习 59

本节小结 61

习题1.4 61

1.5　证明方法 63

1.5.1　直接证明 64

1.5.2　间接证明 65

1.5.3　反证法 66

1.5.4　证明双向蕴涵 67

1.5.5　证明等价命题 68

1.5.6　证明中的错误 69

课堂练习 70

本节小结 71

习题1.5 71

1.6　算法 73

1.6.1　伪码约定 74

1.6.2　多项式运算 80

课堂练习 84

本节小结 85

习题1.6 85

编程练习 86

第二章 整数与数学归纳法 87

2.1　整数 89

2.1.1　除法算法 92

2.1.2　最大公约数 97

2.1.3　最小公倍数 102

课堂练习 103

本节小结 106

习题2.1 106

2.2　计算机中的整数表示 108

2.2.1　二进制数运算 113

课堂练习 124

本节小结 127

习题2.2 128

2.3　数学归纳法 129

2.3.1　应用：循环不变量（程序正确性） 133

课堂练习 137

习题2.3 143

本节小结 143

2.4　素数 146

2.4.1　正整数因子分解 153

课堂练习 156

本节小结 158

习题2.4 158

2.5　线性丢番图方程 159

课堂练习 164

本节小结 167

习题2.5 167

编程练习 168

3.1　关系 169

第三章 关系与偏序集 169

3.1.1　关系的域与值域 173

3.1.2　等价关系 177

3.1.3　等价类与划分 181

3.1.4　闭包 184

课堂练习 190

本节小结 195

习题3.1 197

3.2　偏序集 200

3.2.1　词典序 202

3.2.2　偏序集的有向图 203

3.2.3 哈塞图 204

3.2.4　极小元与极大元 206

3.2.5　格 208

课堂练习 212

本节小结 215

习题3.2 216

3.3　应用：关系型数据库 219

3.3.1　结构化查询语言 223

课堂练习 224

本节小结 226

习题3.3 226

编程练习 227

第四章 矩阵与关系闭包 228

4.1　矩阵 228

4.1.1　矩阵转置 238

4.1.2　对称矩阵 238

4.1.3　布尔（0-1）矩阵 239

课堂练习 243

本节小结 248

习题4.1 250

4.2　关系矩阵与闭包 253

4.2.1　求传递闭包的Warshall算法 262

课堂练习 269

本节小结 273

习题4.2 274

编程练习 276

第五章　函数 277

5.1　函数 277

5.1.1　单射、满射和——映射 284

5.1.2　复合 286

课堂练习 290

本节小结 294

习题5.1 295

5.2.1 函数的逆 298

5.2　特殊函数与集合的基数 298

5.2.2　限制、扩展、映像和预映像 301

5.2.3　弱取整函数与强取整函数 303

5.2.4　集合的基数 305

课堂练习 309

本节小结 312

习题5.2 313

5.3　序列与字符串 314

5.3.1　特殊数列 318

5.3.2　求和 319

5.3.3　索引变量的改变 320

5.3.4　积 323

5.3.6　在计算机内存中表示字符串 324

5.3.5　字符串（单词） 324

课堂练习 326

本节小结 329

习题5.3 330

5.4 元运算 332

课堂练习 336

本节小结 339

习题5.4 340

编程练习 341

6.1 同余 342

第六章　同余 342

6.1.1　整除测试 348

6.1.2　同余类的加法与乘法 352

课堂练习 353

本节小结 356

习题6.1 357

6.2　校验位 358

6.2.1　ISBN 359

6.2.2　UPC-A与EAN-13 364

6.2.3　信用卡的校验位 370

课堂练习 371

本节小结 375

习题6.2 376

6.3　线性同余 377

6.3.1　中国余数定理 381

6.3.2　整数的模（余）表示 383

6.3.3　循环赛 386

6.3.4　散列函数 389

课堂练习 394

本节小结 398

习题6.3 399

6.4　特殊同余定理 401

6.4.1 密码学 405

课堂练习 409

本节小结 413

习题6.4 413

编程练习 414

第七章　计数原理 416

7.1　基本计数原理 416

7.1.1 加法原理 417

7.1.2　乘法原理 418

7.1.3　同时使用加法与乘法原理 421

7.1.4　容斥原理 423

课堂练习 426

本节小结 428

习题7.1 429

7.2　鸽巢原理 431

课堂练习 434

本节小结 436

习题7.2 436

7.3　排列 437

课堂练习 439

本节小结 441

习题7.3 441

7.4　组合 442

课堂练习 444

本节小结 447

习题7.4 447

7.5　广义排列与组合 448

课堂练习 452

本节小结 454

习题7.5 455

7.6　二项式系数 455

7.6.1 计算阶乘与C（n，r）的算法 461

课堂练习 466

习题7.6 468

本节小结 468

7.7　生成排列与组合 469

课堂练习 474

本节小结 475

习题7.7 476

7.8　离散概率 476

7.8.1　公理方法 480

7.8.2　条件概率 482

课堂练习 483

本节小结 485

习题7.8 486

编程练习 487

第八章　递归关系 488

8.1　数列与递归关系 488

8.1.1　用迭代（替代）法求解递归关系 496

课堂练习 503

本节小结 508

习题8.1 509

8.2　线性齐次递归关系 511

课堂练习 521

本节小结 524

习题8.2 525

8.3　线性非齐次递归关系 526

课堂练习 538

本节小结 542

习题8.3 543

编程练习 543

第九章 算法与时间复杂度 544

9.1　算法分析 544

课堂练习 556

本节小结 557

习题9.1 558

9.2　各种算法 560

9.2.1　顺序查找 560

9.2.2　折半查找 562

9.2.3　选择排序 564

9.2.4　插入排序 566

9.2.5　基于比较的排序算法的下限 570

9.2.6　合并排序 571

9.2.7　合并排序算法分析 577

9.2.8　列表中的最小元素与最大元素 577

9.2.9　Strassen矩阵乘法 579

9.2.10　矩阵连乘 585

9.2.11 chainedMatrixMultipli-cation函数分析 591

课堂练习 593

习题9.2 595

本节小结 595

编程练习 598

第十章　图论 599

10.1　图的定义与符号 600

10.1.1　有向图 605

10.1.2　简单图 606

10.1.3　子图 608

课堂练习 610

本节小结 613

习题10.1 615

10.2　通路、路径与圈 617

10.2.1 匹配 624

课堂练习 627

本节小结 630

习题10.2 631

10.3　图的矩阵表示 634

10.3.1 相邻矩阵 635

10.3.2　关联矩阵 639

课堂练习 640

本节小结 642

习题10.3 642

10.4.1　欧拉回路 644

10.4　特殊回路 644

10.4.2 哈密尔顿圈 652

课堂练习 656

本节小结 658

习题10.4 659

10.5　同构 661

课堂练习 665

本节小结 668

习题10.5 668

10.6　图算法 670

10.6.2　Diikstra最短路径算法 671

10.6.1　最短路径算法 671

10.6.3　拓扑排序 678

课堂练习 683

本节小结 684

习题10.6 684

10.7　平面图与图着色 685

10.7.1　平面图 685

10.7.2　图着色 692

课堂练习 698

本节小结 701

习题10.7 702

编程练习 704

第十一章　树与网络 705

11.1　树 705

11.1.1　树的同构 709

课堂练习 711

本节小结 712

习题11.1 712

11.2　有根树 713

11.2.1 二叉树 714

11.2.2　二叉树遍历 717

11.2.3　二叉搜索树 719

11.2.4　二叉搜索树分析 722

11.2.5　表达式树 723

11.2.6　二叉树的同构 726

课堂练习 727

本节小结 729

习题1 1.2 730

11.3　生成树 731

11.3.1　最小生成树 735

课堂练习 740

本节小结 742

习题11.3 742

11.4　网络 744

11.4.1　（再谈）匹配 760

课堂练习 762

本节小结 764

习题11.4 766

编程练习 767

第十二章 布尔代数与组合电路 769

12.1 二元布尔代数 769

课堂练习 781

本节小结 782

习题12.1 783

12.2　布尔代数 786

课堂练习 792

本节小结 794

习题12.2 795

12.3　逻辑门与组合电路 796

12.3.1 Kamaugh图与布尔表达式的最小化 810

12.3.2　涉及三个变量的K-图和布尔表达式的最小化 813

12.3.3　涉及四个变量的K-图与布尔表达式的最小化 815

课堂练习 817

本节小结 821

习题12.3 822

编程练习 824

第十三章　有限自动机与语言 825

13.1　有限自动机与规则语言 825

13.1.1　确定有限自动机 827

13.1.2　源引理的应用 834

13.1.3　规则语言的代数性质 835

13.1.4　非确定有限自动机 836

课堂练习 842

本节小结 846

习题13.1 848

13.2　带输入和输出的有限状态机 853

课堂练习 858

本节小结 860

习题13.2 861

13.3　文法与语言 863

课堂练习 871

本节小结 874

习题13.3 876

编程练习 877

附录 878

部分习题答案与提示 881

符号表 909

参考文献 917