图像处理课期中要写一个图像拼接程序.

这方面的技术当然已经很成熟了, 开源界最著名的当属 hugin, 拼全景图效果非常好. 在学术界也已经不是难题了, Lowe 在 IJCV2007 的一篇 Automatic Panoramic Image Stitching using Invariant Features 是一个完整的流程介绍. MSRA 的 Szeliski 有过一本几十页的 Image Alignment and Stitching: A Tutorial, 也详细的介绍了图像拼接的众多方法. 我基本就照着 Lowe, Szeliski 的一堆论文的方法在搞.

人智课一次作业是写一个 A* 程序算 八数码问题的最优解. 一个自然的问题是, 什么样的初始状态有解?

一个熟知的结论是, 将矩阵元素排成一排, 忽略空格, 当且仅当逆序对个数为偶数时此问题有解.

必要性很好证明, 因为观察可知所有的移动操作不会改变逆序对个数的奇偶性. 那充分性呢?

要证明充分性, 需要将矩阵用另一种方式展开成一排:.

面试中曾经遇到这么一道概率题:

一只猴子随机敲键盘上的 26 个字母, 期望在多少次之后能首次打出 "hulu"?

当时只是直觉觉得答案应该是 , 没有想出很好的做法. 想出来的唯一方法是列一个四元线性方程组, 四个变量定义如下, 有点像 Markov Chain 的感觉:

1. 打出 hulu 的期望次数
2. 已打出 h, 从现在开始算打出 hulu 的期望次数
3. 已打出 hu, 从现在开始算打出 hulu 的期望次数
4. 已打出 hul, 从现在开始算打出 hulu 的期望次数

关于效率..

• xset r rate 200 40

  设置 X Server 接收键盘事件的频率. 把按住某个键时触发的事件频率变多, 就相当于键盘变灵了一样. 200, 40 只是比较适合我的一组参数.

  用了它以后的一个结果是, 没法习惯别人的电脑了, 嫌翻页慢..

• vim-accelerated-jk

  一个 vim 插件, 功能是按住 j 或 k 时, 触发 jk 事件的频率随按住的时间而增加. 速度可调, 和 xset 配合之后, 在 vim 里翻页如飞, 基本不需要C-D, C-U 了. 虽说过度用 jkhl 其实是不好的习惯.

概率论课, 一项作业是写篇小论文. 错排数是高中就总结过的, 恰好概率论某次习题课还讲到, 就花了一周时间又整理了下错排数 (Rencontres Number) 有关的东西. pdf 放在 github.

对于排列 , 设 是它的不动点集合:

设 是所有可能 元排列的集合, 则错排数 可定义如下:

高中搞竞赛的同时会每天也搞电脑, 竞赛资料全是网上找的, 也认识了一堆一堆的人.. 然后, 跟很多人一样养成了一种强迫症.. 就是.. 搜集 pdf..

高中搜集的数学竞赛各种, 现在还保留着的 pdf 还有 1G 多.. 也做过自己整理的事情, 比如把各年联赛题找出来整理了个 25 年联赛题集.. 总之强迫症嘛, 逼着自己做完.

带来的一个结果就是, 搜索能力变强了. 比正常的 google 一下 baidu 一下 ishare 一下要有效的多那时候有北大的学长让我帮忙找一篇很难找的论文, 我搞了三四个小时的样子, 一直都在不同的途径上找这篇论文, 现在可不会这么闲了.. 是一篇 Hilbert 的, 由于那个时代的杂志现在都没有收录在乱七八糟的网站, 搜了好久最后在 Gottingen 的某网站找到了图片版的大概就是经历了很多这样的事之后, 搜论文的话, 对几个常见的网站也都比较熟了.. 比如记得有次也是研究了好久 springer 上的论文下载.

数据结构课上, 比较二分查找与 Fibonacci 查找. 举例时为了方便, 就让数组长度是 8, 因为 8 既是 2 的幂又是 Fibonacci 数, 方便演示算法. 邓俊辉老师随口问了一句像这样的数还有没有呢. 答案是没有的.

Fibonacci 数有一个有趣等价条件: 是 Fibonacci 数当且仅当 中某一个数是完全平方数.

• 必要性很好证. 验证如下等式: 其中 是以 定义的 Fibonacci 数, 是以 定义的 Lucas 数

• 充分性: 于是 为 中的单位元, 那么 , 就可以得到 了.

有了这个性质之后, 只需要考虑 有没有非平凡解即可. 这个很容易就.. 略了.

后来发现一个很强的 Carmichael 定理, 可以直接秒这道题. 定理的内容是: 对每个 必定包含一个没有在之前的 Fibonacci 序列中出现的因子.

在翻 Matrix67 的 思考的乐趣的时候, 看到集合论那里, 依次证明了有理数, 代数数, 可计算数, 可定义数的可数性, 甚舒畅. 然后用经典的 Cantor's Diagonal Argument 证了实数的不可数性, 并说明了此方法对有理数不可用, 因为对角线生成的新数未必是有理数.

然后我想, 对角线法用在可计算数上似乎也可以啊.. 假设可计算数可数, 排成一列 之后, 按照对角线法取出一数, 保证取出数 满足 , 则 也没有被列出. 而进一步, 如果我们规定取数时的对应法则 , 令 无不动点, , 那么取出的新数也就是可计算的了. 那按照 Diagonal Argument, 可计算数不就不可数了?