更新时间：2020-09-11 16:53:44
封面
版权信息
序言｜Preface
第一部分 信息、算法与编码在数理逻辑中
§0.1 数理逻辑简介
第一章 可计算性函数
§1.1 算法和能行过程的直观含义（非数学定义）
§1.2 计算机模型——无界存储机URM
习题1.2
§1.3 URM-可计算性函数
习题1.3
§1.4 可判定谓词及可判定问题
习题1.4
第二章 生成可计算性函数
§2.1 生成可计算性函数
习题2.1
§2.2 原始递归函数
习题2.2
第三章 丘奇论题
§3.1 图灵机
§3.2 丘奇论题定义及应用
习题3.2
第四章 哥德尔编码
§4.1 URM程序的编码
§4.2 可计算函数的编码
§4.3 s-m-n定理
习题4.3.1
习题4.3.2
§4.4 “好”的编码（一）
习题4.4
§4.5 范式定理
第五章 一些重要结果
§5.1 通用函数及通用计算机
§5.2 哥德尔不完全性定理（简单化）
§5.3 P与NP问题
§5.4 “好”的编码（二）
§5.5 加速定理（the speed-up theorem，Blum）
习题5.5
第六章 可判定问题、递归、规约及度
§6.1 可判定，不可判定
习题6.1
§6.2 部分可判定
习题6.2
§6.3 递归及递归可枚举集
习题6.3
§6.4 多一规约
§6.5 图灵（Turing）规约
§6.6 小结：复杂事物的编码
第二部分 信息、算法与编码在可计算分析中
第七章 可计算分析的背景、TTE的轮廓
§7.1 研究背景
§7.2 TTE体系的轮廓
第八章 康托（Cantor）空间上的可计算性
§8.1 2-机器及可计算性
§8.2 可计算串函数是连续的
§8.3 连续串函数集的标准表示
第九章 “好”的命名系统
第十章 ℝ上的可计算性
第三部分 算法信息
第十一章 实数函数的计算复杂性
总结
习题11.0
§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 鉴别信息
第13章习题
第十四章 信源的熵率、冗余度压缩
§14.1 信源模型与信源编码
§14.2 离散稳恒信源的熵率、冗余度
§14.3 渐进等同分割性与定长编码
§14.4 离散无记忆信源的变长编码
§14.5 变长编码的最优编码
§14.6 其他变长编码
§14.7 离散的马尔可夫信源的熵率
第14章习题
第十五章 信道容量及其有效利用
§15.1 信道模型与分类
§15.2 离散无记忆信道及信道容量
§15.3 离散无记忆信道容量的计算
§15.4 某些简单情况下信道容量的解
§15.5 可逆矩阵的信道容量
§15.6 级联信道和并联信道的信道容量
§15.7 输出字母概率分布唯一性
