《程序员的数学(第 2 版)》拆解大纲(定稿:已按审读意见改过)
这一份是动笔前的节级大纲,一节一行,每行「进来时以为 → 出去时知道」。 两头是同一件事的节已经删掉或合并。定稿后正文的节序与这里一致。
切法: 原书 9 章 + 附录,拆成 21 章。 原书第 2 章(逻辑)拆成 4 章、第 3 章(余数)拆成 2 章、第 5 章拆成 2 章、第 6 章拆成 2 章、 第 7 章拆成 2 章、第 8 章拆成 3 章、附录拆成 3 章。按新词密度切,不按字数切。
| 原书 | 拆成 |
|---|---|
| 第 1 章 0 的故事 | 01 |
| 第 2 章 逻辑 | 02 / 03 / 04 / 05 |
| 第 3 章 余数 | 06 / 07 |
| 第 4 章 数学归纳法 | 08 |
| 第 5 章 排列组合 | 09 / 10 |
| 第 6 章 递归 | 11 / 12 |
| 第 7 章 指数爆炸 | 13 / 14 |
| 第 8 章 不可解问题 | 15 / 16 / 17 |
| 第 9 章 总结篇 | 18 |
| 附录 迈向机器学习的第一步 | 19 / 20 / 21 |
审读意见落到了哪里(逐条)
| 审读提的问题 | 改在哪 |
|---|---|
| ① 第 14 章主走查第三个数字算错(该是 66 不是 67) | 走查改成「先看 58(剩 7 个)→ 再看 71(剩 3 个:62、66、67)→ 再看 66,66 比 67 小 → 剩下的那一个就是 67」。三步各写当前范围和被看的那个数,「判断了 3 次」与「第 4 个位置是答案」分开 |
| ② 总纲主线漏掉指数爆炸这一级 | 主线补进第 ⑦ 级「每多一样条件就翻一倍:30 个开关 10.7 亿种,一分钟一次要跑 2037 年 —— 『有限』头一回和『人等得起』分了家」,以及第 ⑧ 级「反过来用它:数据排好序就能一路砍半」。第 ⑨ 级「机器无论多快都做不完」才接得上 |
| ③ 第 01 章丢了原书自称「贯穿本书」的主旨 | 第 01 章新增第 8 节「把大问题分解为小单元」(放在罗马数字之后、可带走的之前),从「IIIIIIIIIIII 和 XII 哪个好使」讲到「创造单元就是把大问题切小」,并写明这句话后面十七章还会反复出现;第 20 章第 8 节的回指因此有了落点 |
| ③ 同章丢了「日常生活中的 0」与「重温历史进程」 | 假胶囊(每 4 粒里 1 粒没药效)并进第 7 节当收尾;埃及/巴比伦/玛雅/印度那一段单独成第 9 节 |
| ④ 第 05 章 && 与 || 两节重复 | 合并成一节。第 5 节讲完 && 之后,同一节末尾三行给出 || 的对照(A 为真就不看右边;写成 if-else)。腾出来的位子给了 check() && execute() 这种拿左边当闸门的实际写法 |
| ⑤ 第 20 章主走查中途换输入 | 全程用 (1,0,1):加权和 s=1.1 → 过 0 输出 1 → 给它编一个目标 2.0 → 平方差损失 0.81 → 权重往哪挪 → 挪完 s=1.3、损失 0.49。算损失这一步照书里的做法省掉激活函数,并且当场讲明为什么必须省(阶梯函数只吐 0 和 1,看不出差多远)。第 21 章续用同一组输入 |
| ⑥ 第 14 章把「时间复杂度 / O(log n)」写得像原书教的 | 两个名字都保留(出门确实会撞见),但按第二类来源标:正文写成「补充(不在书里)」,脚注给 Wikipedia 的原句与查阅日期;第 18 章边界一节明确记账「这是我们补的,原书刻意避开了大 O 记号」 |
| ⑦ 四个书里点了名的名字被拿掉 | 欧拉 + 图论(第 07 章第 7 节末)、康托尔 + 对角论证法(第 16 章第 5 节)、卢卡斯 1883 年发明汉诺塔(第 11 章第 1 节)、怀尔斯 1994 年证明费马大定理(第 17 章第 7 节)全部补回,写法一律是「先用大白话讲透,名字挂在同一段句末」 |
| ⑧ 第 07 章另起的走查超额(三处) | 取审读给的第二条路:「寻找恋人」压成三行的对照例子,不给它独立小节、不逐步走数。全章剩「黑白棋魔术(主走查)+ 铺草席 + 七桥」= 主走查 + 2 处,正好卡在上限。**没有拆章的理由:**保持章号稳定,让审读那 11 条意见还能按号对上;七桥自带的 6 个新词分在两节里,节级配额不破 |
| ⑨ 第 17 章把书里有的东西标成书里没有 | 该节标题改成「书里只给了年份和篇名:剩下的来历要自己补」。图灵 1936 年那篇论文(年份 + 篇名)写成第一类来源并配书内出处;图灵机、邱奇—图灵论题、发表刊物与卷期写成「补充(不在书里)」加查阅日期 |
| ⑩ 第 19 章丢了附录的「为什么是现在」 | 第 1 节之前新增「为什么偏偏是现在才火」,三条各占一段,各拿具体东西起头:网上现成的图片、能并排一起算的显卡、「购买此商品的顾客还购买了」 |
| ⑪ 第 09 章走查报的顺序与节序不一致 | 走查改成 13 → 8 → 52 → 2³²,与节序一致,四步在同一副扑克牌上连成一条线(加 → 减重复 → 乘 → 连乘) |
| ⑫ 第 07 章「寻找恋人」与「铺草席」重复 | 与第 ⑧ 条一起解决:恋人只留三行、只留「不看路线只看目的地」这一句取角;铺草席独占一节,重心整个挪到「这套判定只能证『不能』,逆命题不一定为真」,并写进小节标题 |
新词配额账(定稿后重新数的实际值)
口径按标准: node scripts/book-jargon.mjs math-for-programmers --list,
只数 book-jargon 词表里的承重词,按第一次出现的位置归章;同一概念的不同叫法算一张脸。
章不设上限,配额卡在段(1 个)和节(5 个)——定稿实测:段级超额 0 处、节级超额 0 处。
| 位置 | 第一次出现的承重词 | 个数 |
|---|---|---|
| 总纲 | 单元、指数、对数、递归、概率、停机问题、模型、训练、机器学习 | 9 |
| 01 | (承接总纲,无新增) | 0 |
| 02 | 命题 | 1 |
| 03–06 | (无新增) | 0 |
| 07 | 噪声 | 1 |
| 08 | 变量 | 1 |
| 09 | (无新增) | 0 |
| 10 | 算法 | 1 |
| 11–12 | (无新增) | 0 |
| 13 | 字节、枚举、并行 | 3 |
| 14 | 复杂度、时间复杂度 | 2 |
| 15 | (无新增) | 0 |
| 16 | 字符串 | 1 |
| 17 | 语法、图灵机 | 2 |
| 18 | (无新增) | 0 |
| 19 | GPU、特征、参数、泛化、过拟合、深度学习、向量、矩阵 | 8 |
| 20 | 权重、点积、激活函数、阈值、损失(含损失函数)、误差、梯度、梯度下降、学习率、局部最优 | 10 |
| 21 | 神经网络、前向传播、反向传播、强化学习、大语言模型 | 5 |
最挤的一章是第 20 章(10 个),但它有 12 个小节,最挤的一节也只有 2 个。
数学词大多不在词表里(命题在、可数不在;真值表、阶乘、递推公式、质数、奇偶性都不在), 机器查不出来。这些词按同一条规矩人工控:一段最多引一个,一节最多五个, 并且每个第一次出现时当场 用大白话讲透。
定稿和这份大纲的出入(交稿时必须说明的)
| 出入 | 为什么 |
|---|---|
| 每章多出一节「作者的判断、我们的判断,以及这一章的边界」 | 大纲只列了内容节,而标准要求每章有「作者的判断与证据」和「边界与局限」两段。定稿把它们合成一节放在「可带走的」之前 |
| 第 05 章由 7 节变 8 节 | 主走查按「翻成式子 → 打钩 → 圈框」拆成三节,每节走一步,比挤在一节里更好跟 |
| 第 14 章由 9 节变 10 节 | 「先看现象(15 人找犯人)」单独成节,把它和主走查(15 个数找 67)分开——两者是同一结构的两副外衣,合在一节会让人以为是两条走查 |
| 第 21 章标题从「神经网络与之后」改成「摞成层」 | 「神经网络」这个词如果出现在标题里,它的第一次露面就落在了没有解释的地方(机器检查也会报)。改成大白话标题,名字留在正文第 1 节当场解释 |
| 第 20 章第 6、7 节的标题不带术语 | 同上:「损失函数」「梯度」都改成在正文里当场挂牌,标题只说人话 |
| 第 06 章的「另起走查」只留一处 | 大纲写了一处,定稿照办;个位数那道题就是这一处 |
| 第 18 章多了一节「这本书刻意没讲什么,以及我们补了什么」 | 大纲里只说要记账,定稿把它做成了一整节(第 6 节),因为兑现表在总纲、而账单必须落在正文里 |
没有出入的地方: 21 章的切分、每章的主走查与另起走查处数、 每节「进来时以为 → 出去时知道」的两头,与这份大纲一致。
总纲 index.md
六节:30 秒导读 → 这是谁在什么时候写的 → 全书一条主线(十二级,拆成 ###) →
二十一章地图 → 覆盖什么/不覆盖什么 → 我们的判断 → 许诺兑现表。
主线十二级: ① 人一次抓不住太多东西 → ② 给「没有」一个位子,规则就变简单 → ③ 把大问题切成小单元 → ④ 切之前先学会不重不漏地分两半 → ⑤ 一眼看不出怎么切时,换个角度分组(余数与奇偶性) → ⑥ 分完要数得清(计数四法) → ⑦ 涉及无穷的断言两步就能证完 → ⑧ 有的问题身上藏着小一号的自己(递归) → ⑨ 每多一样条件就翻一倍:「有限」和「人等得起」分了家 → ⑩ 反过来用它:排好序就能一路砍半 → ⑪ 有些事不是慢,是数量级上就不够(可数 / 对角论证 / 停机问题) → ⑫ 人不擅长的地方催生出这些工具;机器学习是同一套思路的现代版。
01 0 的故事:给「没有」一个位子,规则就变简单
主走查: 一个数 2503,换四种写法走到底 —— 十进制四个位 → 抹掉 0 变成 253 → 罗马数字 MMDIII → 二进制 100111000111(12 位)→ 最右边那位是 10⁰ = 1。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为「十二」就是「10 和 2」写在一起 → 知道数本身只有一个,写法有好几种,而写法决定了算起来费不费劲 |
| 2 | 以为 2503 就是四个数字并排 → 能说出每个位置各管多少个(2 个 1000、5 个 100、0 个 10、3 个 1),并知道位置是有意义的(主走查第 1 步) |
| 3 | 以为 0 就是「什么都没有」,可写可不写 → 知道抹掉它 2503 会变成 253,0 的第一件活是占住位子(主走查第 2 步) |
| 4 | 以为罗马数字只是另一套符号 → 知道它没有位置也没有 0,所以加法要靠「五个 I 换一个 V」这样整理,数一大就吃不消(主走查第 3 步) |
| 5 | 以为计算机也该用十进制 → 知道它只用 0 和 1,2503 要写 12 位,但加法表只有 4 格,机器不怕位数多(主走查第 4 步) |
| 6 | 以为 10⁰ 该等于 0(0 个 10 相乘) → 知道值是被「定义」出来的,而定义的挑法只有一条准绳:让规则不分叉(主走查第 5 步) |
| 7 | 以为「0 的作用」只在数学里 → 知道空计划和假胶囊干的是同一件活:给「没有」一个位子,换来「每天一粒」这条不用判断的规则 |
| 8 | 以为这一章讲完 0 就完了 → 知道全书真正的主旨是「把大问题分解为小单元」,而这句话后面十七章还会反复出现,直到附录调参数那里 |
| 9 | 以为按位计数法理所当然 → 知道它是几千年、好几个文明凑出来的,而且很可能是被黏土板这种硬件限制逼出来的 |
| 10 | —— 可带走的 |
| 11 | —— 原文地图 |
02 不重不漏:一条收费规则该怎么写才不出 bug
主走查: 一位 6 岁的乘客买票 —— 同一个人,拿四份收费规则各判一次, 100 元 / 判不了 / 两种价钱都成立 / 100 元。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为逻辑是学院里的东西 → 知道它是用来消掉自然语言歧义的工具,而歧义就藏在需求文档的「或者」里 |
| 2 | 以为「6 岁以上」谁都读得懂 → 知道一句话要能判对错才叫命题,而 6 岁的乘客正是把话说清楚的那块试金石(主走查第 1 步) |
| 3 | 以为规则写全了就行 → 知道「大于 6 岁 / 不到 6 岁」漏掉了正好 6 岁的人,这叫遗漏(主走查第 2 步) |
| 4 | 以为多写一条总没坏处 → 知道「6 岁以上 / 6 岁以下」让同一个人有两种价钱,这叫重复;也知道重复不矛盾时只是啰嗦(主走查第 3、4 步) |
| 5 | 以为看文字就能查出漏和重 → 知道画一根数轴、把端点画成实心空心,漏和重会自己冒出来,而错误大多就出在端点上 |
| 6 | 以为「没漏没重」是两句零散的提醒 → 知道它们各有名字(完整性、排他性),合起来就是把大问题切开的那把尺 |
| 7 | 以为 if 语句只是语法 → 知道一条 if 就是一次「不重不漏地切两半」,而几百条 if 叠起来出 bug,病根都在这把尺上 |
03 真值表:把「并且、或者」钉死成一张表
主走查: 4 岁的 Bob,在星期日乘车。A =「年龄 6 岁以上」= false,B =「乘车日是星期日」= true。 同一对 A、B 走完五个式子:¬A=true、A∧B=false、A∨B=true、A⊕B=true、A=B 为 false。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为「不是……」不用解释 → 知道否定要靠一张两行的表钉死,而这张表天生就没漏没重(主走查第 1 步) |
| 2 | 以为真值表只能用来下定义 → 知道它还能用来证明,「不是不是星期日」等于「是星期日」就是这么证出来的 |
| 3 | 以为「并且」很简单 → 知道它的表有四行,而 4 岁的 Bob 在星期日这一行落在 false 上(主走查第 2 步) |
| 4 | 以为「或者」是「二选一」 → 知道它只在两个都假时才假,而且反过来说更好懂;也知道超市的「持有礼券 A 或 B」两张都有照样打折(主走查第 3 步) |
| 5 | 以为「或者」只有一种 → 知道「在东京或者在大阪」是另一种:两个都真反而假,它叫异或,并能拿两个开关一个灯泡把它接出来(主走查第 4 步) |
| 6 | 以为文氏图只是配图 → 知道它把「真的那些情况」画成一块地,看两个式子等不等只要看阴影一不一样 |
| 7 | 以为「A 和 B 相等」不算命题 → 知道它也是命题,而且它正好是异或的反面(主走查第 5 步) |
04 若 A 则 B:最容易读错的那一个,以及逆命题为什么不一定成立
主走查: 一位 8 岁的乘客。A =「10 岁以上」= false,B =「6 岁以上」= true。 同一个人走完:A⇒B 为真 → 逆命题 B⇒A 被这个人当场推翻 → 逆否命题 ¬B⇒¬A 为真 → 换个写法 (¬A)∨B 也为真 → 德摩根定律两边都算一遍。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为「若 A 则 B」就是日常那句「如果……就……」 → 知道前提为假时它一律算真,而 8 岁那位正是前提为假的那一行(主走查第 1 步) |
| 2 | 以为这条规定很怪 → 能用「陷阱」那张图讲出它为什么必须这样定:不踩进 A、或者待在 B 里,就掉不进坑 |
| 3 | 以为「若 A 则 B」成立,反过来也该成立 → 知道 8 岁这个人就是反例,逆命题不一定为真(主走查第 2 步) |
| 4 | 以为倒过来说都不可靠 → 知道把两头都取反再对调(逆否命题)是安全的,原命题真它就真(主走查第 3 步) |
| 5 | 以为「若 A 则 B」是一种新运算 → 知道它其实等于「不是 A,或者是 B」,一个符号都不用新学(主走查第 4 步) |
| 6 | 以为「不是(A 并且 B)」得原样搬着走 → 知道它等于「不是 A,或者不是 B」,这条互换叫德摩根定律,而 !(x>=0 && y>=0) 改写成 x<0 || y<0 用的就是它(主走查第 5 步) |
| 7 | 以为两个命题能组合出的运算有无穷多种 → 知道正好 16 种,而且把 false 写成 0、true 写成 1,那 16 列就是 0 到 15 的二进制 |
05 卡诺图与三值逻辑:把复杂规则压简,以及 undefined 从哪来
主走查: 二灯游戏里的一种灯况 —— 绿灯灭、黄灯亮。三条规则里它命中第 ⓐ 条 → 写成式子 ((¬A)∧B)∨((¬A)∧(¬B))∨(A∧B) 求值为真 → 在四格图上打钩 → 圈组合框 → 压成 (¬A)∨B,再对这同一种灯况求值,还是真。
另起走查一: 三灯游戏,8 个格子 → (¬A)∨C,黄灯根本不用看。
另起走查二: check() && execute(),check() 返回 false 时 execute() 一次都不跑。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为规则复杂就只能硬记 → 知道先把它翻成式子,而翻完那一版比原来更长,这才是卡诺图出场的理由(主走查第 1、2 步) |
| 2 | 以为卡诺图是什么高级工具 → 知道它就是把所有真假组合摆成一张二维表,该按按钮的格子打钩(主走查第 3 步) |
| 3 | 以为打完钩还得自己想 → 知道把相邻的钩用尽量大的框圈起来,每个框对应一个短式子,合起来就是压好的规则(主走查第 4、5 步) |
| 4 | 以为灯多了图就没用了 → 知道三个灯是 8 格、B 与 C 的分界要错位排,而结果里根本不出现 B —— 黄灯不用看 |
| 5 | 以为真假两个值就够用了 → 知道程序会崩、会卡死、会抛异常,于是多出第三个值 undefined;也知道 && 因此不能交换左右(A 为假就不看右边),它等于一段嵌套的 if,而 || 是同一件事的镜像(A 为真就不看右边),等于一段 if-else |
| 6 | 以为短路求值只是个省时间的小聪明 → 知道 check() && execute() 是拿左边当闸门,顺序反过来会真的把不该跑的跑掉 |
| 7 | 以为三个值一进来定律就全乱了 → 知道德摩根定律在三值逻辑里照样成立(九行表逐行核过),但一共 39 种运算符,书里只讲了三个 |
06 余数就是分组:1 亿天以后是星期几
主走查: 今天星期日,10¹⁰⁰ 天以后是星期几? 先拿 100 天试(100÷7=14 余 2 → 星期二)→ 1 亿天(÷7 余 2,还是星期二)→ 直接算 10¹⁰⁰ 除以 7 算不动 → 改看 0 的个数,余数按 1、3、2、6、4、5 循环,周期是 6 → 100÷6=16 余 4 → 星期四。
另起走查: 1 234 567 的 987 654 321 次方,个位是几 —— 个位按 7、9、3、1 循环, 指数除以 4 余 1 → 答案 7。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为算「100 天后星期几」只能一天天数 → 知道一除就出来:余数 2 就是星期二(主走查第 1 步) |
| 2 | 以为这只是省事 → 知道 1 亿天数下来要三年多,而除一次仍然是一秒的事;余数的本事是「大数一次降成小数」(主走查第 2 步) |
| 3 | 以为余数就是除法剩下的零头 → 知道它其实是在分组:七角形时钟走一圈是一周,指针停在哪一格就是哪一天 |
| 4 | 以为 10¹⁰⁰ 也照着除就行 → 知道这个数除不动,得先拿小的试出规律 —— 0 的个数每加 6 个,星期数就重来一遍(主走查第 3、4 步) |
| 5 | 以为找规律靠灵光一闪 → 知道套路是固定的:先用小数试算、把结果排成一列、找出循环长度、再用余数落到那一格(另起走查) |
| 6 | 以为「看 0 的个数」只是这一题的巧劲 → 知道它就是第 14 章要正式讲的那件工具的雏形 |
07 奇偶性:不试一次,也能断定「做不到」
主走查: 黑白棋魔术。桌上 7 枚棋子里黑棋 3 枚(奇数)→ 徒弟添 1 枚黑棋 → 8 枚里黑棋 4 枚(偶数) → 观众翻转 1 枚白棋 → 黑棋变 5 枚(奇数)→ 魔术师数出奇数,断定「翻过」。 (7 枚的具体摆法是我们为演示编的,书里只说随机排列。)
另起走查一: 铺 草席 —— 半张为单位共 62 块(偶数,看不出问题)→ 涂成黑白相间,黑 30、白 32 → 一整张必占一黑一白 → 铺不满。这套判定只能证「不能」。 另起走查二: 七桥 —— 4 个顶点的度数是 3、5、3、3,四个都是奇点 → 一笔画要求奇点不超过 2 → 走不完。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为魔术师靠记住原来的摆法 → 知道他蒙着眼睛,什么都没看见,信息全在徒弟添的那一枚上(主走查第 1 步) |
| 2 | 以为一枚棋子传不了多少信息 → 知道它传的是一个「黑棋个数是单还是双」,而这一位刚好够回答「动没动过」(主走查第 2、3 步) |
| 3 | 以为这只是个戏法 → 知道计算机通信里天天在用它:徒弟是发送方,观众是噪声,那枚棋子叫奇偶校验位(主走查第 4 步) |
| 4 | 以为它能查出所有错 → 知道 7 枚的 128 种摆法被切成两组各 64 种,同时翻两枚就骗过去了 |
| 5 | 以为要证明「铺不满」必须把所有铺法试一遍 → 知道涂个色数一数就够了,黑 30 白 32 差 2,而这套判定只能证「不能」,反过来数目相等也不保证铺得满(另起走查一;寻找恋人那题在这一节里只占三行,作对照) |
| 6 | 以为「一笔画」得靠试 → 知道把地图简化成点和线之后,只数每个点连着几条边就能定死(另起走查二上半) |
| 7 | 以为七桥是个孤零零的趣题 → 知道判据是「奇点要么 0 个、要么 2 个」,七桥四个点全是奇点所以不可能;也知道这条判据是欧拉解这道题时给出的,图论就是从这儿起头的(另起走查二下半) |
| 8 | 以为「看清全部细节」总是对的 → 知道有时候「准确地分类」比「正确地把握」更管用 |
08 数学归纳法:两步走完无穷多个断言
主走查: 存钱罐 —— 第 100 天一共存了多少钱。逐个加太慢 → 高斯配对:首尾相加都是 101、 一共 100 对、除以 2 得 5050 → 把 100 换成 n 写成断言 → 用两步证明它对所有 n 成立: 基底 n=0 两边都是 0;归纳拿 k=3 当场演一遍(左边 6+4=10,右边 4×5÷2=10)。
另起走查一: 循环不变式 —— 数组 [3, 1, 4] 走 sum,s 依次是 0 → 3 → 4 → 8。
另起走查二: 一个错的归纳证明 —— 「所有棋子颜色相同」,毛病出在 k=1:两组各 1 枚,重叠 0 枚。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为 1 加到 100 只能老实加 → 知道首尾配对之后只剩一次加、一次乘、一次除(主走查第 1 步) |
| 2 | 以为这只是小聪明 → 知道换成加到 100 亿,老实加要 300 年,配对法还是三步 —— 省的不是力气,是数量级(主走查第 2 步) |
| 3 | 以为「对所有 n 都成立」画个图就够了 → 知道图只画得出一种情况,而 n 有无穷个,所以需要另一种证法(主走查第 3 步) |
| 4 | 以为证无穷个断言得有无穷种办法 → 知道只要两步:先推倒第一张,再保证「倒了第 k 张,第 k+1 张一定跟着倒」(主走查第 4 步) |
| 5 | 以为这两步是空话 → 能看着小高斯那条断言把两步各走一遍,并且知道第二步里「假设 P(k) 成立」不是循环论证(主走查第 5 步) |
| 6 | 以为归纳法是数学家的东西 → 知道它就是一个 while 循环:k 从 0 数到 n,每转一圈用一次第二步 |
| 7 | 以为写循环靠小心 → 知道每转一圈都成立的那句话叫循环不变式,写循环前先想清楚它,错就少一半(另起走查一) |
| 8 | 以为有图有真相 → 知道有个「证明所有棋子同色」的假证明,两步都像模像样,毛病只在 k=1 那一格上(另起走查二) |
09 数数的四条法则:加、减重复、乘、连乘
主走查: 一副扑克牌。红桃 13 张(10 张数字 + 3 张花牌,加法法则)→ 这 13 张里能点亮灯泡的 8 张(6 + 4 − 2,容斥原理)→ 整副 52 张(4 × 13,乘法法则)→ 32 个灯泡的亮灭花样 2³² = 42.9 亿种(连乘)。
另起走查: 植树问题 —— 10 米路每隔 1 米种一棵,答案是 11 棵不是 10 棵; 同一件事换成内存里的 100 个数据,最后一个的编号是 99。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为数数没什么可讲 → 知道数数就是「把要数的东西和整数一一对上」,而漏和重是唯一的两种出错法 |
| 2 | 以为 10 米路每米一棵就是 10 棵 → 知道是 11 棵,因为 10 是间隔数不是棵数;也 知道这道题的另一件外衣是「第 k 个数据编号 k−1」(另起走查) |
| 3 | 以为数得仔细就够了 → 知道东西一多手指头不够用,真正要找的是「对应规则」,而规则要从对象的性质里读出来 |
| 4 | 以为把两堆加起来天经地义 → 知道加法法则有前提:两堆不能有重复的东西(主走查第 1 步) |
| 5 | 以为红桃里 2 的倍数加 3 的倍数就是答案 → 知道 6 和 12 被数了两次,减掉之后是 8 张,这叫容斥原理(主走查第 2 步) |
| 6 | 以为 52 张也得一张张数 → 知道「每种花色分别有 13 张」这句话本身就是乘法,4 × 13 一步到位(主走查第 3 步) |
| 7 | 以为乘法法则只管两堆 → 知道 32 个灯泡是 32 个 2 连乘,42.9 亿种花样;也知道这个数就是 32 位能表示的数的个数(主走查第 4 步) |
10 排列与组合:顺序算不算,决定了要不要除
主走查: 手上 5 张牌 A、B、C、D、E。全排一遍 5! = 120 种 → 只取 3 张排 P(5,3) = 60 种 → 不管顺序只取 3 张 C(5,3) = 10 种 → 三者的关系:6 × 10 = 60。
另起走查一: 3 种药共 100 粒 —— 99 个空隙里插 2 块隔板,C(99,2) = 4851 种。 另起走查二: 5 张牌里两张王牌,至少一端是王牌 —— (48 + 48 − 12) ÷ 2 = 42 种; 换用逻辑再算一遍:60 − 18 = 42。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为排 5 张牌得一种一种列 → 知道是 5 × 4 × 3 × 2 × 1,因为每排一张,可选的就少一张(主走查第 1 步) |
| 2 | 以为这串连乘没名字 → 知道它叫阶乘,还知道 0 的阶乘被定义成 1 而不是 0,理由和第 01 章定义 10⁰ 是同一条 |
| 3 | 以为 52 张牌的排法「很多」 → 拿到一个 68 位的数,并知道 13 张牌的排法就已经超过 60 亿 |
| 4 | 以为「取 3 张排一排」要重新想 → 知道只是把连乘砍到第 3 项:5 × 4 × 3 = 60(主走查第 2 步) |
| 5 | 以为不管顺序会更难算 → 知道先按顺序算再除掉重复度:60 ÷ 6 = 10(主走查第 3 步) |
| 6 | 以为置换、排列、组合是三件事 → 能用一张 10 行 6 列的表把三者串起来:6 × 10 = 60(主走查第 4 步) |
| 7 | 以为「同一种药可以多放几粒」就没法套公式 → 知道摆隔板能把它变回组合:C(99,2) = 4851(另起走查一) |
| 8 | 以为「至少有一端是王牌」只能分情况硬算 → 知道两条路都通:容斥算 42,或者用「反过来减」也算 42(另起走查二) |
11 递归:在它自己身上找出一个小一号的它自己
主走查: 6 层汉诺塔最少要移动多少次。先解 3 层(7 次)→ 看出「6 层 = 5 层 + 1 次 + 5 层」→ 写成递推式 → 从 H(0)=0 一路算到 H(6) = 63 → 抽出解析式 2ⁿ − 1 → 十行 C 程序跑出 63 步。
另起走查: 阶乘的递归定义 —— 3! 展开成 3 × 2 × 1 × 1,最后那个 1 就是 0!, 这也解释了第 10 章为什么把 0! 定义成 1。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为 6 个圆盘要一步步试 → 知道先缩小规模看 3 个,7 次就解完;也知道这游戏是卢卡斯 1883 年发明的(主走查第 1 步) |
| 2 | 以为 6 层和 5 层是两道题 → 能指出 6 层的解法整个由 5 层的解法拼出来:上面 5 个挪走、最大的那个挪过去、5 个再挪回来(主走查第 2 步) |
| 3 | 以为「用自己解自己」会绕成死循环 → 知道每绕一次问题就小一号,小到 0 层就什么也不用做,所以绕得完 |
| 4 | 以为要算 63 次得画 63 步 → 能从 H(0)=0 逐行算到 H(6)=63,这种「拿上一层表示这一层」的式子叫递推公式(主走查第 3 步) |
| 5 | 以为有了递推式就到头了 → 知道还能再抽一层,把 0、1、3、7、15、31、63 看成 2ⁿ − 1(主走查第 4 步) |
| 6 | 以为递归是数学里的说法 → 看见十行 C 代码原样照抄那三步,跑出来正好 63 步(主走查第 5 步) |
| 7 | 以为「找递归结构」要靠灵感 → 拿到一条固定动作:遮住问题的一部分,看剩下的是不是同一道题小了一号(另起走查) |
12 斐波那契、帕斯卡与分形:同一把钥匙开的三把锁
主走查: 一种动物,出生两天后每天生一只 —— 第 11 天有多少只。 第 1~5 天是 1、1、2、3、5 → 看出「今天 = 昨天全活着 + 前天那批各生一只」→ 递推式 → F(0) 到 F(11) 逐行算到 89。
另起走查一: 帕斯卡三角形 —— 5 行 5 列的格子路线有 10 条,而 C(5,3) 也是 10,两条路算同一件事。 另起走查二: 递归画树 —— 第 n 层树枝的末端接第 n−1 层,第 0 层什么也不画。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为算第 11 天得把每只动物都跟一遍 → 知道只要盯住两条:昨天的都活着、前天以前的各生一只(主走查第 1 步) |
| 2 | 以为这道题的递推式和汉诺塔一样 → 知道它要往回看两层不是一层,所以第 0 天得单独定成 0(主走查第 2、3 步) |
| 3 | 以为这串数是这道题独有的 → 知道摆砖头、打拍子、爬楼梯都会撞见它,它叫斐波那契数列 |
| 4 | 以为帕斯卡三角形是加法练习 → 知道每个数都是上面相邻两数之和,而这些数正好是第 10 章的组合数(另起走查一) |
| 5 | 以为「组合数等于上面两数之和」是巧合 → 能用「包含 A 的 + 不包含 A 的」讲出它为什么必然成立 |
| 6 | 以为递归只能算数 → 知道它也能画:一根树枝末端再接两根小一号的树枝,画到第 0 层收手(另起走查二) |
| 7 | 以为分形图是艺术 → 知道把帕斯卡三角形的奇数偶数涂成两色,谢尔平斯基三角形就自己浮出来了 |
13 指数爆炸:「有限」和「人等得起」头一回分了家
主走查: 一张 1 毫米厚的纸,对折到超过地月距离(39 万公里)要几次。 10 次 1024 毫米 → 20 次 1048 米 → 30 次 1073 公里 → 39 次 549 755 公里,超了。
另起走查一: 30 个复选框全测一遍 —— 2³⁰ = 10.7 亿次,一次一分钟要跑 2037 年。 另起走查二: 512 位密钥 —— 每多 1 位试解次数翻倍,2⁵¹² 是个 155 位的数。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为对折到月球得上百万次 → 知道 39 次就够,而这个差距本身才是这一章要教的东西(主走查) |
| 2 | 以为「翻倍」只是长得快一点 → 知道它长的是指数上的 1,不是数值上的 1;也知道 2ⁿ 会爆炸而 n² 不会 |
| 3 | 以为爆炸只发生在纸上 → 知道 30 个复选框就够爆:10.7 亿种组合,一分钟一次要 2037 年(另起走查一) |
| 4 | 以为「反正是有限的,机器全速跑总能跑完」 → 知道要紧的不是「有限时间」而是「人等得起的时间」,这两件事在这里头一回分了家 |
| 5 | 以为密码难破是因为算法多神秘 → 知道最笨的破法就是一把把钥匙试,而每多 1 位钥匙数翻倍,512 位就试不完了(另起走查二) |
| 6 | 以为遇到难题先想算法 → 知道第一步是估问题空间有多大,再决定能不能一个不漏地试 |
| 7 | 以为爆炸了就没辙 → 拿到四条路:堆机器、换解法、求近似、掷骰子,并知道每条路各自要付什么代价 |
14 反过来用它:一路砍半,以及只看 0 的个数
主走查: 15 个排好序的数 16 17 23 29 31 42 45 58 62 66 67 71 78 83 88 里找 67。 第 1 次看正中间的 58(67 更大,剩右边 7 个)→ 第 2 次看 71(67 更小,剩 62、66、67 三个)→ 第 3 次看 66(67 更大)→ 判断了 3 次,剩下的那一个就是 67。范围 15 → 7 → 3 → 1。
另起走查一: 用对数把乘法变加法 —— 100 × 1000 换成 2 + 3 = 5,再还原成 100 000。 另起走查二: 计算尺 —— 两根等间隔刻度的尺子对齐就能加,换成对数刻度就能乘。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为 15 个人里找一个人要问 15 次 → 知道 3 次就够,因为每次问的是正中间那个(现象层) |
| 2 | 以为「砍一半」只是省一半力 → 能跟着 58、71、66 走完三步,并说出每步剩几个:15 → 7 → 3 → 1(主走查) |
| 3 | 以为这法子只在小数据上好使 → 知道判断 10 次能覆盖 2047 个、20 次 209 万、30 次 21 亿 —— 多问一次,能查的数据就翻一倍 |
| 4 | 以为这是白捡的便宜 → 知道有前提:数据必须排好序,否则「在左边还是右边」根本判不了 |
| 5 | 以为「翻一倍只多问一次」没个正式说法 → 知道数据变多时会慢多少这件事叫时间复杂度,而这一类写作 O(log n);并且知道这两个名字不是原书教的,是我们补的 |
| 6 | 以为对数是高中课本里那个吓人的符号 → 知道它就是「数一数 0 有几个」:100 000 的对数是 5 |
| 7 | 以为对数和乘方是两回事 → 知道它们互为逆运算,「10 的 5 次方是 100 000」和「100 000 的对数是 5」说的是同一句话 |
| 8 | 以为对数只是换个写法 → 知道它能把乘法降成加法,而奈皮尔 1614 年拿出它时,天文学家正被大数乘法压着(另起走查一、二) |
| 9 | 以为图上那条竖直冲天的曲线没法看 → 知道把纵轴换成对数刻度,爆炸就被压成一条斜线 |
15 反证法:先假设它不成立,再逼出矛盾
主走查: 质数有无穷多个。假设只有有限个 → 拿最小的四个 2、3、5、7 演一遍: 乘起来是 210,加 1 得 211 → 211 除以 2、3、5、7 都余 1 → 按假设它该是质数,可它又比列表里所有质数都大 → 两句话同时成立,矛盾 → 假设错了。
另起走查一: 不存在最大的整数 —— 假设最大的是 M,M+1 立刻更大。 另起走查二: 中文版编者注指出原书这一步论证不严密,以及为什么这不影响结论。
| 节 | 进来时以 为 → 出去时知道 |
|---|---|
| 1 | 以为证明就是从条件一路推到结论 → 知道还有一条路:先假设结论不成立,再把矛盾逼出来 |
| 2 | 以为这条路很玄 → 拿「不存在最大的整数」走一遍,三行就完(另起走查一) |
| 3 | 以为质数是个模糊的说法 → 知道它是「只能被 1 和自己整除、并且大于 1 的整数」,还知道 1 为什么不算 |
| 4 | 以为「质数有无穷多个」得一个个找 → 能跟着 2、3、5、7 → 210 → 211 走完全程(主走查) |
| 5 | 以为反证法可以放松 —— 反正前提本来就是假的 → 知道中间每一步都必须严丝合缝,否则「矛盾」可能是自己推错的 |
| 6 | 以为书上的证明都对 → 知道中文版编者在这里加了一条注,指出这一步不严密,而原书作者、编者、我们是三个不同的声音(另起走查二) |
16 可数:两种「无穷」,一种数得过来,一种数不过来
主走查: 所有整数数列的集合数不过来。假设数得过来 → 把它们排成一张无穷大的表(第 k 个排第 k 行) → 取对角线上的数 0、2、5、2、0、9 → 各加 1 得 1、3、6、3、1、10 → 这个新数列与表里每一行至少差一处 → 表里没有它,可表号称包含全部,矛盾。
另起走查一: 可数的三个例子 —— 偶数(第 k 号是 2(k−1))、全体整数(0、+1、−1、+2、−2 交错编号)、 有理数(斜着走,跳过重复的)。 另起走查二: 程序的集合可数 —— 字符种类有限,按长度从短到长排、同长按字符顺序排,一个都不漏。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为无穷就是无穷,没什么好分的 → 知道判据是「能不能一个个编号」,能编号的叫可数(另起走查一上半) |
| 2 | 以为部分不可能和整体一样多 → 知道偶数能和全体正整数一一对上,这正是无穷集合的脾气(另起走查一下半) |
| 3 | 以为程序有无穷多种就没法编号 → 知道程序是有限种字符的有限排列,按长度排就能编号,所以程序可数(另起走查二) |
| 4 | 以为所有集合都能编号,只是规律难找 → 知道有的集合无论用什么规律都会漏,这样的集合确实存在 |
| 5 | 以为「一定会漏」这种话没法证 → 能跟着对角线 0、2、5、2、0、9 加 1 走完全程,并知道这套论证叫对角论证法,是康托尔提出的(主走查) |
| 6 | 以为这招到处能用 → 知道它对有理数就不灵:对角线造出来的小数不一定是有理数,而这正是最容易用错的地方 |
| 7 | 以为函数的个数和程序差不多 → 知道「输入一个整数、输出一个整数」的函数和整数数列一一对应,所以函数也数不过来 |
17 停机问题:有些程序,谁都写不出来
主走查: 假设有一个判断程序 HaltChecker(p, d),能判定「把 d 喂给 p,p 会不会停」→ 用它写出 SelfLoop(p):判定为「会停」就故意死循环,判定为「不停」就立刻结束 → 把 SelfLoop 自己喂给 SelfLoop:若它停了,说明判定是「不停」,可它停了 —— 矛盾; 若它不停,说明判定是「会停」,可它不停 —— 还是矛盾 → HaltChecker 写不出来。
另起走查一: 数量级上的理由 —— 程序可数、函数不可数,所以一定有函数没有对应的程序。 另起走查二: 如果 HaltChecker 存在,费马大定理和哥德巴赫猜想都能一句话判掉。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为「解不了」是指太难或者还没人想出来 → 知道不可解问题是另一回事:原则上写不出那个程序 |
| 2 | 以为程序总会跑完 → 知道行为只有两种:有限时间内结束,或者永不结束;while (1 > 0) {} 就是后者 |
| 3 | 以为「会不会停」看看代码就知道 → 知道要判的是「任意程序 + 任意数据」,而且判断者自己必须停下来 |
| 4 | 以为总有人能写出这个判断程序 → 能跟着 SelfLoop 把两种情况各推一遍,两边都撞上矛盾(主走查) |
| 5 | 以为这只是一道逻辑谜题 → 知道它换成任何编程语言都一样写不出来,而且同类的不可解问题还有一串 |
| 6 | 以为不可解问题只有这一个来源 → 知道第 16 章那个数数的对照给出了另一条理由:程序数得过来,函数数不过来(另起走查一) |
| 7 | 以为「写不出来」听着像托词 → 知道假如写得出来,费马大定理(1994 年被怀尔斯证明,此前 358 年无人能证)和哥德巴赫猜想都能被一句判定打 发(另起走查二) |
| 8 | 以为原书什么来历都没交代 → 知道书里只给了年份 1936 和篇名,而图灵机、邱奇—图灵论题、发表在哪本刊物上是我们补的 |
18 回头看:人不擅长什么,就发明什么
主走查: 拿第 06 章那道题重走一遍,当作「幻想法则」的样板 —— 现实世界的问题 「100 天后是星期几」→ 换到余数世界(100 ÷ 7 = 14 余 2)→ 把答案带回来(星期二)。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为这本书是九个互不相干的话题 → 能用一句话把九章串起来:每一章都在把「人做不动的」变成「机器照做就行的」 |
| 2 | 以为解题靠聪明 → 知道全书反复用的是两个动作:先拿小数试算找规律,再把结果抽象成变量 |
| 3 | 以为工具是数学家闲出来的 → 知道每一样都对应人类的一处短板:记不住大数、判断易错、管不了大量事物、处理不了无穷 |
| 4 | 以为「换个角度」是句空话 → 拿到一条可操作的套路:把问题搬到另一个世界解、再把答案搬回来(主走查) |
| 5 | 以为读完这本书就会写高性能算法了 → 知道它刻意避开了什么:大 O 记号的正式写法、概率统计、极限与微积分,以及这次拆解补进来的书外内容都在这里记一笔账 |
| 6 | 以为书写完了结论就定了 → 知道两版之间隔了 12 年,而附 录那三章的时代坐标停在 2017 年底 |
19 机器学习解决什么问题:预测与分类
主走查: 一家网店 —— 投 x 万元广告,销售额 y 会是多少。先摆出过去 5 组数据 → 假设 y = ax + b(这一步叫建立模型)→ a、b 未知,由数据定 → 拿一部分数据训练、留一部分数据考试。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为机器学习火起来是因为算法突然变聪明了 → 知道是三样东西同时到位:网上现成的数据、能并排一起算的显卡、以及「买了还买」这种能立刻变现的出口 |
| 2 | 以为机器学习是让程序员写更聪明的规则 → 知道恰恰相反:规则由计算机从数据里自己找,程序员不直接写 |
| 3 | 以为「预测」很玄 → 能指着广告费和销售额那 5 个点说出预测问题的三样东西:输入、输出、目标(主走查第 1 步) |
| 4 | 以为预测就是画条线 → 知道先要假设一种关系(y = ax + b),这一步叫建立模型,而模型可能一开始就选错(主走查第 2 步) |
| 5 | 以为模型定了就能用 → 知道里面还有两个待定的数,它们叫参数;参数选得越好,预测越准(主走查第 3 步) |
| 6 | 以为数据就是数据 → 知道要分成两份:训练数据用来调参数,测试数据用来考试,而考的是没见过的题 |
| 7 | 以为练习题全做对就是学好了 → 知道那可能是过拟合;真正要的是没见过的题也答得好,这叫泛化能力(主走查第 4 步) |
| 8 | 以为分类是另一门手艺 → 知道它就是第 06、07 章的分组换了个场合:手写数字判成 0 到 9 里的哪一个 |
| 9 | 以为输入只能是一个数 → 知道一张图片是一排像素值,一排数摞在一起叫向量;输出也可以是一排数,比如 10 个数字各自的概率 |
20 感知器:一个输入 (1, 0, 1) 从头走到尾
主走查(全章同一组输入): 输入 (1, 0, 1),权重 (0.6, −0.2, 0.5) → 加权和 s = 1.1 → 过 0,输出 1 → 给它编一个目标 2.0 → 平方差损失 (2.0 − 1.1)² = 0.81 → 看出该把 w₁、w₃ 往上挪(因为这两个输入是 1)→ 挪成 (0.7, −0.2, 0.6) → s = 1.3,损失降到 0.49。 这些数全部是我们为演示编的。 算损失那几步照书里的做法把激活函数摘掉,并当场讲明为什么必须摘。
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为「机器学习模型」是个庞然大物 → 知道最基本的那一个只有三条线、三个乘法、一次加法(主走查第 1 步) |
| 2 | 以为三个输入地位相同 → 知道每条线上挂着一个数决定它有多要紧,这个数叫权重;把 0.6、−0.2、0.5 乘进去再相加得 1.1(主走查第 2 步) |
| 3 | 以为「乘一乘加起来」得写一长串 → 知道排成两列数对着乘再求和,这个动作叫内积,写出来就两个字母 |
| 4 | 以为算出 1.1 就完了 → 知道后面还有一道闸门:大于 0 输出 1,否则输出 0,这道闸门叫激活函数,它的门槛值叫阈值(主走查第 3 步) |
| 5 | 以为这跟「学习」还差得远 → 拿到四步:喂输入 → 得输出 → 和目标比 → 挪参数,一圈一圈重复(主走查第 4 步) |
| 6 | 以为「比一比」就是看对不对 → 知道要的是「差多远」,所以取差的平方再求和;这个衡量「有多不好」的式子叫损失函数(主走查第 5 步) |
| 7 | 以为知道差多远就知道怎么改了 → 知道改的方向是「哪边下坡最陡」,那个方向的名字叫梯度;顺着它一小步一小步走的做法叫梯度下降法(主走查第 6 步) |
| 8 | 以为下山总能走到最低处 → 知道可能停在一个小坑里(局部最优),步子迈多大也是一门讲究(学习率);也知道这一整套「只看脚下往哪走」正是第 01 章那句「把大问题分解成小单元」的又一次应用 |
| 9 | 以为参数是程序员调出来的 → 知道程序员管模型、管损失函数、管数据,唯独不碰参数的具体数值 |
21 神经网络与之后:把感知器摞起来
主走查(续第 20 章,同一组输入 (1, 0, 1)): 把三个感知器并排成一层、再接一层 → 同一组输入现在要经过 3 + 3 = 6 条以上的连线 → 第一层各自算出自己的加权和 → 第二层拿上一层的输出当输入 → 最后吐出 3 个数。层数一多,要调的权重从 3 个变成十几个, 「往哪边挪」就不能靠一个个试了 —— 这正是反向传播要解决的事。 (层数、连线数与「十几个」是我们照书里那张图数出来的。)
| 节 | 进来时以为 → 出去时知道 |
|---|---|
| 1 | 以为一个感知器就够用了 → 知道它能干的事太有限,于是把它们排成层、一层接一层(主走查第 1 步) |
| 2 | 以为「几层」是个明确的说法 → 知道有人按连线数、有人按节点排数,同一张图能叫 2 层也能叫 3 层 |
| 3 | 以为层数只是变宽变大 → 知道每层的输出就是下一层的输入,同一组 (1, 0, 1) 要连着过两次加权和(主走查第 2 步) |
| 4 | 以为参数多了照样一个个试 → 知道那是第 13 章那种爆炸;所以要先从左往右算一遍(前向传播),再从右往左回推每个权重该怎么动(反向传播)(主走查第 3 步) |
| 5 | 以为深度学习是另一门技术 → 知道它就是层数更多的神经网络,而「为什么更深更有效」在书写成时还是研究热点 |
| 6 | 以为学习都得有标准答案 → 知道强化学习没有:它靠试错和奖励,DQN 打电子游戏、AlphaGo 下围棋走的都是这条路 |
| 7 | 以为机器什么都能替人做了 → 拿到书里给的四件人类还得干的事:搭模型、保数据可靠、解释结果、做决定 |
| 8 | 以为这本书讲的机器学习还算新 → 知道附录写于 2017 年 12 月,而这一行之后最大的变化(大语言模型那一支)不在书里,并知道我们补了哪一句、出处在哪 |