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

信息纶 在信息学竞赛中的简单应用 侯启明 信息论简介 信息论是关于信息的本质和传输规律的 科学的理论 通过它可以很方便地得到某些交互式问 题的一个较好的步数下界(信息论下 让我们先来看一些 信息论的基本理论 理论基础 定义:如果一个随机变量x共有n种取值, 概率分别为pop2y,pn,则其熵为 H(x)=f(popp2xypn)= Cp logp1 定理1:在得到关于随机变量x的一个熵 为h的信