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

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

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

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

显示部分信息
前  言
译者序
计算机科学与数学是密不可分的。不论是计算机本身的数值计算、逻辑推理、符号处理等,还是计算机程序中应用到的数学思想和算法,数学在计算机科学中仿佛灵魂一般地存在。另一方面,随着机器学习、人工智能、大数据等新兴技术的飞速发展以及计算性能的飞跃性提升,计算机为数学算法、模型及方法论的实践化提供了更丰富的空间和可能。《计算机科学中的数学:信息与智能时代的必修课》便是计算机科学和数学相关领域的最佳入门图书。
《计算机科学中的数学:信息与智能时代的必修课》是谷歌工程师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/。

I 作者相关

发表评论