计算机科学中的数学 信息与智能时代的必修课PDF电子书下载

第Ⅰ部分 数学证明 3

引言 3

0.1 参考文献 4

第1章 什么是证明 5

1.1 命题 5

1.2 谓词 8

1.3 公理化方法 8

1.4 我们的公理 9

1.4.1 逻辑推理 9

1.4.2 证明的模式 10

1.5 证明蕴涵 10

1.5.1 方法#1 11

1.5.2 方法#2：证明逆反命题 12

1.6 证明“当且仅当” 13

1.6.1 方法#1：证明两个语句相互蕴涵 13

1.6.2 方法#2：构建iff链 13

1.7 案例证明法 14

1.8 反证法 15

1.9 数学证明的优秀实践 16

1.10 参考文献 18

1.1节习题 18

1.5节习题 21

1.7节习题 21

1.8节习题 23

第2章 良序原理 26

2.1 良序证明 26

2.2 良序证明模板 27

2.2.1 整数求和 27

2.3 质因数分解 29

2.4 良序集合 29

2.4.1 不一样的良序集合（选学） 30

2.2节习题 31

2.4节习题 38

第3章 逻辑公式 40

3.1 命题的命题 41

3.1.1 NOT，AND和OR 41

3.1.2 当且仅当 42

3.1.3 IMPLIES 42

3.2 计算机程序的命题逻辑 44

3.2.1 真值表计算 45

3.2.2 符号表示 46

3.3 等价性和有效性 47

3.3.1 蕴涵和逆否 47

3.3.2 永真性和可满足性 48

3.4 命题代数 49

3.4.1 命题范式 49

3.4.2 等价性证明 50

3.5 SAT问题 53

3.6 谓词公式 54

3.6.1 量词 54

3.6.2 混合量词 55

3.6.3 量词的顺序 56

3.6.4 变量与域 56

3.6.5 否定量词 57

3.6.6 谓词公式的永真性 57

3.7 参考文献 58

3.1节习题 59

3.2节习题 61

3.3节习题 65

3.4节习题 68

3.5节习题 69

3.6节习题 71

第4章 数学数据类型 79

4.1 集合 79

4.1.1 常用集合 80

4.1.2 集合的比较和组合 80

4.1.3 幂集 81

4.1.4 集合构造器标记 82

4.1.5 证明集合相等 82

4.2 序列 83

4.3 函数 84

4.3.1 域和像 84

4.3.2 函数复合 86

4.4 二元关系 86

4.4.1 关系图 87

4.4.2 关系的像 89

4.5 有限基数 90

4.5.1 有限集有多少个子集 91

4.1节习题 92

4.2节习题 96

4.4节习题 97

4.5节习题 105

第5章 归纳法 107

5.1 一般归纳法 107

5.1.1 一般归纳法的规则 108

5.1.2 举例说明 108

5.1.3 归纳法证明的模板 109

5.1.4 一般归纳法的简洁写法 110

5.1.5 更复杂的例子 111

5.1.6 错误的归纳证明 113

5.2 强归纳法 115

5.2.1 强归纳法的规则 115

5.2.2 斐波那契数列 116

5.2.3 质数的乘积 117

5.2.4 找零问题 118

5.2.5 堆盒子游戏 119

5.3 强归纳法、一般归纳法和良序法的比较 120

5.1节习题 121

5.2节习题 131

第6章 状态机 136

6.1 状态和转移 136

6.2 不变性原理 137

6.2.1 沿对角线移动的机器人 137

6.2.2 不变性原理的定义 139

6.2.3 示例：《虎胆龙威》 141

6.3 偏序正确性和终止性 143

6.3.1 快速求幂 143

6.3.2 派生变量 145

6.3.3 基于良序集合的终止性（选学） 146

6.3.4 东南方向跳跃的机器人（选学） 146

6.4 稳定的婚姻 147

6.4.1 配对仪式 148

6.4.2 我们结婚吧 150

6.4.3 他们从此幸福地生活在一起 150

6.4.4 竟然是男性 151

6.4.5 应用 152

6.3节习题 153

6.4节习题 165

第7章 递归数据类型 172

7.1 递归定义和结构归纳法 172

7.1.1 结构归纳法 174

7.2 匹配带括号的字符串 175

7.3 非负整数上的递归函数 179

7.3.1 N上的一些标准递归函数 179

7.3.2 不规范的函数定义 179

7.4 算术表达式 181

7.4.1 Aexp的替换和求值 181

7.5 计算机科学中的归纳 185

7.1节习题 185

7.2节习题 193

7.3节习题 201

7.4节习题 202

第8章 无限集 206

8.1 无限基数集 206

8.1.1 不同之处 209

8.1.2 可数集 209

8.1.3 幂集的势严格大于原集合 211

