柯氏复杂性

维基百科，自由的百科全书

在计算机科学中，一个对象比如一段文字的柯氏复杂性 (柯尔莫哥洛夫复杂性, 描述复杂性, Kolmogorov-Chaitin complexity, stochastic complexity, 算法熵) 是衡量描述这个对象所需要的信息量的一个尺度。以下面的两个长度为64的字符串为例。

0101010101010101010101010101010101010101010101010101010101010101

1100100001100001110111101110110011111010010000100101011110010110

第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。

一个字符串 $s$ 的柯氏复杂性( $C (s)$ 或者 $K (s)$ ，区别如后)是这个字符串的最短描述的长度。换言之，一个字符串 $s$ 的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机/图灵机程序的长度。这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样。所以在讨论柯氏复杂性的时候，通常都事先固定一个通用图灵机 $U$ 作为参照。可以证明在使用 $U$ 做参照的时候，对任意的图灵机 $M$ ,都存在一个仅决定于 $U$ 和 $M$ 的常数 $c M$ 使得对所有的字符串 $s$ 相对于 $U$ 的柯氏复杂性 $C U$ (或者 $K U$ )和相对于 $M$ 的柯氏复杂性 $C M$ (或者 $K M$ )都满足

$C_U(s)\leq C_M(s)+c_M$ 。

根据这点，通常确定了一个参照图灵机后就用 $C$ 和 $K$ 表示柯氏复杂性（省略 $U$ ）。

[编辑] 参考资料

李明，[荷]P.M.B.威塔涅(Paul Vitanyi)，描述复杂性，科学出版社，北京，1998
Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997

zh-hans:;zh-hant:zh-hans:查;zh-hant:檢 • zh-hans:;zh-hant:論 • zh-hans:;zh-hant:編 • zh-hans:;zh-hant:歷

数据压缩方法

无损数据压缩

理论	熵 · 复杂性 · 信息冗余
熵編碼法	哈夫曼树 · 算术编码（Shannon-Fano · 区间） · Golomb · Exp-Golomb · 统一编码（Elias · Fibonacci） · Asymmetric binary
字典编码	RLE · LZ77/78 · LZSS · LZW · LZWL · LZO · DEFLATE · LZMA · LZX · LZJB
其他	CTW · BWT · PPM · DMC

音频压缩

理论	卷积 · 采样 · 采样定理
音频编解码器	LPC · WLPC · CELP · ACELP · A-law · μ-law · MDCT · 傅里叶变换 · 音响心理学
其他	动态范围压缩 · 语音编码 · 子带编码

图像压缩

条件	色彩空間 · 像素 · 色度抽样 · Compression artifact
方法	RLE · 分形压缩 · 小波压缩 · SPIHT · DCT · KLT
其他	比特率 · 标准测试图像 · 峰值信噪比

视频压缩

条件	視訊特性 · Frame · 視訊類型 · 視訊質量
视频编解码器	运动补偿 · DCT · 量化
其他	率失真理论（CBR · ABR · VBR）

分类: 計算理論 | 算法信息论 | 递归论 | 信息论

See also ebooksgratis.com: no banners, no cookies, totally FREE.

柯氏复杂性

维基百科，自由的百科全书

[编辑] 参考资料

Views

导航

帮助

搜索

其他语言