《计算机科学中的数学：信息与智能时代的必修课》详细读书笔记
Author: [美] Eric Lehman / F. Thomson Leighton / Albert R. Meyer Translator: 唐李洋 / 刘杰 / 谭昶 / 金博 / 马海平 / 朱琛 Published: 2018-04 | Category: 计算机-数学基础 Core Thesis: 计算机科学的根基是离散数学——掌握数学证明、逻辑推理和离散结构，是理解算法、数据挖掘和人工智能的必备基础。 Reading Date: 2026-05-14 Tags: 数学 计算机科学 离散数学 MIT 算法基础 豆瓣评分: 8.3 | 评价人数: 68 | 页数: 832
一、全书概览
一句话总结
这是MIT计算机科学与工程专业本科生的初等离散数学课程讲义，用严谨的数学证明方法，系统构建了计算机科学所需的数学基础。
全书结构
| 部分 | 主题 | 章节范围 | 一句话概括 | |------|------|---------|------------| | 第I部分 | 数学证明 | 第0-1章 | 什么是证明，如何构造证明 | | 第II部分 | 结构与集合 | 多章 | 集合、关系、图论基础 | | 第III部分 | 组合与计数 | 多章 | 排列组合、计数原理 | | 第IV部分 | 概率论 | 多章 | 离散概率及其在CS中的应用 | | 第V部分 | 递归 | 多章 | 递归定义、递推关系 |
二、逐章要点
第I部分：数学证明
第1章：什么是证明
核心观点
数学证明是从公理出发，通过逻辑推理得出结论的严密过程。它是计算机科学中最基本的能力——不仅仅是数学工具，更是思维训练。
关键概念
| 概念 | 定义 | 一句话理解 | |------|------|------------| | 命题（Proposition） | 可判定真假的陈述 | "2+2=4" 是命题，"x>3" 不是 | | 谓词（Predicate） | 依赖于变量的命题 | P(x) = "x > 3"，真值取决于x | | 公理（Axiom） | 不证自明的基本假设 | 数学推理的起点 | | 定理（Theorem） | 经证明成立的命题 | 证明后的命题就是定理 | | 引理（Lemma） | 为证明定理服务的辅助命题 | 小定理，为大局服务 | | 推论（Corollary） | 从定理直接推出的结论 | 定理的"副产品" |
证明方法
| 方法 | 说明 | 适用场景 | |------|------|---------| | 直接证明 | 从前提直接推导结论 | 因果关系明确时 | | 反证法 | 假设结论不成立，推出矛盾 | 直接证明困难时 | | 构造性证明 | 直接构造出满足条件的对象 | 存在性证明 | | 数学归纳法 | 证明基础步+归纳步 | 自然数相关的命题 | | 穷举法 | 枚举所有可能情况 | 情况数有限时 |
行动清单
- [ ] 练习区分命题和非命题
- [ ] 用反证法证明"√2是无理数"
- [ ] 用数学归纳法证明一个简单等式
第II部分：结构与集合
核心概念：集合论基础
| 概念 | 符号 | 含义 | |------|------|------| | 集合 | {a, b, c} | 不同元素的集合 | | 子集 | A ⊆ B | A中所有元素都在B中 | | 并集 | A ∪ B | 属于A或B的所有元素 | | 交集 | A ∩ B | 同时属于A和B的元素 | | 差集 | A \ B | 属于A但不属于B的元素 | | 补集 | Ā | 全集中不在A的元素 | | 笛卡尔积 | A × B | 所有有序对(a,b) | | 幂集 | P(A) | A的所有子集的集合 |
关系与函数
| 概念 | 定义 | 计算机科学应用 | |------|------|---------------| | 等价关系 | 自反、对称、传递 | 数据分类、哈希 | | 偏序关系 | 自反、反对称、传递 | 任务调度、版本控制 | | 全序关系 | 任意两元素可比较 | 排序算法 | | 函数 | 每个输入对应唯一输出 | 程序设计基础 |
图论基础
| 概念 | 定义 | 应用 | |------|------|------| | 无向图 | 顶点和无方向边的集合 | 社交网络 | | 有向图 | 边有方向的图 | 网页链接关系 | | 路径 | 顶点和边的序列 | 路由算法 | | 连通性 | 任意两顶点间存在路径 | 网络可靠性 | | 树 | 无环连通图 | 数据结构（二叉树等） |
第III部分：组合与计数
核心计数原理
| 原理 | 公式 | 说明 | |------|------|------| | 加法原理 | |A|+|B| | 完成任务的方式数=各方式之和 | | 乘法原理 | |A|×|B| | 连续步骤的方式数=各步之积 | | 排列 | P(n,k) = n!/(n-k)! | 从n个取k个有序排列 | | 组合 | C(n,k) = n!/(k!(n-k)!) | 从n个取k个无序组合 | | 容斥原理 | |A∪B|=|A|+|B|-|A∩B| | 避免重复计数 | | 鸽巢原理 | n+1个物品放入n个盒子 | 必有盒子至少两个物品 |
行动清单
- [ ] 用容斥原理解决一个实际问题
- [ ] 理解排列和组合的区别和应用场景
- [ ] 练习鸽巢原理的思维方法
第IV部分：概率论
离散概率核心
| 概念 | 定义 | 公式 | |------|------|------| | 样本空间 | 所有可能结果的集合 | Ω | | 事件 | 样本空间的子集 | A ⊆ Ω | | 概率 | 事件发生的可能性度量 | P(A) = |A|/|Ω| | | 条件概率 | 已知B发生时A的概率 | P(A|B) = P(A∩B)/P(B) | | 独立事件 | P(A∩B) = P(A)×P(B) | 互不影响 | | 贝叶斯定理 | 逆向概率计算 | P(A|B) = P(B|A)P(A)/P(B) | | 期望值 | 随机变量的平均值 | E[X] = Σx·P(x) | | 方差 | 离散程度的度量 | Var(X) = E[X²] - E[X]² |
概率在CS中的应用
- 算法分析：随机算法的期望运行时间
- 机器学习：贝叶斯分类器、概率图模型
- 密码学：概率加密、零知识证明
- 网络：排队论、网络可靠性
第V部分：递归
核心概念
| 概念 | 定义 | 示例 | |------|------|------| | 递归定义 | 用自身定义自身 | n! = n×(n-1)! | | 递推关系 | 用前项表示后项 | F(n) = F(n-1) + F(n-2) | | 基础步 | 递归的终止条件 | 0! = 1 | | 归纳步 | 递归的推进规则 | F(n) = n×F(n-1) | | 主定理 | 分治算法复杂度分析 | T(n) = aT(n/b) + f(n) |
常见递推关系
| 关系类型 | 形式 | 解 | |---------|------|------| | 等比型 | T(n) = c·T(n-1) | T(n) = O(c^n) | | 线性递推 | T(n) = T(n-1) + T(n-2) | 斐波那契型 | | 分治型 | T(n) = aT(n/b) + f(n) | 由主定理决定 |
三、关键概念速查
| 概念 | 定义 | 一句话理解 | |------|------|------------| | 离散数学 | 研究离散（非连续）结构的数学 | 计算机用的是0和1，不是连续函数 | | 形式逻辑 | 用符号研究推理的学科 | "如果P则Q"的数学化表达 | | 数学归纳法 | 证明对所有自然数成立的工具 | 先证明n=1，再从n推导n+1 | | 图论 | 研究图的结构和性质的学科 | 网络分析的理论基础 | | 组合数学 | 研究计数和排列的学科 | "有多少种可能"的数学 | | 离散概率 | 离散样本空间上的概率 | 掷骰子式的概率分析 | | 递归 | 用自身定义自身的结构 | 程序设计中最重要的概念之一 |
四、核心框架/模型
MIT 6.042J 课程知识体系
数学证明（思维工具）
├── 命题逻辑 & 谓词逻辑
├── 证明方法（直接/反证/归纳）
└── 良序原理
│
离散结构（语言工具）
├── 集合论
├── 关系 & 函数
├── 图论
└── 树结构
│
计数与概率（分析工具）
├── 排列组合
├── 容斥原理
├── 离散概率
├── 期望 & 方差
└── 随机变量
│
递归（建模工具）
├── 递归定义
├── 递推关系
├── 生成函数
└── 渐近分析
从数学到计算机的映射
| 数学概念 | 计算机对应 | 实际应用 | |---------|-----------|---------| | 命题逻辑 | 布尔运算 | 条件判断、电路设计 | | 集合论 | 数据结构 | 数据库、集合操作 | | 关系 | 图/表 | 关系数据库 | | 图论 | 网络 | 社交网络、路由 | | 组合计数 | 算法分析 | 复杂度计算 | | 概率论 | 随机算法 | ML、AI基础 | | 递归 | 程序结构 | 递归函数、分治 |
五、金句摘录
"良好教育的标志不是你懂得多少知识，而是你善于查找你所需要的知识。"（本书序言引用）
"本书特别强调数学定义、证明及其应用方法。"
"本书适用于计算机相关专业学生及从业人员的数学入门，亦可作为统计、机器学习、数据挖掘等课程的初学资源。"
六、行动清单
每天
- [ ] 学习一个数学概念并完成相关练习
- [ ] 用形式化语言描述一个日常问题
每周
- [ ] 完成一套章节练习题（注意：本书习题无标准答案）
- [ ] 将一个数学概念映射到实际编程场景
每月
- [ ] 完成一个大章节的系统性学习
- [ ] 用数学方法分析一个实际算法的复杂度
七、社区评价
来源：豆瓣精选
高分书评
《MIT经典课程讲义》 — 豆瓣读者
原版是MIT 6.042J课程的配套教材，内容涵盖计算机科学需要的基础数学，特别强调证明方法。
不同声音
《中文版错误百出》 — 豆瓣读者（短评）
不负责任的排版印刷错误贼多，影响阅读体验。
《翻译让人痛苦》 — 豆瓣读者（短评）
一本仍在创作的教材，能感受到翻译老师的痛苦。书名误导人，内容就是离散数学。
《不适合做考试教材》 — 豆瓣读者（短评）
独特视角讲解的离散数学思维，但不适合作为考试教材。习题没有答案，强烈不推荐自学使用。
八、争议与批评
| 批评点 | 来源 | 核心论据 | 是否成立 | |--------|------|----------|----------| | 中文版错误多 | 豆瓣短评 | 排版印刷错误严重影响理解 | 成立——多人反馈此问题 | | 习题无答案 | 豆瓣短评 | 自学无法检验对错 | 成立——这是本书最大的使用障碍 | | 书名误导 | 豆瓣短评 | 实质是离散数学教材 | 部分成立——副标题已说明 | | 不适合自学 | 豆瓣短评 | 无答案、内容需要引导 | 部分成立——更适合课堂使用 | | 内容面广但不深 | 豆瓣短评 | 832页覆盖太多主题 | 这是入门教材的特点 |
我的判断
- 哪些批评有道理：中文版翻译和排版质量确实是硬伤，建议有能力的读者参考MIT OCW原版。习题无答案对自学者很不友好。
- 哪些批评不成立：书名"计算机科学中的数学"并不误导——它确实是在讲计算机科学所需的数学基础。作为MIT课程的配套教材，它的定位很清晰。
九、一句话总结
MIT计算机科学本科生的离散数学经典教材，832页系统覆盖证明、集合、图论、计数、概率和递归——是算法和AI的数学地基，但中文版翻译质量堪忧，建议配合原版或MIT OCW使用。
笔记生成：2026-05-14 by 喵喵 🐈