8.1.4 对角线证明 213

8.2 停止问题 214

8.3 集合逻辑 217

8.3.1 罗素悖论 217

8.3.2 集合的ZFC公理系统 218

8.3.3 避免罗素悖论 220

8.4 这些真的有效吗 220

8.4.1 计算机科学中的无穷大 221

8.1节习题 221

8.2节习题 228

8.3节习题 233

8.4节习题 236

第Ⅱ部分 结构 241

引言 241

第9章 数论 242

9.1 整除 242

9.1.1 整除的性质 243

9.1.2 不可整除问题 244

9.1.3 虎胆龙威 245

9.2 最大公约数 247

9.2.1 欧几里得算法 247

9.2.2 粉碎机 249

9.2.3 水壶问题的通解 251

9.2.4 最大公约数的性质 252

9.3 质数的奥秘 253

9.4 算术基本定理 255

9.4.1 唯一分解定理的证明 256

9.5 阿兰·图灵 257

9.5.1 图灵编码（1.0版） 258

9.5.2 破解图灵编码（1.0版） 260

9.6 模运算 260

9.7 余运算 262

9.7.1 环Zn 264

9.8 图灵编码（2.0版） 265

9.9 倒数与约去 266

9.9.1 互质 267

9.9.2 约去 268

9.9.3 解密（2.0版） 268

9.9.4 破解图灵编码（2.0版） 269

9.9.5 图灵后记 269

9.10 欧拉定理 271

9.10.1 计算欧拉φ函数 273

9.11 RSA公钥加密 274

9.12 SAT与RSA有什么关系 276

9.13 参考文献 277

9.1节习题 277

9.2节习题 278

9.3节习题 285

9.4节习题 285

9.6节习题 287

9.7节习题 288

9.8节习题 293

9.9节习题 293

9.10节习题 295

9.11节习题 303

第10章 有向图和偏序 309

10.1 顶点的度 311

10.2 路和通路 311

10.2.1 查找通路 313

10.3 邻接矩阵 314

10.3.1 最短路径 315

10.4 路关系 316

10.4.1 复合关系 316

10.5 有向无环图＆调度 317

10.5.1 调度 318

10.5.2 并行任务调度 320

10.5.3 Dilworth引理 322

10.6 偏序 323

10.6.1 DAG中路关系的性质 323

10.6.2 严格偏序 324

10.6.3 弱偏序 325

10.7 用集合包含表示偏序 326

10.8 线性序 327

10.9 乘积序 327

10.10 等价关系 328

10.10.1 等价类 328

10.11 关系性质的总结 329

10.1节习题 330

10.2节习题 331

10.3节习题 334

10.4节习题 335

10.5节习题 338

10.6节习题 344

10.7节习题 347

10.8节习题 349

10.9节习题 352

10.10节习题 354

第11章 通信网络 357

11.1 路由 357

11.1.1 完全二叉树 357

11.1.2 路由问题 358

11.2 路由的评价指标 358

11.2.1 网络直径 358

11.2.2 交换机的数量 359

11.2.3 网络时延 359

11.2.4 拥塞 360

11.3 网络设计 361

11.3.1 二维阵列 361

11.3.2 蝶形网络 362

11.3.3 Bene？网络 363

11.2节习题 368

11.3节习题 368

第12章 简单图 373

12.1 顶点邻接和度 373

12.2 美国异性伴侣统计 375

12.2.1 握手引理 376

12.3 一些常见的图 377

12.4 同构 378

12.5 二分图与匹配 380

12.5.1 二分匹配问题 380

12.5.2 匹配条件 381

12.6 着色 384

12.6.1 一个考试安排问题 384

12.6.2 一些着色边界 386

12.6.3 为什么着色 387

12.7 简单路 388

12.7.1 简单图中的路、通路和圈 388

12.7.2 圈作为子图 389

12.8 连通性 390

12.8.1 连通分量 390

12.8.2 奇数长度的圈和2-着色性 391

12.8.3 k-连通图 392

12.8.4 连通图的最小边数 393

12.9 森林和树 394

12.9.1 叶子、父母和孩子 394

12.9.2 性质 395

12.9.3 生成树 397

12.9.4 最小生成树 397

12.10 参考文献 401

12.2节习题 402

12.4节习题 403

12.5节习题 406

12.6节习题 411

12.7节习题 418

12.8节习题 420

12.9节习题 424

第13章 平面图 431

13.1 在平面上绘制图形 431

13.2 平面图的定义 433

13.2.1 面 434

13.2.2 平面嵌入的递归定义 436

13.2.3 这个定义行吗 438

13.2.4 外表面在哪里呢 438

13.3 欧拉公式 439

13.4 平面图中边的数量限制 440

13.5 返回到K5和K3,3 441

