← 专著首页目录德麦国际专著第 70 号

第十六章 通道一:压缩——旧路径的代价超过阈值

SDE数学解构导论 · 约 1,116 汉字

一、机制

通道一的机制可以一句话说完:

旧 D 在旧 E 上仍然做得出来,但随着 E 的规模上升,代价增长到不可接受;

新 S 是一次表示压缩,它把代价降阶,并保证旧 D 的输出可以从新表示中恢

复。

要点在“仍然做得出来”。这是通道一与通道三的分界:通道一里旧方法没有失败,只是变得昂贵;通道三里旧方法根本给不出对象。混淆这两者,是既有文献里最常见的一处错误,本编第十九章将纠正一次具体的误判。

二、七个例子与压缩比

把第一编的概念发生链按代价重排,通道一的签名立刻显形。设规模参数为 n。

旧D        任务         旧代价        新S   新代价          性质
逐一记号      记录数量 N     Θ(N) 个符号 位值制    Θ(log N) 个   指数压缩
                                     符号
数数        求 k 组已知    Θ(N),N 为   加法   Θ(k·log N) 指数压缩
          数量之和       总数
加法        a 重复 n 次   Θ(n) 次运算   乘法   Θ(1) 符号长     指数压缩
                                     度
乘法        a 自乘 n 次   Θ(n) 次乘法   幂    Θ(1) 符号长     指数压缩
                                     度
通分        两个分数比      求最小公倍      小数   逐位对齐         局部化
          大小         数               Θ(位数)
幂         由 aˣ=b 求 x 无直接算       对数   乘法群 →        局部化
                     法,试探            加法群
有限差分      求瞬时变化      不可达(只      微分   一次求导         见第二十章
          率          能逼近)

前四行是同一件事的四次重演:把“重复”折叠成“参数”。逐一记号把 N 个记号折成 log N 位;加法把“重新数一遍”折成“取已有结果相加”;乘法把“重复加”折成“因子与次数”;幂把“重复乘”折成“底与指数”。每一次折叠都把线性代价降为对数代价或常数符号长度。

第五、六行不同:小数与对数并没有把代价降阶,它们做的是另一件事——把一个不好算的运算搬到一个它好算的表示里。通分的困难不在于规模,在于最小公倍数依赖两个分母的算术关系;小数把这一依赖去掉,代价变成纯位数。对数把乘法搬进加法。这一类本章称为局部化型压缩,第十七章会说明它为什么必然出现。

第七行是难判例,留到第二十章处理。

三、判定签名 A

据此可以写出通道一的判定签名,三条同时满足才算通道一:

签名 A1(代价降阶). 存在规模参数 n 与任务族,使旧 D 的代价 C(n) 与新 S

的代价 c(n) 满足 c(n) = o(C(n));或旧运算在新表示下由非局部变为局部。

签名 A2(可恢复). 旧 D 的全部输出可由新 S 在不高于 O(c(n)) 的代价内恢

复。新 S 没有增加可表达的对象,只是把同一批对象表示得更短。

签名 A3(旧 D 未失败). 在新 S 出现之前,旧 D 对每个有限实例都给得出正

确答案。

A2 是这条签名的判错开关。 它要求“表达域不变”。若新 S 让原本表示不了的对象变得可表示,则 A2 为假,该次发生不是通道一——不论它看上去多么像“旧办法太麻烦了”。

第十九章将用这一条推翻一处流行的归属。

四、通道一为什么是数学教育的主战场

小学到初中的绝大部分内容都落在通道一:位值制、四则、竖式、九九表、约分、小数、指数律、对数律。这解释了一个长期被误解的现象——这些内容之所以能被“训练”出来,正是因为它们是压缩。压缩有明确的效率指标,效率可以练。

同时这也划出了训练的边界:通道二与通道三的内容练不出来。一个学生把分数运算练到极熟,不会因此更接近理解“为什么需要分数”,因为分数不走通道一(第十九章)。把三条通道的内容用同一套办法教,是当前数学教育里一处结构性的错配。这一判断可以被检验:若把分数按扩张通道教(从“除法在整数上不封闭”入手)而非按压缩通道教(从“分东西太麻烦”入手),理解指标应有可测的差异。这是本编留给教育研究的一个可证伪预言。

德麦国际专著第 70 号 · 王德生《SDE数学解构导论》