码之道 信息.pptVIP

例如”42153”的编码可以用下面的过程来求出： 首先，第一位比4小，后四位不确定的一类有72个。 第一位等于，第二位小于，后三位不确定的有6个； 如此计算下去，最后得到累加和为80，也就是”42153”的编码。 而问题一的译码也可以通过这样的方法解决。 * 和刚才提到的编码方式类似，我们仍然用分类累加的方法来译码。 对于刚才例子中得到的编码80—— 首先累加第一位，当累加到4的时候超过了80，于是确定第一位是4，累加首位为1、2或3的字符串72个； 同样的可以得出第二位是2，累加到78…… 如此这样下去，最后就可以得到所求字符串了，这样复杂度和刚才的编码一样都是O(字符串长度*字符集大小的平方) * 普遍的，对于刚才两个问题，（click）当所求字符串长度为n，字符集大小为m时，（click）我们可以做到O(nm^2)，（click）于是我们将复杂度从阶乘级别优化到了多项式级别！ * 通过刚才的例题，我们看到了编码译码思想与方法的巧妙应用，而在我的论文中，还提到了以下思想方法在编码译码中的应用： （click）数论、组合计数等数学知识 （click）递推、动态规划、枚举、贪心、有哪些信誉好的足球投注网站、排序、构造等算法 （click）堆、树状数组等特殊的数据结构 * 编码译码的灵活多样，使得其在各个方面都有广泛应用，可谓： 编码若宇。宇善容万物而不乱，处万物之所源，故几于道。 而缤纷多彩的编码译码思维方法的经典的应用，我的论文中提到了以下几个： 用于无损数据压缩的熵编码哈夫曼编码（click） 最早发明用来避免讯号传送出错的格雷码（click） 针对特殊的结构——标号树的普吕弗编码（click） 常用数据结构散列表的映射函数哈希函数（click） 下面我们来探索普吕弗编码。 * 普吕弗编码的对象——标号树的定义是：顶点标号为1至n的n顶点树。 我们知道不同的n结点标号树的数量是n的n-2次方，凯莱曾在1889年给出了第一个证明，1918年普吕弗给出了另一个证明，其中他提出了普吕弗序列。 * 普吕弗编码的编码过程是这样的 对于树T，我们不断从中移除标号最小的叶子，直到T只剩下两个结点。 此过程中第i次移除叶子的相邻结点的标号，就是普吕弗序列的第i项。 值得注意的是，普吕弗编码提供了标号树与整数序列的双射。 * 请看幻灯，我们以这棵树为例来看看如何生成普吕弗序列： 首先删除最小的节点4，其相邻结点为1，序列第一项为1； 此时最小节点为6，删除，插入2； 删除2，插入1； 删1，插3； 删7，插3； 删3，插5； 于是我们得到了这棵树的普吕弗编码 * 设普吕弗编码是{a1, a2, …, an-2}，(click)我们在其最后添加一项n。 (click)假设从树T生成序列a的时候第i次移除的叶子是bi，那么ai是其相邻点，于是(ai, bi)就是T中的一条边，这n-1项就是树T的所有边。 我们按照i从小到大的顺序计算bi： 对于每个bi，(click)他是不在ai到an-1中且不是b1到bi-1的最小结点(click)，这样我们就可以用堆在O(nlogn)的时间内完成普吕弗译码过程。 * 我们来看看这道竞赛题：刚才提到的一一映射性质，就可以应用在此题上。 题目大意是：给出标号树每个顶点的度数，求满足限制的标号树个数。 * 根据普吕弗编码的生成方式，我们知道：在满足要求的标号树的普吕弗编码中，标号i会出现其度数减一次。 于是我们可以用重集全排列得到合法标号树个数为——n-2的差的乘除以各顶点度数减一的差的阶乘的积。 * 和普吕弗编码一样，在实际应用中，我们用各种巧妙的思维和灵活的方法，创造出缤纷多彩的编码译码方式，（click）并让他们在各个领域发挥着独有的功效，解决了不同的实际问题。 * 通过刚才的简单讲解，相信大家都会同意： （click） 编码译码就如同水一样：水是生命之源，编码译码是信息之源；水亦柔亦刚，编码译码也同样灵动。 （click） 或许道可道，非常道，我的论文仅仅是抛砖引玉，编码译码的广阔世界还等待着我们去继续探索。 如果您对编码译码感兴趣，欢迎下来和我交流讨论。 * 最后，我要 感谢我父母对我无私的关爱！ 感谢张君亮老师的认真指导！ 感谢各位教练和我的朋友们给我的帮助！ 感谢中国计算机协会提供这次上台讲演的机会！ 我还要感谢各位评委和大家的耐心倾听，谢谢！ * 欢迎大家就我刚才讲的内容提问。 * 周梦宇 Moony Chou 成都七中 zmy90320@ etc. 信息 信息论 无所不在的比特——小小的0和1 The Mathematical Theory of Communication 《通信的数学理论》 By Claude E. Shannon （香农） 为信息论奠定了基础 电报、电话、广播、