Problem of Two Eggs

在知乎上看到这么一道题, 原题描述的不太严谨, 其大意是:

一幢 200 层的大楼,给你两个鸡蛋. 如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从前 n-1 层扔鸡蛋都不碎. 这两只鸡蛋一模一样,不碎的话可以扔无数次. 已知鸡蛋在0层扔不会碎.

提出一个策略, 要保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

清华的数学学习

貌似中文标题的都偏吐槽向.

现状

清华的"工科数学基础课", 课堂教学方式大致都是 抄课本.

当然, 抄有不同的抄法. 有的老师抄在黑板上, 有的抄在一学期改一页的ppt上. 一般他们在抄的同时会把文字部分匹配出来读一读, 遇到公式的话有的会读, 有的用指示代词替换掉了, 每个知识点下面抄一个例题. 总之像是个可以写程序控制机器人来完成的活.

Facts About David Hilbert

没错, 这篇文章其实是Cantor, Gödel, Turing这个主题. 我发现只要关于他们的东西都很容易让我看high..

最近在看那本The Annotated Turing. 书中第三章以David Hilbert为主线, 介绍了20世纪初的几十年里数理逻辑与集合论的发展. 想一想的话, Hilbert的确是将Cantor, Gödel, Turing联系起来的关键人物, 然而这段历史我以前知道的并不细致, 而且关于Hilbert's Program, Hilbert's Problems 的故事各个地方说的都乱七八糟的自己也不清楚了, 于是做个记录.

Monte Carlo Tree Search & Monte Carlo Ray Tracing

这学期有两个有意思的大作业都跟Monte Carlo有那么点关系.


人智的大作业是写一个Connect Four 游戏的AI. 当然由于原本这个游戏是有必胜策略 的, 所以老师对这个游戏做了小修改. 给了50个测试AI, 编号2~100的偶数, 越牛的编号越大, 让我们打着玩, 评测时用另外一批AI.

建议的方法是$\alpha-\beta$剪枝, 但是写出来之后效果不行, 貌似缺一个好的估价函数. 但是编估价函数又有点蛋疼....这时候 maskray, zxytim, blahgeek 纷纷表示Monte Carlo Tree Search很靠谱.

关于张益唐的一些八卦

今天听老师说了一些关于Yitang Zhang的八卦相当感慨

因为文革原因,上北大的时候已经20多岁了

78级北大数院公认最优秀的毕业生

硕士在北大师从老潘学解析数论

84年丘先生回国到处演讲招学生,挑选了很多优秀的中国学生, 当时身为San Diego院长的他一年招了20多个中国学生去San Diego,他们几乎都成为了当今最牛的中国数学家

SIFT and Image Stitching

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

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

On the Solvability of 8-Puzzle

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

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

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


要证明充分性, 需要将矩阵用另一种方式展开成一排:$(a_{11}a_{12}a_{13}a_{23}a_{22}a_{21}a_{31}a_{32}a_{33})$.

Recurrent Event

去年11月面试Hulu 的时候,曾经遇到这么一道概率题:

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

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

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

Work Faster

关于效率..

  • xset r rate 200 40

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

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

  • vim-accelerated-jk

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