13.6 平面图的着色 442

13.7 多面体的分类 443

13.8 平面图的另一个特征 445

13.2 节习题 446

13.8 节习题 447

第Ⅲ部分 计数 455

引言 455

第14章 求和与渐近性 457

14.1 年金的值 458

14.1.1 钱未来的价值 458

14.1.2 扰动法 459

14.1.3 年金价值的闭型 460

14.1.4 无限长的等比数列 460

14.1.5 示例 461

14.1.6 等比数列求和的变化 462

14.2 幂和 463

14.3 估算求和式子 465

14.4 超出边界 468

14.4.1 问题陈述 468

14.4.2 调和数 471

14.4.3 渐近等式 473

14.5 乘积 474

14.5.1 斯特林公式 475

14.6 双倍的麻烦 477

14.7 渐近符号 479

14.7.1 小o 479

14.7.2 大O 479

14.7.3 θ 481

14.7.4 渐近符号的误区 482

14.7.5 Ω（选学） 484

14.1节习题 484

14.2节习题 486

14.3节习题 486

14.4节习题 488

14.7节习题 490

第15章 基数法则 499

15.1 通过其他计数来计算当前计数 499

15.1.1 双射规则 499

15.2 序列计数 500

15.2.1 乘积法则 501

15.2.2 n-元素集合的子集 501

15.2.3 加和法则 502

15.2.4 密码计数 502

15.3 广义乘积法则 503

15.3.1 有缺陷的美元钞票 504

15.3.2 一个象棋问题 505

15.3.3 排列 505

15.4 除法法则 506

15.4.1 另一个象棋问题 506

15.4.2 圆桌骑士 507

15.5 子集计数 508

15.5.1 子集法则 509

15.5.2 比特序列 510

15.6 重复序列 510

15.6.1 子集序列 510

15.6.2 Bookkeeper法则 511

15.6.3 二项式定理 512

15.7 计数练习：扑克手牌 513

15.7.1 四条相同点数的手牌 514

15.7.2 葫芦手牌 514

15.7.3 两个对子的手牌 515

15.7.4 花色齐全的手牌 517

15.8 鸽子洞原理 517

15.8.1 头上的头发 518

15.8.2 具有相同和的子集 519

15.8.3 魔术 521

15.8.4 秘密 521

15.8.5 真正的秘密 523

15.8.6 如果是4张牌呢 524

15.9 容斥原理 525

15.9.1 两个集合的并集 525

15.9.2 三个集合的并集 525

15.9.3 42序列、04序列或60序列 526

15.9.4 n个集合的并集 527

15.9.5 计算欧拉函数 529

15.10 组合证明 530

15.10.1 帕斯卡三角恒等式 530

15.10.2 给出组合证明 531

15.10.3 有趣的组合证明 532

15.11 参考文献 533

15.2节习题 534

15.4节习题 537

15.5节习题 538

15.6节习题 544

15.7节习题 548

15.8节习题 550

15.9节习题 554

15.10节习题 561

第16章 母函数 566

16.1 无穷级数 566

16.1.1 不收敛性 567

16.2 使用母函数计数 568

16.2.1 苹果和香蕉 568

16.2.2 母函数的积 569

16.2.3 卷积法则 570

16.2.4 利用卷积法则数甜甜圈 570

16.2.5 卷积法则中的二项式定理 571

16.2.6 一个荒唐的计数问题 572

16.3 部分分式 573

16.3.1 带有重根的部分分式 575

16.4 求解线性递推 575

16.4.1 斐波那契数的母函数 575

16.4.2 汉诺塔 576

16.4.3 求解一般线性递推 580

16.5 形式幂级数 580

16.5.1 发散母函数 580

16.5.2 幂级数环 581

16.6 参考文献 583

16.1节习题 583

16.2节习题 583

16.3节习题 586

16.4节习题 588

16.5节习题 595

第Ⅳ部分 概率论 599

引言 599

第17章 事件和概率空间 601

17.1 做个交易吧 601

17.1.1 理清问题 601

17.2 步法 602

17.2.1 步骤一：找到样本空间 602

17.2.2 步骤二：确定目标事件 605

17.2.3 步骤三：确定结果的概率 606

17.2.4 步骤四：计算事件的概率 608

17.2.5 蒙特霍尔问题的另一种解释 609

17.3 奇怪的骰子 609

17.3.1 骰子A vs.骰子B 610

17.3.2 骰子A vs.骰子C 612

17.3.3 骰子B vs.骰子C 612

17.3.4 掷两次 613

17.4 生日原理 615

17.4.1 匹配概率的确切公式 615

17.5 集合论和概率 616

17.5.1 概率空间 616

17.5.2 集合论的概率法则 617

17.5.3 均匀概率空间 618

