《描述复杂性》求取 ⇩

1预备知识1

1.1 引论1

1.2 数学预备知识4

1.2.1 预备知识和记号4

1.2.2 二进制串5

1.2.3 近似记号8

1.3 可计算性理论基础9

1.3.1 可枚举函数12

1.4 描述复杂性之源13

1.4.1 随机性14

1.4.2 预测与概率19

1.4.3 信息论和编码22

1.4.4 状态×符号复杂性32

1.5 历史回顾与参考文献32

2描述复杂性35

2.1 变性定理37

2.2 不可压缩性41

2.3 作为整数函数的C45

2.4 随机有限序列48

2.5 随机无限系列53

2.6 有限序列的统计性质59

2.6.1 0-1的统计60

2.6.2 块的统计62

2.6.3 连续相同符号的长度64

2.7 C的算法性质65

2.8 算法信息理论69

2.9 历史回顾与参考文献77

3前缀描述复杂性79

3.1 不变性定理81

3.2 不可压缩性83

3.3 作为整数函数的K85

3.4 随机有限序列85

3.5 随机无限序列87

3.6 历史回顾与参考文献92

4描述概率95

4.1 再论可枚举函数96

4.2 非经典的测度论97

4.3 离散样本空间99

4.3.1 通用可枚举准测度100

4.3.2 先验概率103

4.3.3 描述概率104

4.3.4 编码定理104

4.3.5 求和测试下的随机性107

4.4 连续样本空间110

4.4.1 通用可枚举准测度110

4.4.2 先验概率111

4.5 历史回顾与参考文献115

5.1 引言117

5归纳推理117

5.2 Bayes推理120

5.3 Solomonoff的归纳理论121

5.3.1 数学上的分析122

5.3.2 在归纳中的应用127

5.4 最短描述长度原则128

5.5 历史回顾与参考文献135

6不可压缩方法137

6.1 三个例子138

6.2 组合学141

6.3.1 堆排序145

6.3 算法的平均情况复杂性145

6.3.2 布尔矩阵乘法的平均复杂性148

6.3.3 m-平均情况复杂性149

6.4 形式语言152

6.4.1 形式语言理论152

6.4.2 在线CFL识别156

6.4.3 多读写指针自动机158

6.5 计算模型161

6.5.1 图灵机时间复杂性161

6.5.2 并行计算162

6.5.3 通信复杂性163

6.6 历史回顾与参考文献168

7题外便览171

7.1 资源有界的描述复杂性171

7.2 Kt复杂性和势能175

7.3 通用优化搜索177

7.4 逻辑深度179

7.5 物理学、生物学及其它184

7.6 历史回顾与参考文献188

参考文献191

符号索引206