蓝色的螺丝钉分享 http://blog.sciencenet.cn/u/dataminer 学识不多 兴趣挺广

博文

关于信息与计算的问题 精选

已有 6378 次阅读 2009-4-8 20:49 |个人分类:生活点滴|系统分类:观点评述|关键词:信息论,计算理论| 信息论, 计算理论

信息熵的基本意义是反映消息最少需要的平均编码长度。

计算理论主要是研究是计算复杂性的理论,计算复杂性一般主要指计算时需要的时间和空间复杂性,特别是时间复杂性。

信息论与计算理论有一个小小的桥梁,就是Kolmogorov复杂度。Kolmogorov复杂度描述的是一段计算机程序最少需要的编码长度。一般而言产生一条消息(注意是产生,而不是求解)的计算机程序的Kolmogorov复杂度与这条消息的最小编码长度近似。

根据信息论,一般而言消息是可以压缩的(这里专指无损压缩)。在通信中经常采用压缩技术来减少通信开销。压缩和解压缩程序本质上都是图灵机。因为压缩与解压缩都是无损的,所以压缩和解压缩并不改变消息的任何信息含量。从解压缩方来看,将压缩数据经过解压程序运算就得到了想要的数据。

现在考虑这么一个信息传递问题:

Alice要向Bob发送所有10位数以内的所有素数。她有三种选择:

     1. 是直接将所有这些素数传送给Bob;

     2. 将这些素数压缩(ZIP?)后和解压程序一起传送给Bob;

     3. 发送一个求解10位数以内所有素数的程序给Bob,Bob收到程序后,运行程序就可以得到这些素数了;

无论选择哪种方法,Bob都可以得到10位数以内的所有素数。问题是这三种方法是否等价?

从Bob最后要得到的结果来看,三者无疑是等价的(如果Bob对时间一点都不在乎)。

从信息论的角度来看,1和2等价是没有什么问题的,压缩与解压不过是对信息的不同编码方式进行转换,不会改变信息的任何内容。但是3呢?从信息论的角度来看,3和1,2应该是不同的。因为Alice发送的消息与Bob需要的消息是完全不同的东西,用信息熵来度量的话,Alice发送的程序的最小编码长度(或者Kolmogorov复杂度?)可能远小于这些素数的最小编码长度(但是Bob却还是能得到他需要的素数)。

如果考虑额外的计算开销。3的方法给Bob带来了额外的开销,3不能和1等价,但是方法2同样也给Bob带来了额外的运算开销。解压缩程序与计算素数的程序都是图灵机,并无本质上的不同。所以如果考虑额外的计算开销,2与1也就不等价了。

另外一个场景:

Alice向Bob传送联通北京所有景点的哈密顿回路(货郎担问题)。Alice有3种选择:

1. 将哈密度回路直接发给Bob(可以压缩也可以不压缩,这里看做等效的)

2. 将北京景点图发给Bob,让Bob自己去找

3. 将北京景点图和计算哈密顿环路的程序发给Bob

1,2,3是否等效的问题这里就不讨论了,这里讨论其他两个问题。

首先第一个问题,景点地图所包括的信息是不是包含了该图的哈密顿环路的信息? 首先从信息论的观点出发,信息一旦损失,就不可再恢复。消息进行有损压缩后,如果不补充新的知识,无论用什么解压算法,都不可能还原。但是根据图,是一定可以找到哈密尔顿回路的(如果不考虑时间限制的话)。另一方面,直观上来讲,仅从一张图尔得到该图的哈密尔顿回路却是很困难的。

第二个问题,如果给了图和计算程序(情况3),是不是就可以讲图和程序共同包含了哈密尔顿环路的信息? 但是有可能Bob的假期都过了,他还没能得到他要的回路。

从上面的的问题可以看出,信息论无法统一度量信息传递过程中的所有开销。压缩方法以增加计算开销的方式来获得较小的传输开销。但是按照信息论,传输开销的减小程度是有限制的。但是根据方法3的情况,有可能通过增加计算开销来将传输开销降低到信息熵的限制以下。根据这些事实,是不是可以猜想,信息与计算是遵循一定规律转化的?更进一步,对于一个传输过程,信息与计算之和是不是守恒的?



http://blog.sciencenet.cn/blog-230547-224850.html


下一篇:Ubuntu安装显卡驱动

7 陈绥阳 胡俊峰 周春雷 黄富强 iwesun zhangcw wangyi6

发表评论 评论 (8 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-11-22 10:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部