README.md

计算机科学中的数学 信息与智能时代的必修课

第I部分 数学证明

• 引言 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
• 第2章 良序原理 26
  • 2.1 良序证明 26
  • 2.2 良序证明模板 27
  • 2.2.1 整数求和 27
  • 2.3 质因数分解 29
  • 2.4 良序集合 29
  • 2.4.1 不一样的良序集合（选学） 30
• 第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
• 第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
• 第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
• 第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
• 第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
• 第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

第Ⅱ部分 结构

• 引言 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 环Z_n 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
• 第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
• 第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 Benes ̌网络 363
• 第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
• 第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 返回到K_5和K_3,3 441
  • 13.6 平面图的着色 442
  • 13.7 多面体的分类 443
  • 13.8 平面图的另一个特征 445

第Ⅲ部分 计数

• 引言 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
• 第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
• 第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

第Ⅳ部分 概率论

• 引言 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
• 第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
• 第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
• 第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
• 第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

第Ⅴ部分 递推

• 引言 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
• 参考文献 802
• 符号表 806