《信息、算法与编码》求取 ⇩

第一部分信息、算法与编码在数理逻辑中3

0.1 数理逻辑简介3

第一章可计算性函数8

1.1 算法和能行过程的直观含义（非数学定义）8

1.2 计算机模型——无界存储机URM9

1.3 URM-可计算性函数11

1.4 可判定谓词及可判定问题13

第二章生成可计算性函数15

2.1 生成可计算性函数15

2.2 原始递归函数20

第三章丘奇论题25

3.1 图灵机25

3.2 丘奇论题定义及应用27

第四章哥德尔编码32

4.1 URM程序的编码32

4.2 可计算函数的编码33

4.3 s-m-n定理33

4.4 “好”的编码（一）35

4.5 范式定理38

第五章一些重要结果40

5.1 通用函数及通用计算机40

5.2 哥德尔不完全性定理（简单化）40

5.3 P与NP问题41

5.4 “好”的编码（二）45

5.5 加速定理（the speed-up theorem，Blum）46

第六章可判定问题、递归、规约及度48

6.1 可判定，不可判定48

6.2 部分可判定50

6.3 递归及递归可枚举集51

6.4 多一规约53

6.5 图灵（Turing）规约55

6.6 小结：复杂事物的编码56

第二部分信息、算法与编码在可计算分析中59

第七章可计算分析的背景、TTE的轮廓59

7.1 研究背景59

7.2 TTE体系的轮廓60

第八章康托（Cantor）空间上的可计算性63

8.1 T2-机器及可计算性63

8.2 可计算串函数是连续的67

8.3 连续串函数集的标准表示69

第九章 “好”的命名系统72

第十章 R上的可计算性78

第三部分算法信息89

第十一章实数函数的计算复杂性89

11.1 柯氏（Kolmogorov）复杂性93

11.2 前缀复杂性94

11.3 柯氏复杂性与香农熵96

11.4 算法熵是不可计算的98

第四部分信息论103

第十二章 信息论发展简史和现状103

第十三章信息论的基本概念106

13.1 导论106

13.2 离散熵的定义108

13.3 熵的特性110

13.4 联合熵、条件熵113

13.5 离散互信息114

13.6 多个随机变量下的互信息116

13.7 互信息的性质119

13.8 熵函数形式的唯一性120

13.9 连续随机变量下的熵与互信息123

13.10 鉴别信息123

第十四章信源的熵率、冗余度压缩128

14.1 信源模型与信源编码128

14.2 离散稳恒信源的熵率、冗余度129

14.3 渐进等同分割性与定长编码131

14.4 离散无记忆信源的变长编码134

14.5 变长编码的最优编码137

14.6 其他变长编码140

14.7 离散的马尔可夫信源的熵率149

第十五章信道容量及其有效利用155

15.1 信道模型与分类155

15.2 离散无记忆信道及信道容量155

15.3 离散无记忆信道容量的计算158

15.4 某些简单情况下信道容量的解160

15.5 可逆矩阵的信道容量165

15.6 级联信道和并联信道的信道容量167

15.7 输出字母概率分布唯一性170

15.8 信道容量的迭代算法170

第十六章信道编码175

16.1 信道编码概述175

16.2 信道译码准则176

16.3 联合典型序列和联合渐近等同分割定理178

16.4 信道编码定理，即香农第二定理179

第十七章线性分组码180

17.1 纠错码分类180

17.2 线性分组码概述180

17.3 生成矩阵、一致校验矩阵180

17.4 线性码的距离、重量和检错、纠错能力182

17.5 陪集、标准阵列和译码方法184

17.6 小结：“好”的分组码186

第十八章循环码189

18.1 循环码的定义及特性189

18.2 循环码的生成矩阵和一致校验矩阵193

第十九章卷积码196

19.1 多项式矩阵法196

19.2 标量矩阵法197

19.3 移位寄存器法198

19.4 状态、格图和Viterbi译码法200

第二十章汉明码、BCH码203

20.1 汉明码和完备码203

20.2 BCH码204

第二十一章有限域基本性质208

21.1 循环群208

21.2 环、理想、整环、同构等概念209

21.3 域的扩张213

21.4 代数扩域215

21.5 多项式模与分裂域218

21.6 有限域的结构220

21.7 多项式及多项式域（附录）230

第二十二章量子信息科学简介234

22.1 量子234

22.2 量子比特235

22.3 量子态叠加与量子态纠缠235

22.4 量子隐形传态237

22.5 量子通信238

22.6 冯·诺依曼熵239

22.7 最后的一点说明241

参考文献243