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

第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方法#111
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.1NOT，AND和OR41
3.1.2当且仅当42
3.1.3IMPLIES42
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.5SAT问题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.1N上的一些标准递归函数179
7.3.2不规范的函数定义179
7.4算术表达式181
7.4.1Aexp的替换和求值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
第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_n264
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.11RSA公钥加密274
9.12SAT与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.3Dilworth引理322
10.6偏序323
10.6.1DAG中路关系的性质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.3Benes?网络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.3k？连通图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返回到K_5和K_3,3441
13.6平面图的着色442
13.7多面体的分类443
13.8平面图的另一个特征445
13.2节习题446
13.8节习题447
第Ⅲ部分计数
引言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小o479
14.7.2大O479
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.2n-元素集合的子集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.2Bookkeeper法则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.342序列、04序列或60序列526
15.9.4n个集合的并集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
第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骰子Avs.骰子B610
17.3.2骰子Avs.骰子C612
17.3.3骰子Bvs.骰子C612
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.1DNA检测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
第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.1Akra-Bazzi公式794
22.4.2两个技术问题795
22.4.3Akra-Bazzi定理796
22.4.4主定理797
22.5进一步探索797
22.4节习题799
参考文献802
符号表806