冬令营17日

 

首先说一下，今天的内容是我目前为止的收获最大的，因为今天的内容很多都涉及到了数学，还有就是晚上论文答辩的时候，吴文虎教授特别提到了一些有关信息学前景以及有关我们学习信息学的目的的问题，吴教授的发言我应该会在冬令营录像发下来之后录进电脑。

 

上午

 

内容: 信息学竞赛中的数学建模初探

授课: 李学武, TGC

 

李学武教授我仰慕很久了，因为李教授在数学理论方面建树颇丰，很有研究。今天听他的讲课更是深有感触。其实学信息学，数学是最重要而且密不可分的模块，不，不是模块，信息学就是数学的一部分，信息学研究的用强大的计算速度解决数学问题，其中有求解的，也有证明的，关于机器证明的那一部分，今年的集训队论文有人提到了，还不够彻底，我记得有一套书叫做《好玩的数学》中有一章就是讲的机器证明，很经典。这部分我以后再谈。

李教授讲的就是有一本数学名著《具体数学》中的一些经典问题，这里我提一下比较重要的部分。

递推关系与求和: 引入是 Josephus (约瑟夫)问题，我们已经知道，关于约瑟夫问题，有模拟的方法可解，但是，有没有更好的方法呢？答案是肯定的，我们观察每次报数出圈，有当前为偶数号的一部分人出圈，接下来，又是新一轮的报数出圈，而且有一部分人成了新的偶数号，我们不难发现，整个出圈的过程，就是一个递归的过程，好，那么我们定义 J(n) 为在有 n 个人的圈上，最后剩下来的人是几号。易得出如下三个递归定义的表达式：

(1)    J(1)=1

(2)    J(2n)=2J(n)-1

(3)    J(2n+1)=2J(n)+1

其中 n 为正整数。

然后我们易得出一个闭形式 (closed form) 的表达式: J(2^m +l)=2l+1.

我们来看一下能不能再化简，我们把 n 化为一个 m 位二进制数，第一位为 B1，最后一位为 Bm，那么我们从那个闭形式表达式惊异地发现，每一次 J(n) 操作，只是把 n 这个二进制数的第一非零位 B1 ，移到 Bm 之后！多么神奇的性质啊！（原因请自己推导）那么，在进行多次 J(n) 操作之后，在进行 J(n) 操作值就会不变了，原因是 n 的所有二进制位都变成 1 了，我们把这样的值叫做“不动点”，这个概念在复合函数中经常提到。多次调用这个函数，不动点会出现在原 n 二进制数中 1 的个数 k 次以下（因为尾部可能有连续的 1），而不动点的值就是 2^(k+1)-1.

我们再把刚刚那些递归定义的式子拓展一下：

(1)    f(1)=α

(2)    f(2n)=2f(n)+β

(3)    f(2n+1)=2f(n)+γ

我们再来尝试用闭形式来描述这些递推式。

观察后知，我们把这个函数写成 f(n)= A(n)α+B(n)β+C(n)γ.

我们列表发现，A(n)事实上是等于 trunc(log n), 而 B(n) 呢，则在 A(n) 不变的周期中随着 n 的增加而从 A(n)-1 递减到 0, C(n) 则恰好相反，在 A(n) 不变的周期中随着 n 的增加而从 0 递增到 A(n)-1. 这些结论，事实上可以由归纳法证明。

接下来，李教授讲了一些关于 sigma 式的化简，由于过于简单，我在这里就不再叙述了。但是李教授提出的思想却是相当好的：

递归<–>求和

  |      |

  >闭形式<

在有诸多表达式形式的情况下，我们要熟练掌握表达式的转化，这样我们才能高效地分析问题，从而解决问题。但这又需要我们有相当扎实的数学理论功底，以前对于名言“数学是无穷的科学”的理解一直停留在“数学题是做不完”的层面(哈哈！)，而我们现在发现，数学的代数变换，几何变换，以及数形结合还有最新的机器解题（信息学）等方面的探索是无穷无尽的，数学是最基础的自然科学，它的发展推动着整个科学界的发展。

下午是 TSU 的周源同学讲随机化算法，由于牵扯到很多概率的知识，我留到以后再讲；晚上答辩时吴文虎教授的讲话，我准备单独地写一篇文章，就不在这里写了。