17.5.4 无穷概率空间 619

17.6 参考文献 620

17.2节习题 620

17.5节习题 623

第18章 条件概率 626

18.1 蒙特霍尔困惑 626

18.1.1 帷幕之后 627

18.2 定义和标记 627

18.2.1 问题所在 628

18.3 条件概率四步法 629

18.4 为什么树状图有效 630

18.4.1 大小为k的子集的概率 631

18.4.2 医学检测 632

18.4.3 四步分析法 633

18.4.4 固有频率 634

18.4.5 后验概率 634

18.4.6 概率的哲学 635

18.5 全概率定理 637

18.5.1 以单一事件为条件 637

18.6 辛普森悖论 638

18.7 独立性 640

18.7.1 另一个公式 640

18.7.2 独立性是一种假设 641

18.8 相互独立性 641

18.8.1 DNA检测 642

18.8.2 两两独立 643

18.9 概率vs.置信度 645

18.9.1 肺结核测试 645

18.9.2 可能性修正 646

18.9.3 很可能正确的事实 648

18.9.4 极端事件 648

18.9.5 下一次抛掷的置信度 649

18.4节习题 650

18.5节习题 650

18.6节习题 660

18.7节习题 661

18.8节习题 663

18.9节习题 666

第19章 随机变量 667

19.1 随机变量示例 667

19.1.1 指示器随机变量 668

19.1.2 随机变量和事件 668

19.2 独立性 669

19.3 分布函数 670

19.3.1 伯努利分布 672

19.3.2 均匀分布 672

19.3.3 数字游戏 673

19.3.4 二项分布 675

19.4 期望 677

19.4.1 均匀随机变量的期望值 677

19.4.2 随机变量的倒数的期望 678

19.4.3 指示器随机变量的期望值 678

19.4.4 期望的另一种定义 678

19.4.5 条件期望 679

19.4.6 平均故障时间 680

19.4.7 赌博游戏的预期收益 682

19.5 期望的线性性质 686

19.5.1 两枚骰子的期望 687

19.5.2 指示器随机变量的和 687

19.5.3 二项分布的期望 688

19.5.4 赠券收集问题 689

19.5.5 无限和 691

19.5.6 赌博悖论 691

19.5.7 悖论的解答 692

19.5.8 乘积的期望 693

19.2节习题 694

19.3节习题 696

19.4节习题 698

19.5节习题 702

第20章 离差 712

20.1 马尔可夫定理 712

20.1.1 应用马尔可夫定理 714

20.1.2 有界变量的马尔可夫定理 714

20.2 切比雪夫定理 715

20.2.1 两个赌博游戏的方差 716

20.2.2 标准差 717

20.3 方差的性质 718

20.3.1 方差公式 719

20.3.2 故障时间的方差 719

20.3.3 常数的处理 720

20.3.4 和的方差 721

20.3.5 生日匹配 722

20.4 随机抽样估计 723

20.4.1 选民投票 723

20.4.2 两两独立采样 725

20.5 估计的置信度 726

20.6 随机变量的和 728

20.6.1 引例 728

20.6.2 切诺夫界 729

20.6.3 二项式尾的切诺夫界 729

20.6.4 彩票游戏的切诺夫界 730

20.6.5 随机负载均衡 731

20.6.6 切诺夫界的证明 732

20.6.7 边界的比较 734

20.6.8 墨菲定律 735

20.7 大期望 736

20.7.1 重复你自己 736

20.1节习题 737

20.2节习题 738

20.3节习题 739

20.5节习题 746

20.6节习题 750

20.7节习题 753

第21章 随机游走 755

21.1 赌徒破产 755

21.1.1 避免破产的概率 757

21.1.2 获胜概率递推 758

21.1.3 有偏情形的简单解释 759

21.1.4 步长多长 761

21.1.5 赢了就退出 762

21.2 图的随机游走 763

21.2.1 网页排名初探 764

21.2.2 网页图的随机游走 765

21.2.3 平稳分布与网页排名 766

21.1节习题 768

21.2节习题 769

第Ⅴ部分 递推 779

引言 779

第22章 递推 780

22.1 汉诺塔 780

22.1.1 上界陷阱 781

22.1.2 扩充-化简法 781

22.2 归并排序 783

22.2.1 寻找递推 784

22.2.2 求解递推 784

22.3 线性递推 786

22.3.1 爬楼梯 786

22.3.2 求解齐次线性递推 789

22.3.3 求解一般线性递推 790

22.3.4 如何猜测特解 792

22.4 分治递推 793

22.4.1 Akra-Bazzi公式 794

22.4.2 两个技术问题 795

22.4.3 Akra-Bazzi定理 796

22.4.4 主定理 797

22.5 进一步探索 797

22.4节习题 799

参考文献 802

符号表 806