数据与可计算结构 [data-structure]

    七树合一定理 [seven-trees-in-one]

    Definition 1. 二叉树类型 [binary-tree]

    • September 24, 2024
    • kokic

    $\gdef\spaces#1{~ #1 ~}$

    二叉树意味树的每个结点最多两个子树. 其类型由两个构造器归纳给出

    inductive Tree α
  | leaf : Tree α
  | node : α → Tree α → Tree α → Tree α

    叶结点构造器 leaf 用于构造出一棵空树, 空树作为某个结点的所有子结点时, 该结点正是叶结点. 相应的, 二叉树的值存储在非叶结点中. 每个 (非空, 无标记) 二叉树类型的值要么是一个单结点 $\{\text{pt}\} = 1$, 要么等价于二叉树的有序配对 $B \times B = B^2$. 即 $B \xrightarrow{\sim} \{\text{pt}\} \sqcup B^2$.

    换言之, 二叉树可定义为某种满足 $B=1+B^2$ 的 (代数) 结构. 回顾 $6$ 次分圆多项式 $$ \Phi_6(x) \spaces= x^2-x+1 $$ 其复根 $\zeta_6$, $\zeta^{-1}_6$ 是所谓的 $6$ 次本原单位根.

    Theorem 2. Blass–Lawvere 定理 [blass-lawvere]

    • September 24, 2024
    • kokic

    $\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

    记 $B$ 是二叉树类型, 则存在一个 “极精确的双射” $B \xrightarrow{\sim} B^7$.

    显然并非所有 $\zeta_6$ 满足的等式都能提升到 $B$ 之间的同构, 如 $B^6 \ncong 1$. 自然的问题是, 哪些等式能提升到同构? 这个问题由下面的 Fiore–Leinster 定理 回答.

    Theorem. Fiore–Leinster [fiore-leinster]

    $\gdef\N{\mathbf{N}}$ $\gdef\Z{\mathbf{Z}}$

    设 $f,g_1,g_2 \in \N[x]$, 其中 $f$ 有非零常数项且 $\deg f \ge 2$. 若 $f(x) - x$ 整除非常值的 $g_1-g_2$ (在 $\Z[x]$ 中), 则在 $\N[x]/(x=f(x))$ 中, $g_1(x)=g_2(x)$.

    特别的, 取 $f(x)=1+x^2$, Fiore–Leinster 定理 表明, 若在 $\N[x]/(x=1+x^2)$ 中成立 $f(x) = g(x)$, 则存在 “极精确的双射” $f(B) \cong g(B)$. 在 $\N[x]/(x=1+x^2)$ 中可以演绎得到 $x=x^7$ 但无法给出 $1=x^6$. 对于前者 $x^7-x = (x^2-x+1)(x^5+x^4-x^2-x) = 0$. 再看 $x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)$, 这给出 $B^4+B^2+1 \ncong 0$, $B^4+B^2+B+1=B$.

    这套想法亦可应用于其他树结构, 如有根平面树, 其每个结点有 $0$, $1$ 或 $2$ 个子结点, 即 $T \cong 1+T+T^2$. 由 Fiore–Leinster 定理, 存在 “极精确的双射” $T \cong T^5$.

    栈置换–二叉树同构 [stack-tree-isomorphism]

    Definition 1. 栈置换 [stack-permutation]

    • November 06, 2024
    • kokic

    栈置换 (stack permutation) 也称作栈混洗 (stack shuffle). 给定一个非空栈 $A$ 和两个空栈 $B$ 与 $S$, 每次只允许 $(i)$ 弹出 $A$ 并压入 $S$. $(ii)$ 弹出 $S$ 并压入 $B$. 可以想见, 最终 $A$ 的元素一定会全部进入 $B$. 这样的 $B$ 就称为 $A$ 的一个栈置换.

    不难发现, $A$ 的所有栈置换其实就是 $A$ 的所有出栈可能. 熟知 $n$ 元素栈共有 $\frac1{n+1}{2n \choose n}$ 种出栈情况. 另一方面, $n$ 个节点能构成 $\frac1{n+1}{2n \choose n}$ 种二叉树, 两者的计算都可以在 Catalan 数的相关条目中找到. 这表明两者作为集合同构, 一个可以考虑的问题是, 如何实现该同构? 即, 具体地写出这个双射. 这方面的 开创性工作 来自 R. F. Hille.

    Definition 2. Hille 编码 [hille-encode]

    以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码.

    • 1 表示添加当前树节点的左子树. 例如 111 表示的树为 (⋅ (⋅ (⋅))).
    • 01 表示添加当前树节点的右子树. 例如 10101 表示的树为 (⋅ _ (⋅ _ (⋅))).
    • 而对于 01 前的 $k$ 个 0, 这些 0 用于表示将当前树节点回溯到前 $k$ 层. 例如 11001 表示的树为 (⋅ (⋅) (⋅)).

    注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲.

    由于我们的讨论不涉及具体元素, 不失一般性, 可以固定栈置换的入栈顺序为 $123\cdots n$. 同时这些数字也是二叉树节点的标签. 影响出栈序列的只有压入和弹出两个操作, 而构建二叉树允许的操作粗看起来要多一些. 因此首先需要通过一些技巧将二叉树构建操作的表示简化. 我们将栈的压入和弹出分别编码为 1 和 0, 并将栈置换对应的二进制序列称为栈编码. 对应的, 以 Hille 编码 刻画二叉树的构建.

    Example 3. $n=3$ [stack-permutation-000A]

    • November 06, 2024
    • kokic

    以下写出三节点二叉树的所有 $5$ 种情况, 以展示这些树的二进制序列如何对应到栈置换. 此处二进制序列按栈弹空为标准, 补充了末尾的零.

    这个过程的反向实际上并不平凡, 如果只考虑 $n=3$ 也就是上图的情况, 敏锐的读者可以发现, 这些栈置换其实就是二叉树按节点添加顺序 1 编号后的中序遍历序列 2. 我们接下来就要解释这到底不平凡在哪里. 首先是对原始文献的一个观察, Hille 原始文献 当中提出的算法实际上存在错误, 将之改写成 Lean4 语言, 即

    只要考虑下面这个例子即可发现, 将一棵二叉树转化为它的 Hille 编码并非是简单的中序遍历.

    可以验证, 从 110100100 这个编码出发, 无法直接恢复原本的 , 其正确的 Hille 编码应该为 1101000100. 同时我们也可以解释, 为何中序遍历在许多情况下能够得到正确的 Hille 编码.

    Exegesis 4. 栈编码与 Hille 编码的等价性 [stack-permutation-000B]

    • November 06, 2024
    • kokic

    首先容易验证的是, 中序遍历总是能够给出二叉树 $b \in B$ 到栈置换 $s \in S$ 的映射, 而对于每一个栈置换 $s \in S$, 都能够写出唯一的二进制序列, 即栈编码 $c \in C$. 不考虑末尾连续的 0, 当栈编码 $c$ 与二叉树 $b$ 的 Hille 编码 $h \in H$ 相同时, 对 $B$ 直接进行中序遍历便能得出正确的 Hille 编码.

    $$ \begin{CD} B @>>> S \\ @VVV @VVV \\ H @>>> C \end{CD} $$

    Proof. [stack-permutation-000C]

    • November 06, 2024
    • kokic

    记 $B \to H$ 为 $f$, 根据 Hille 编码 的定义, $f$ 是一个双射. 根据二叉树的性质, $g: B \to S$ 是中序遍历, 前文已经固定栈置换的入栈顺序为 $123\cdots n$, 这样一来就固定了 $B$ 的层序遍历, 因此 $g$ 也是双射. 现在来看 $h: S \to C$, 这显然也是一个双射. 最后, 我们能够从 $h \in H$ 当中恢复出 $c \in C$ 的信息, 只要将 $h$ 序列视为栈编码, 并且忽略空栈的弹出, 这就意味着 $H \to C$ 是满射, 随后利用 $C \to S \to B \to H$, 这样就得到了 $H \cong C$.

    现在, Hille 原文所使用的 encode 算法就是 $h \circ g: B \to C$, 而预期的正确实现则是 $f$, 因此两者在结果上相差一个同构.

    Exegesis 5. 有效长度估计 [stack-permutation-000D]

    • November 06, 2024
    • kokic

    $\gdef\spaces#1{~ #1 ~}$

    另一个可供探究的问题是 Hille 编码的有效长度 $L$, 这里有效长度指的是 Hille 编码去除末尾连续的 0 后所得的字符串长度. 固定二叉树的节点个数 $n$, 这 $\frac1{n+1}{2n \choose n}$ 棵树的有效长度最短当然是 $n$. 当 $n=0$ 时 $L=0$, 当 $1 \le n \le 3$ 时 $L \le 2n-1$, 而当 $3 \le n$ 时 $L \le 3n-4$, 即

    $$ n \spaces\le L_n \spaces\le \max(0, 2n-1, 3n-4) $$

    1

    即按照 Hille 编码逐步添加节点的顺序.

    2

    如二叉树 1101000100 按添加顺序对节点编号, 然后做中序遍历得到的是 2314.

    综合微分法 [synthetic-differential]

    • May 9, 2024
    • kokic

    $\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$ $\gdef\str#1{{\footnotesize #1}}$

    $\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$

    我们首先观察朴素的数值微分的计算过程. 待微分函数为 $(x+3)^2$, 此处不妨取 $x=-2$, $h=10^{-5}$, 这一位置的导数 $A$ 近似为

    $$ A \quads\approx \frac{f(x+h)-f(x)}h \eqq \frac{(1 + 10^{-5})^2 - 1^2}{10^{-5}} \eqq 2.00001 $$

    并且如果试图得到与预期的 $A=2$ 更接近的结果, 则须将无穷小近似 $h$ 选取为更靠近 $0$ 的数值, 这对于浮点精度有限的计算机来说极为不利.

    而朴素的符号微分视表达式为树结构, 通过遍历树并对符合模式的节点应用求导规则. 即

    $$ \begin{aligned} (x+3)^2 & \spaces\to (x+3)'(x+3) + (x+3)(x+3)' \\ & \spaces\to 1 \cdot (x+3) + (x+3) \cdot 1 \\ & \spaces\to 2x+6 \end{aligned} $$

    此时再应用 $x=-2$ 得到 $A=2$. 这个做法在结果上可行, 但处理复杂的表达式时, 中间过程本身会产生大量新的结点, 使递归遍历的实际时间达到指数级 $\mathcal{O}(2^N)$.

    有没有方法可以既避免递归又减少中间结点呢? 我们先看一个涉及复数域的观察.

    Exegesis. 复步微分法 [complex-step]

    • May 13, 2024
    • kokic

    $\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

    考虑光滑函数 $f(x)$, 其在 $x=a$ 处可表为关于 $X$ 的 Taylor 级数 1 $f(a) + f'(a)(X-a) + \text{etc.}$, Mathworks 的创始人 Cleve Moler 约 60 年 2 前考虑了借用虚数单位 $i$ 的数值微分, 相关文献称为 complex step 微分法 3, 注意

    $$ f(a+i h) \spaces= f(a) + i h f'(a) - \frac{h^2}{2!}f''(a) - \frac{ih^3}{3!}f'''(a) + \cdots $$

    这个其实就是将 Taylor 级数的每一项完全展开, 在 后续 的计算中也会继续用到. 如此便有 $$ \frac{\partial f}{\partial x} \spaces= \frac{\Im f(x+ih)}{h} + \mathcal{O}(h^2) \quads\implies \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

    这个方法最初被设计用于处理数值微分问题, 但稍加思考就能发现, 该过程也适用于符号微分. 与前一个问题所改进的结果的精度不同, 用于 符号微分 时, 所取得的优势是更精简的中间表达式和非递归的计算过程.

    1

    习惯上会混淆 $x$ 与 $X$, 这里做出区分.

    2

    即 1967 年. 不过这个名字要等到 1998 年, William Squire 和 George Trapp 才正式提出.

    3

    按方法的内容来说, “complex step 微分” 可以翻译为 “复步微分”.

    选取同样的 $h=10^{-5}$, 以下计算表明 Cleve 方法相比前文基于有限差分的数值微分方法能够很好的避免精度损失.

    $$ \frac{\Im(1 + 10^{-5}i)^{2}}{10^{-5}} \eqq \frac{\Im(\square + 2 \times 10^{- 5}i)}{10^{- 5}} \eqq 2 $$

    实际上此处 $h$ 的选取, 只要其非零, 从而带有 $i$ 的项不消失, 就不会影响到最终的结果. 换言之, 这个方法从根本上来说, 是无关于 $h \in \R\smallsetminus\{0\}$ 和 $i$ 的, 只是在数值计算时借由复数算术和复函数值可以免去一些幂零结构的讨论. 一旦意识到这一点, 我们便可以将

    $$ \frac{\partial f}{\partial x} \quads\approx \frac{\Im f(x+ih)}{h} $$

    当中的近似 “$\approx$” 修正为严格等于 “$=$”, 这只需要将 $\{z \in \C : z^2 = -1\}$ 替换为 $D = \{x \in R : x^2 = 0\}$, 问题就来到了如何构造这样的 $R$ 使得 $D$ 中有非零的元素, 这样的结构实际上会动摇经典逻辑中对于排中律的看法.

    Definition. 对偶数 [dual-number]

    • May 14, 2024
    • kokic

    $\gdef\R{\mathbf{R}}$ $\gdef\C{\mathbf{C}}$

    一种通俗的讲法是, 认为对偶数 $R[x]/(x^2)$ 可以作为复数 $\R[x]/(x^2+1)$ 的类比. 如果有读者能轻率地暂时忽略 $R[x]/(x^2)$ 这种结构的存在性, 或者说接受了下面的 $d$ 的定义

    $$ \exists ~ d \in R\smallsetminus\{0\}, ~ d^2 = 0 $$

    不能接受也很正常, 因为这轻易就会导致某个经典逻辑中的 矛盾. 为此我们需要下面的准备工作.

    Axiom. Kock–Lawvere [kock-lawvere]

    • May 13, 2024
    • kokic

    $\gdef\spaces#1{~ #1 ~}$ $\gdef\R{\mathbf{R}}$

    首先需要强调的是, 这个公理所涉及到的结构的有效性全都依赖于 意象理论, 而相关基础的严格性保证基本上在 1970 年之前就已经由 William Lawvere 完工. 记 $\mathcal{E}$ 是光滑空间之间的光滑映射构成的范畴, 同时假定 $\mathcal{E}$ 还是笛卡尔闭范畴, 也就是 $\mathcal{E}$ 中的箭头对笛卡尔积封闭.

    我们可以从 $\mathcal{E}$ 中选出一条几何直线 $R$, 通过指定 $R$ 上两点 $0$ 和 $1$ 之间的距离作为单位长度来确定其他线段的长度. 发挥一些古希腊精神, 线段的移动可以给出 $R$ 上的加法, 尺规作图所构造的 相似三角形 能给出 $R$ 上的乘法 $\gamma = \alpha\beta$.

    Methods in Algebra - Volume 1, p. 369

    因此 $R$ 带有交换环结构, 并且允许经典数学中的对象实数环 $\R$ 成为 $R$ 的模型, 注意这里我们只能考虑 $\R$ 作为环的部分, 因为 $R$ 中存在着幂零元.

    Kock–Lawvere 公理说的是, 对任意映射 $f: D \to R$, 存在唯一的 $a,b \in R$, 使得

    $$ f(\epsilon) \spaces= a + b \epsilon, \quad \forall \epsilon \in D $$

    将这里的 $a$ 换成 $f(0)$, 并完全使用量词叙述, 则是

    $$ \forall ~ f \in R^D, ~ \exists! ~ b ~ \text{s.t.} ~ \forall ~ d \in D \quad (f(d) = f(0) + b d) $$

    如果说这个公理的形式还不足以暗示它的目的, 那么下面这个推论就完全能做到了.

    Corollary. 所有函数都光滑 [kock-lawvere-000A]

    • May 13, 2024
    • kokic

    $\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$

    对任意函数 $f:R \rightarrow R$, 存在唯一的函数 $f':R \rightarrow R$ 满足

    $$ f(x + \varepsilon) \spaces= f(x) + f'(x)\varepsilon,\quad \forall ~ x \in R, ~ \forall ~ \varepsilon \in D $$

    这个通常作为 Kock–Lawvere 公理 的推论出现, 不过从 $\mathcal{E}$ 的定义来看, 这才是整套框架真正的目的之一. 即, 为全体函数恢复牛顿时期 “幂零无穷小量” 计算上的直观, 而不导致矛盾.

    Axiom is incompatible with the law of excluded middle. Either the one or the other has to leave the scene. In Part I of this book, the law of excluded middle has to leave, being incompatible with the natural synthetic reasoning on smooth geometry to be presented here. In the terms which the logicians use, this means that the logic employed is ‘constructive’ or ‘intuitionistic’. We prefer to think of it just as ‘that reasoning which can be carried out in all sufficiently good cartesian closed categories’.

    — Anders Kock, Synthetic Differential Geometry

    无论是单纯接受这个 公理 还是认可该公理存在的舞台 $\mathcal{E}$, 其实都会导致完全相同的结果, 那就是 $\mathcal{E}$ 当中一般函数的性质发生了变化, 让所有的函数都变得光滑. 与之相对的, 这样的好性质所要求的代价是, $\mathcal{E}$ 当中不能使用经典逻辑中的选择公理、排中律、反证法等命题.

    这样一来, 我们所说的 “将近似修正为严格等于” 就可以精确表示为

    $$ \frac{\partial f}{\partial x} \quads= f(x+\epsilon) ~ \str{中} ~ \epsilon ~ \str{项的系数} $$