算法合集之《信息论在信息学竞赛中的简单应用》.ppt

《算法合集之《信息论在信息学竞赛中的简单应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在信息学竞赛中的简单应用侯启明信息论信息论简介信息论是关于信息的本质和传输规律的科学的理论。通过它可以很方便地得到某些交互式问题的一个较好的步数下界(“信息论下界”)让我们先来看一些信息论的基本理论理论基础定义：如果一个随机变量x共有n种取值，概率分别为p0,p2,......,pn，则其熵为H(x)=f(p0,p2,......,pn)=-∑Cpilogpi定理1：在得到关于随机变量x的一个熵为h的信息后，x的熵将会减少h。定理2：当一个随机变量的各种取值概率相等时，它的熵最大。这些理论看上去和某些题目关系密切，不是吗？那么，具体应该如何运用呢？让我们来看一些例子：我

2、们宿舍二楼到三楼之间楼梯的窗户外面是相邻的一个平房的房顶。在那一带栖息着三只浑身雪白，有着一只蓝眼睛和一只绿眼睛的——例1：验证一下定理1猫！ABC例1：验证一下定理1在天冷的时候，它们喜欢趴在楼内的暖气上。于是，每只猫就有了两种状态：在屋内和在屋外。因此，三只猫的状态共有8种可能情况，假设它们是等概率的。现在，我在一楼的小卖部。由于种种原因，我希望知道猫当时的状况，因此，我往上看了一眼，结果发现在这个位置只能知道屋内猫的只数……例1：验证一下定理1问题1：把所有猫的情况作为一个随机变量x，则当我在小卖部的时候，x的熵是多少？解答1：由于8种情况的概率相等，所以：H(

3、x)=f(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=log8问题2：我看一眼所得到的信息y的熵是多少？解答2：由于猫的只数共有0,1,2,3四种情况，概率分别为(1/8,3/8,3/8,1/8)，所以：H(y)=f(1/8,3/8,3/8,1/8)=log8-6log3/8例1：验证一下定理1问题3：我看完之后，x的熵H'(x)是多少？解答3：此时猫的只数为0,1,2,3的四种情况的概率依次是(1/8,3/8,3/8,1/8)，而每种情况的熵分别为(0,log3,log3,0)，所以此时H'(x)的数学期望为：H'(x)=1/8*0+3/8*lo

4、g3+3/8*log3+1/8*0=6log3/8可以发现H(x)=H(y)+H'(x)。定理1得到了验证。例2：Rods(IOI2002)一个Rod是一个由至少2个单位正方形连成的水平或竖直的长条。在一个N*N的方阵中，放了水平和竖直两个Rod。如图1，其中Rod用X表示。图1例2：Rods(IOI2002)两个Rod可能有公共方格，比如在图1中，方格（4，4）无法确定是仅属于1个Rod还是同时属于两个Rod。因此，在这种情况下我们假定它同时属于两个Rod。这样，图中竖直Rod的上端点是（4，4）而不是（5，4）。图1最初我们并不知道两个Rod的位置，你的任务是编程序

5、找出它们的位置。你只能通过库函数rect(a,b,c,d)来定位两个Rod。如果至少一个属于某个Rod的方格落在矩形[a,b]x[c,d](如图1中阴影区域)内的话，rect返回1，否则返回0。例2：Rods(IOI2002)图1对每个测试点，如果你的程序没有正确确定两个Rod的位置或调用rect超过400次，你将得到0分。否则，如果调用rect的次数至多为100，你将得到5分；在101到200间，你将得到3分；在201到400间，你将得到1分。例2：Rods(IOI2002)图1比赛时我很快想到了一个最多调用rect函数6log2n+C（某个常数）次的方法，但是因为这

6、个数差不多刚好达到100，所以我在这时就开始试图优化上式中log2n的系数，结果徒劳无功，反而耽误了时间。因此，看过答案以后，我试着从信息论的角度分析了一下这个问题：例2：Rods(IOI2002)6log2n+C?由于题目中没有涉及到概率，因此假设所有情况都是等概率的。所以，设Rod的摆放方法为随机变量x，x所有可能的取值数为f(n)，那么x的熵H(x)就等于log(f(n))。而由于库函数只有两种返回值，其熵最大为Hmax(y)=log2。因此，rect调用次数的信息论下界就是L=H(x)/Hmax(y)=log(f(n))/log2=log2f(n)例2：Rods

7、(IOI2002)在n*n的方阵中放1个Rod（无论横竖）共有n*C(n+1,2)种方案，放两个相交的Rod共有C2(n+2,3)种方案，所以：f(n)=(n2(n+1)/2)2-((n+2)(n+1)n/6)2=(2n6+3n5-n4-3n3-n2)/9当n充分大时：L=log(f(n))/log2>log2(2n6/9)≈6log2n-2.2例2：Rods(IOI2002)下面讨论f(n)的值：由于各种原因，不一定总是使两种返回值概率相等，所以最坏情况下的调用次数往往达不到信息论下界，两者大约相差一个常数，因此，可以认为6log2n+