清华的数学学习

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

现状

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

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

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很靠谱.

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})$.

Number of Fixed Points in Random Permutations

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

对于排列$\pi$, 设$\mathcal{F}(\pi)$是它的不动点集合: $$ \mathcal{F}(\pi) = \{ k \in [1,n]\cap \mathbb{N} : \pi(k) = k \} $$

设$\Pi_n$是所有可能$n$元排列的集合, 则错排数$D_{n,k}$可定义如下: $$ D_{n,k} = | \{ \pi \in \Pi_n : | \mathcal{F}(\pi) | = k \} |, k = 0,1,\cdots n $$