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

作者
唐李洋女,博士,毕业于合肥工业大学管理科学与工程系。现就职于中国电子科技集团公司第三十八研究所,曾游学美国,数据挖掘与大数据分析研究经验颇丰,在相关领域重要国际期刊及会议发表论文数篇。译有《高可用MySQL》(第1版和第2版)、《R高性能编程》、《大数据猩球:海量数据处理实践指南》、《流式架构:Kafka与MapRStreams数据流处理》等图书。

刘杰男,博士,南开大学教授、博士生导师。研究领域包括机器学习与数据挖掘方面的理论方法研究,以及面向信息抽取、网络挖掘、对话生成等问题的应用研究。在机器学习、数据挖掘领域重要国际期刊及会议发表论文多篇。担任中国计算机学会中文信息技术专家委员会、中国计算机学会大数据专家委员会、人工智能学会机器学习专家委员会等多个专家委员会委员及通讯委员。相关成果获得天津市科技进步二等奖两项。

谭昶男,博士,毕业于中国科学技术大学计算机应用与技术系。现任科大讯飞股份有限公司大数据研究院执行院长兼智慧城市事业群副总裁,中国计算机学会公共政策委员会执行委员及大数据专家委员会委员。负责科大讯飞公司智慧城市、计算广告和个性化推荐等方向的大数据核心技术研发及应用推广工作,在大数据技术、个性化推荐方面有着多年的研究和实践经验。

金博男,博士,大连理工大学教授。致力于数据挖掘、大数据分析、创新管理、商务智能等领域的科学研究。主持和参与多项国家级和省部级课题,在相关领域重要国际期刊及会议上发表论文60余篇,并担任数据挖掘领域三大顶级会议KDD、ICDM、SDM的程序委员会委员,是ACM、IEEE和CCF高级会员。
马海平女,博士,毕业于中国科学技术大学计算机科学技术系。现就职于科大讯飞股份有限公司,担任大数据研究院研究主管,从事数据挖掘与人工智能算法以及计算广告和个性化教育等领域的研究工作。在国际知名期刊和学术会议发表论文7篇,合著出版著作《Spark机器学习进阶实战》《Spark核心技术与高级应用》。朱琛男,硕士,毕业于中国科学技术大学,百度资深数据挖掘工程师。现就职于百度人才智库(TalentIntelligenceCenter),从事人力资源智能化研究,致力于用AI为HR赋能。研究方向包括文本数据挖掘、社交网络分析、图数据挖掘。在国际顶尖会议与期刊杂志发表论文十余篇,申请专利十余项,曾担任数个国际顶级会议(KDD、SDM等)程序委员会委员。

内容

本书原为麻省理工学院计算机科学与工程专业的数学课程讲义,谷歌技术专家参与编写,涵盖计算机科学涉及的全部基础数学知识,包括形式逻辑符号、数学证明、归纳、集合与关系、图论基础、排列与组合、计数原理、离散概率、递归等,特别强调数学定义、证明及其应用方法。本书因具有系统、完整,以及有趣、易读等明显优势,现已被全球IT技术相关从业者及准从业者奉为圭臬、广泛传阅,在人工智能日益普及的全新信息时代,更是大放异彩。本书适合计算机相关专业学生及从业人员作为数学入门教材,亦可作为统计、机器学习、数据挖掘等课程的宝贵资料。

第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.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.3k?C连通图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.2Bookkee

显示部分信息
前  言
译者序
计算机科学与数学是密不可分的。不论是计算机本身的数值计算、逻辑推理、符号处理等,还是计算机程序中应用到的数学思想和算法,数学在计算机科学中仿佛灵魂一般地存在。另一方面,随着机器学习、人工智能、大数据等新兴技术的飞速发展以及计算性能的飞跃性提升,计算机为数学算法、模型及方法论的实践化提供了更丰富的空间和可能。《计算机科学中的数学:信息与智能时代的必修课》便是计算机科学和数学相关领域的最佳入门图书。
《计算机科学中的数学:信息与智能时代的必修课》是谷歌工程师EricLehman,与麻省理工学院的两位教授F.ThomsonLeighton和AlbertR.Meyer合著的教科书,也是麻省理工学院计算机专业本科公开课的讲义。建议读者在研读本书的同时学习这门课程,网址是https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/。
本书的翻译历经译者们一年多的辛勤付出和共同努力,经过仔细校验、核对和最终审核,竭力保证翻译的准确性。在翻译风格上,本书竭力忠于原著,尽可能地传达作者的原意。另外,本书遵循知识共享CreativeCommonsAttribution-ShareAlike3.0协议,许可使用协议的网址为https://creativecommons.org/licenses/by-sa/3.0/。




#现在前往

精选留言

计算机,科学,中的,数学
sample
2020-06-21
写留言
签到
投稿
QQ咨询
返回顶部