atppp’s Blog

上个星期 Knuth 又出来讲 Computer Musing 了……高老头精神很好，幽默风格不减，现场笑声不断。记两小段：

… that’s when I first heard BDDs (Binary Decision Diagram), and I said, oh boy, I got put that into volume four of The Art of Computer Programming. Well, I started writing this part a year ago in May, so that’s more than twelve months, more than a year ago then you see. And, every other section of The Art of Computer Programming, well, I used to polish off a section in six weeks. Now, er… you know I am getting older and computer science is getting harder (laughter), so it’s taking longer now but I had no idea that I was gonna spend a whole year on it. But the more I looked into it, it was just… er… I couldn’t put it down. There’s so much stuff that needed to be in my book. … When people talk about combinatorial explosion which usually means the size of the problem is getting big; to me, combinatorial explosion means the size of volume four is getting big (laughter). I mean, there’s just so much stuff that has to be said about, even when I am sticking to what i considered the basics …

高老头提到他希望引用 Wikipedia 里面的一段话：In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD in the literature, used when the ordering and reduction aspects need to be emphasized).

… when I wanted to get permission to get quote from the Wikipedia, and they have been working all the laws for the other way around for when Wikipedia is quoting from me (laughter). But, anyway they said it was O.K. for me to quote the Wikipedia even though my book is not issued with the GPL.

高老头提到他幽默感时曾说：I don’t take everything too seriously. 对以上两段，也请勿 take too seriously…

Knuth 在 1984 年发过一片研究厕纸问题的论文（The Toilet Paper Problem，后收入 Selected Papers on the Analysis of Algorithms）。在很多卫生间都可以看到如右图所示的双卷卫生纸架，以防一卷用完时出现尴尬情景。Knuth 研究的问题就是一卷用完时另一卷平均还剩几张的问题。他论文里写道：世界上有两种人，喜欢从大卷里用纸的和喜欢从小卷里用纸的；但是无论是谁，如果碰到两卷都用完了，那就有麻烦了！（很多人都说 Knuth 是因为自己碰到过这个事情所以才写了这篇文章）。Knuth 在 Mathematical Writing 第 31 页 15. Excerpts from class, October 30 提到发表这个论文时遇到的麻烦。杂志编辑对这个图灵奖得主的论文评价是“在我们杂志上讲笑话是危险的！”。Knuth 最后同意修改有粪便学双关含义的论文章节标题，但是论文题目死活不肯改了，因为 Knuth 号称已经用这个题目做过两次演讲。最后编辑只好说：Your toilet paper is accepted！

Knuth 推导出的结果如上图所示（憎恨数学者请跳过此段） 。n 是厕纸初始张数（张的含义是单个人 D.B. 后使用的厕纸数量），p 是大卷厕纸爱好者的比例，M_n(p) 为一卷用完时另一卷剩余的张数。结果很符合逻辑：如果 p 很小，大部分人都用小卷厕纸，最后剩下的一卷肯定很大；而大卷厕纸爱好者一旦占优（p > 50%），则最后很有可能出现两卷厕纸差不多一起用完的情形（M_n(p) 极小）。一个细节问题是这篇论文里面的 Catalan 数定义略有不同，论文里的 C_i 是通常定义下的 C_i-1。

Knuth 推导出公式之后感叹：When a formula turns out to be so simple, it must have a simple explanation. But the author hasn’t been able to think of any direct proof.（统计学里常见，很多时候确实可以找到简单方法）Knuth 一直很追求简单性，写 TAOCP 里很多算法都要斟酌词汇找到最有效的表达方法，不过在厕纸问题上却碰了个钉子，于是直接把郁闷的心情写进了论文。Knuth 在厕纸问题论文最后感谢：I wish to thank the architect of the computer science building at Stanford University for implicitly suggesting the problem… 大牛是不是都喜欢搞笑，想起诺贝尔物理学奖得主 Ramsey 大师在巨著 Molecular Beams 的参考书目里有一条是这样的：RAM50e N. F. Ramsey, private communications and lectures (1950)。囧，private communication 一般表示和别的大牛私人通信，他居然自己和自己私人通信……

Knuth 更多八卦可以看收入水木精华区的 helloooo 的文章。Knuth 中文名字是高德纳，我们一般叫他高老头，高老头非常可爱，几个月会出来讲个学（Computer Musings 有视频）。

上面这俩是啥？是新的厕纸设备，只有使用完第一卷时才能使用第二卷（图片来源）。这么看来，Knuth 那篇论文完全是在自娱自乐，有统计学上的价值却不能解决实际问题。现在新厕所都用上面这类新装置了，（啊，我终于回到我写这篇文章的起因了）不过上个月我上厕所，发现两卷居然都被人用光了！看来这种新装置也不靠铺。当时我身上一没手机二没女朋友照片三没人民币，连选择的条件都没有，只好等有老大爷进来求他给我送点纸。更奇怪的是，过去了两天居然还没有人装上新厕纸，资本主义的效率是不是就是这么低啊？看来我碰到的恐怕不是什么小概率事件，而是清洁工罢工了……

说到资本主义的低效率，我住的公寓楼地下室的垃圾箱要维护，这一维护，居然就维护了三个多月，搞得垃圾通道完全停用，门口的临时垃圾箱一到周末就会满出来。据说他们把垃圾箱拆开了才发现少零件……零件来了每天叮叮咚咚敲一会儿就收工了，晕啊，修个垃圾桶就能修三个月，这就是资本主义！

这篇文章思维好跳跃，我最近逻辑有点乱……