计算机科学中的数学

本书是麻省理工学院计算机科学与工程专业本科生的初等离散数学课程讲义，涵盖了国外计算机科学专业涉及的基础数学知识，内容涉及形式逻辑符号、数学证明、归纳、集合与关系、图论基础、排列与组合、计数原理、离散概率、递归等，特别强调数学定义、证明及其应用方法。 本书适用于计算机相关专业学生及从业人员的数学入门，亦可作为统计、机器学习、数据挖掘等课程的初学资源。

第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

唐李洋 女，博士，毕业于合肥工业大学管理科学与工程系。现就职于中国电子科技集团公司第三十八研究所，曾游学美国，数据挖掘与大数据分析研究经验颇丰，在相关领域重要国际期刊及会议发表论文数篇。译有《高可用MySQL》（第1版和第2版）《R高性能编程》《大数据猩球：海量数据处理实践指南》《流式架构：Kafka与MapR Streams数据流处理》等图书。 刘杰 男，博士，南开大学教授、博士生导师。研究领域包括机器学习与数据挖掘方面的理论方法研究，以及面向信息抽取、网络挖掘、对话生成等问题的应用研究。在机器学习、数据挖掘领域重要国际期刊及会议发表论文多篇。担任中国计算机学会中文信息技术专家委员会、中国计算机学会大数据专家委员会、人工智能学会机器学习专家委员会等多个专家委员会委员及通讯委员。相关成果获得天津市科技进步二等奖两项。 谭昶 男，博士，毕业于中国科学技术大学计算机应用与技术系。现任科大讯飞股份有限公司大数据研究院执行院长兼智慧城市事业群副总裁，中国计算机学会公共政策委员会执行委员及大数据专家委员会委员。负责科大讯飞公司智慧城市、计算广告和个性化推荐等方向的大数据核心技术研发及应用推广工作，在大数据技术、个性化推荐方面有着多年的研究和实践经验。 金博 男，博士，大连理工大学教授。致力于数据挖掘、大数据分析、创新管理、商务智能等领域的科学研究。主持和参与多项国家级和省部级课题，在相关领域重要国际期刊及会议上发表论文60余篇，并担任数据挖掘领域三大顶级会议KDD、ICDM、SDM的程序委员会委员，是ACM、IEEE和CCF高级会员。 马海平 女，博士，毕业于中国科学技术大学计算机科学与技术系。现就职于科大讯飞股份有限公司，担任大数据研究院研究主管，从事数据挖掘与人工智能算法以及计算广告和个性化教育等领域的研究工作。在国际知名期刊和学术会议发表论文7篇，合著出版著作《Spark机器学习进阶实战》《Spark核心技术与高级应用》。 朱琛 男，硕士，毕业于中国科学技术大学，百度资深数据挖掘工程师。现就职于百度人才智库（Talent Intelligence Center），从事人力资源智能化研究，致力于用AI为HR赋能。研究方向包括文本数据挖掘、社交网络分析、图数据挖掘。在国际顶尖会议与期刊杂志发表论文十余篇，申请专利十余项，曾担任数个国际顶级会议（KDD、SDM等）程序委员会委员。

暂无其它内容！

• 一本仍在创作的教材，能感受到翻译老师的痛苦

  来源：豆瓣 发布时间：2025-05-04 07:29:16

• 就是离散数学，习题没有答案

  来源：豆瓣 发布时间：2025-05-04 07:29:16

• 中文版错误百出

  来源：豆瓣 发布时间：2025-05-04 07:29:16