首页 > 科技 > 计算机 > 计算机科学

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

作译者：Eric Lehman（埃里克雷曼）,F Thomson Leighton(F 汤姆森莱顿),Albert R Meyer（艾伯特 R 迈耶）

出版时间：2019-04 千字数：1198 版次：01-01 页数：832

开本：16开装帧： I S B N ：9787121355332

换版：

纸质书定价：￥168.0

库存:有

分享到：

共有图书评论0条【查看评论摘要】

看了又看

{{data.bookName}}

￥{{data.price}}

内容简介

前言

上架建议

作者简介

编辑推荐

音视频专区

目录

第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
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
第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
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　Benes ?网络	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  返回到K_5和K_3,3	441
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  小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
第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
第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

译者序
计算机科学与数学是密不可分的。不论是计算机本身的数值计算、逻辑推理、符号处理等，还是计算机程序中应用到的数学思想和算法，数学在计算机科学中仿佛灵魂一般地存在。另一方面，随着机器学习、人工智能、大数据等新兴技术的飞速发展以及计算性能的飞跃性提升，计算机为数学算法、模型及方法论的实践化提供了更丰富的空间和可能。《计算机科学中的数学：信息与智能时代的必修课》便是计算机科学和数学相关领域的最佳入门图书。
《计算机科学中的数学：信息与智能时代的必修课》是谷歌工程师Eric Lehman，与麻省理工学院的两位教授F. Thomson Leighton和Albert R. Meyer合著的教科书，也是麻省理工学院计算机专业本科公开课的讲义。建议读者在研读本书的同时学习这门课程，网址是https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- for-computer-science-fall-2010/。
本书的翻译历经译者们一年多的辛勤付出和共同努力，经过仔细校验、核对和最终审核，竭力保证翻译的准确性。在翻译风格上，本书竭力忠于原著，尽可能地传达作者的原意。另外，本书遵循知识共享Creative Commons Attribution-ShareAlike 3.0协议，许可使用协议的网址为https://creativecommons.org/licenses/by-sa/3.0/。
衷心感谢参与翻译工作的老师和同学们，他们是：唐李洋（第1~4章）、朱琛（第5~8章初译）、刘杰（第9~13章初译）、金博（第14~16章初译）、谭昶和马海平（第17~22章初译），全书翻译、检验和统稿由唐李洋完成。还要感谢电子工业出版社的张春雨、刘舫老师的最后审校。
由于时间仓促，加之水平有限，书中难免会有错误，敬请广大读者不吝赐教。

查看更多 > 图书评论

暂无评论

发表图书评论

评论标题：
评论内容：
验证码：: 看不清楚
点击刷新
: 您还没有登录，请登录后再评论。
点击“登录”

购买过本书的顾客还买过

{{data.bookName}}

￥{{data.price}}