信息、算法与编码电子书

书名页

版权页

序言｜Preface

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

§0.1　数理逻辑简介

第一章　可计算性函数

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

§1.2　计算机模型——无界存储机URM

§1.3　URM-可计算性函数

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

第二章　生成可计算性函数

§2.1　生成可计算性函数

§2.2　原始递归函数

第三章　丘奇论题

§3.1　图灵机

§3.2　丘奇论题定义及应用

第四章　哥德尔编码

§4.1　URM程序的编码

§4.2　可计算函数的编码

§4.3　s-m-n定理

§4.4　“好”的编码（一）

§4.5　范式定理

第五章　一些重要结果

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

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

§5.3　P与NP问题

§5.4　“好”的编码（二）

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

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

§6.1　可判定，不可判定

§6.2　部分可判定

§6.3　递归及递归可枚举集

§6.4　多一规约

§6.5　图灵（Turing）规约

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

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

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

§7.1　研究背景

§7.2　TTE体系的轮廓

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

§8.1　T2-机器及可计算性

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

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

第九章　“好”的命名系统

第十章　ℝ上的可计算性

第三部分　算法信息

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

§11.1　柯氏（Kolmogorov）复杂性

§11.2　前缀复杂性

§11.3　柯氏复杂性与香农熵

§11.4　算法熵是不可计算的

第四部分　信息论

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

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

§13.1　导论

§13.2　离散熵的定义

§13.3　熵的特性

§13.4　联合熵、条件熵

§13.5　离散互信息

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

§13.7　互信息的性质

§13.8　熵函数形式的唯一性

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

§13.10　鉴别信息

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

§14.1　信源模型与信源编码

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

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

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

§14.5　变长编码的最优编码

§14.6　其他变长编码

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

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

§15.1　信道模型与分类

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

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

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

§15.5　可逆矩阵的信道容量

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

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

§15.8　信道容量的迭代算法

第十六章　信道编码

§16.1　信道编码概述

§16.2　信道译码准则

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

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

第十七章　线性分组码

§17.1　纠错码分类

§17.2　线性分组码概述

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

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

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

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

第十八章　循环码

§18.1　循环码的定义及特性

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

第十九章　卷积码

§19.1　多项式矩阵法

§19.2　标量矩阵法

§19.3　移位寄存器法

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

第二十章　汉明码、BCH码

§20.1　汉明码和完备码

§20.2　BCH码

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

§21.1　循环群

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

§21.3　域的扩张

§21.4　代数扩域

§21.5　多项式模与分裂域

§21.6　有限域的结构

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

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

§22.1　量子

§22.2　量子比特

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

§22.4　量子隐形传态

§22.5　量子通信

§22.6　冯·诺依曼熵

§22.7　最后的一点说明

参考文献