本文要介绍的是我写的一个有趣的 Python 小程序,一个脱离了低级趣味的程序,一个有益于广大人民了解算法的程序。代码在 Github 上。
这个程序可以用来制作各种各样的算法动画,包含但不限于:
几年前在知乎上有这么 一个问题:
问题: 有哪些 \(\mathbb{Z}[x]\) 中的多项式,它们在有理数域 \(\mathbb{Q}\) 上是不可约的,而对任意素数 \(p\),模 \(p\) 以后在 \(\mathbb{Z}_p[x]\) 上都是可约的?
当时我给了回答,后来账号注销了,答案也一并删除了。现在把我的原答案贴在这里:
今天我要介绍一个 Markov 链采样中的精彩算法,叫做 coupling from the past (CFTP)。这个算法看似简单,实则充满玄机。我相信你可以在五分钟内理解算法的步骤,然后再花五分钟左右看懂算法的证明,但是我打赌你需要几个星期甚至更久的时间来细细回味其中奥妙。
为了引出算法,我们从一个计数问题开始:
问题: 下图是一个边长分别为 \(a,b,c\) 的平行六边形,其中 \(a,b,c\) 都是正整数,内角均为 120 度:
请问:用边长为 1 的菱形密铺它,有多少种不同的方法?
你可能经常听到这样一句话:“做数学要大胆假设,小心求证”。我们今天要介绍的故事主角平面分拆中的 Andrews 猜想就完美地符合这一点。两个看似风马牛不相及的计数对象,因为有着相同的计数序列,冥冥中被联系在了一起,启发三位数学家 Mill, Robins 和 Rumsey 解决了一个困难的组合学猜想。整个过程并无高深的内容,但是其中的“信仰一跃”和“灵魂一猜”构成了故事的高潮,而那些繁琐的计算过程不过是小心求证的注脚而已。
本文来自我几年前读 David Bressoud 的 (Bressoud 1999)
Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture
一书时的读书笔记。本文只介绍 DPP 的 Andrews 猜想,并仅使用初等的 \(q-\) 二项式定理作为工具。我这里采用的叙述方式与 Bressoud 的书不同:Bressoud 是把 DPP 的 Andrews 猜想和 CSPP 的 Macdonald 猜想统一用 \(q-\) 超几何级数一起解决的。Macdonald 猜想的证明似乎无法避免使用超几何级数的理论,但 Andrews 猜想是完全可以用初等的 \(q-\) 多项式解决的。
问题: 给定一个有限、无向的连通图 \(G= ( V,E )\),设 \(\mathcal{T}\) 是 \(G\) 的所有生成树组成的集合,怎样在 \(\mathcal{T}\) 中按照均匀分布进行采样?即设计一个算法,能够随机地给出 \(G\) 的一个生成树,并且 \(\mathcal{T}\) 中每个生成树被取到的概率是相等的。
常见的生成树算法如 DFS/BFS 算法、Prim 算法、Kruskal 算法等给出的生成树都不是完全随机的。例如,取 \(G\) 为 \(\mathbb{Z}^2\) 中 \(m\times n\) 的网格图,\(G\) 的任何生成树都是一个迷宫,把背景平面涂黑,把生成树的边涂白,就可以清楚地看到迷宫的结构。迷宫的任何两个房间 ( 即树的顶点 ) 可以通过生成树中唯一的路径相连,这样的迷宫叫做完美迷宫。
DFS 算法 ( 每次将新顶点的顺序打乱再入栈 ) 倾向于尽可能深地探索整个图,因此得到的迷宫往往包含长且蜿蜒的路径,死角 ( 即叶节点 ) 是很少的:

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器