《计算中的基本理论与方法》

目 录1

第一章预备知识1

§1-1字符串、字母表和语言1

§1-2图和树2

§1-3集合表示法和关系4

§1-4经典逻辑5

第二章有穷自动机与正规语言12

§2-1确定型有穷自动机12

§2-2非确定型有穷自动机16

§2-3正规表达式20

§2-4双向有穷自动机25

§2-5泵作用引理27

§2-6正规集合的性质28

第三章图灵机31

§3-1可计算性与可计算函数31

§3-2图灵机的定义和例子34

§3-3专用图灵机37

§3-4通用图灵机45

§3-5图灵可计算性49

第四章部分递归函数及其与图灵机的等价性61

§4-1三类递归函数61

§4-2原始递归谓词与递归谓词68

§4-3哥德尔编码72

§4-4图灵机与部分递归函数的等价性74

§4-5递归语言与递归可枚举语言78

§5-1计算复杂度及图灵机的资源82

第五章计算复杂性82

§5-2巡迥、空间与时间复杂度之间的关系90

§5-3计算模型间的相似性93

§5-4理论复杂性量度与加速定理96

第六章程序正确性证明101

§6-1预备知识101

§6-2部分正确性证明104

§6-3终止性证明114

§6-4完全正确性证明117

§6-5递归程序的正确性120

第七章 定理的机器证明123

§7-1海尔勃朗特定理124

§7-2归结原理127

§7-3归结原理的改进132

§7-4 自然推导法139

§7-5重写规则法142

§7-6 B-M定理证明系统145

§7-7几何定理机器证明151

第八章非标准逻辑156

§8-1 引言156

§8-2算法逻辑157

§8-3二阶逻辑170

§8-4模态逻辑175

§8-5时态逻辑181

§8-6动态逻辑189

§8-7 3-值逻辑、无穷值逻辑和模糊逻辑195

§8-8直觉主义逻辑203

§8-9非单调逻辑209

§8-10开放逻辑214

第九章推理方法219

§9-1推理方法的分类、演绎推理和归纳推理219

§9-2概率推理221

§9-3不确定性推理227

§9-4非单调推理235

§9-5模糊推理237

§9-6其它推理方法241

第十章按自然法则计算——研究非图灵模型的途径之一250

§10-1遗传算法253

§10-2模拟退火算法258

§10-3人工神经网络263

§10-4混沌273

§10-5分形277

主要参考文献281