Atitit 软件体系重要理论学科

Atitit 软件体系重要理论学科 v2 s67.docx

Atitit 软件重要理论学科

目录

1. 计算理论这门学问 2

1.1. 学科的产生 2

1.2. 在这些领域中，自动机理论和形式语言理论是50年代发展起来的 2

1.3. 四类自动机  图灵机  诺伊曼 pda下推自动机 有限状态自动机fsm 3

1.4. 计算机科学分为计算机理论和计算机应用。 计算机基础理论包含以下几部分： 4

1.4.1. ( 1) 程序理论( 程序逻辑、程序正确性验证、形式开发方法等) 4

1.4.2. ( 2) 计算理论( 算法设计与分析、复杂性理论、可计算性理论等) 4

1.4.3. ( 3) 语言理论( 形式语言理论、自动机理论、形式语义学、计算语言学等) 4

1.4.4. ( 4) 人工智能( 知识工程、机器学习、模式识别、机器人等) 4

1.4.5. ( 5) 逻辑基础( 数理逻辑、多值逻辑、模糊逻辑、模态逻辑、直觉主义逻辑、组合逻辑等) 4

1.4.6. ( 6) 数据理论( 演绎数据库、关系数据库、面向对象数据库等) 4

1.4.7. ( 7) 计算机数学( 符号计算、数学定理证明、计算几何等） 4

2. 理论用途 5

2.1. 理论计算机科学主要包括:①自动机论与形式语言理论②程序理论③形式语义学④算法分析和计算复杂性理论。 5

3. ①自动机论 5

4. 形式语言理论 5

5. ②程序理论 5

6. ③形式语义学 5

7. ④算法分析 5

8. 计算复杂性理论。 5

9. 目录 6

9.1. 集合及其运算 6

9.2. 图与树 6

9.3. Lambda 6

10. Fp函数式 6

_{11. 可计算性理论} 6

12. Other 6

12.1. 第3章 语言层次 16 7

13. 自动机理论与应用 7

13.1. 编译原理四种类型文法 8

13.2. 自动机理论automata theory 8

14. 语言学 8

14.1. 理论发展 8

15. ref 9

1. 计算理论这门学问

，顾名思义，就是把“计算”(computation)这个抽象的现象作为我们的研究对象，用数学工具来分析和刻画，并为此而建立的理论体系。

全书分为三部分：自动机；可计算性；复杂度。这刚好是计算的三个不同的方面：计算的模型；计算的界限；计算的代价。自动机理论抽象的描述了什么叫“问题”，什么叫“解”，计算的机制可以有什么样的形式。可计算性关注的是计算的“行不行”的一面。而复杂度关注的是“好不好”的一面、也即问题的“难”和“易”。

什么是计算机？什么可以被计算？什么样的问题是难的、什么样的问题是容易的？这些计算机科学最自然最根本的问题，是计算理论这门学问的主题，也是这本书的主题。

1.1. 学科的产生

在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的(后来证明是彼此等价的)算法定义，从而建立了算法理论(即可计算性理论)。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机(称为图灵机)中的一种通用机就是存储程序型的

1.2. 在这些领域中，自动机理论和形式语言理论是50年代发展起来的

。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机(简称RAM)以及多带图灵机等。

1.3. 四类自动机  图灵机  诺伊曼 pda下推自动机 有限状态自动机fsm

1.4. 计算机科学分为计算机理论和计算机应用。 计算机基础理论包含以下几部分：1.4.1. ( 1) 程序理论( 程序逻辑、程序正确性验证、形式开发方法等)1.4.2. ( 2) 计算理论( 算法设计与分析、复杂性理论、可计算性理论等)1.4.3. ( 3) 语言理论( 形式语言理论、自动机理论、形式语义学、计算语言学等)1.4.4. ( 4) 人工智能( 知识工程、机器学习、模式识别、机器人等)1.4.5. ( 5) 逻辑基础( 数理逻辑、多值逻辑、模糊逻辑、模态逻辑、直觉主义逻辑、组合逻辑等)1.4.6. ( 6) 数据理论( 演绎数据库、关系数据库、面向对象数据库等)1.4.7. ( 7) 计算机数学( 符号计算、数学定理证明、计算几何等）

( 8) 并行计算( 网络计算、分布式并行计算、大规模并行计算、演化算法等) [1] 

2. 理论用途

书中的三个部分，对于搞研究的人来说，前两个领域已经或走到头了或不再是主流研究趣味了，只有复杂度尚活跃，但也只是个理论方向之一；而对于那些有志于业界工作的学生，后两个部分几乎永远不会在工作中用到，而只有第一部分的自动机，可能会用到一点点正则表达式。

看来，从“有用”这个方向去为计算理论辩护，难免会遭遇尴尬和勉强。

2.1. 理论计算机科学主要包括:①自动机论与形式语言理论②程序理论③形式语义学④算法分析和计算复杂性理论。

3. ①自动机论4. 形式语言理论5. ②程序理论6. ③形式语义学7. ④算法分析8. 计算复杂性理论。

9. 目录9.1. 集合及其运算9.2. 图与树9.3. Lambda10. Fp函数式11. NLP12. _{可计算性理论}

 编辑

本词条由“科普中国”百科科学词条编写与应用工作项目 审核 。

可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。可计算理论的研究对象有三个 ： ( 1) 判定问题； ( 2) 可计算函数；( 3) 计算复杂性。 [1] 

可计算理论的计算模型主要包括: ( 1)Turing 机； ( 2) 递归函数 ； ( 3) λ演算 ；( 4) POST 系统；( 5) 正则算法。 第一个模型是程序设计语言 S，该程序语言定义了 1) 变量；2) 标号； 3)语句； 4) 指令；5) 程序； 6) 状态;；7) 快相； 8) 后继； 9)计算。 设f(x 1 , x 2 , …, x n )是一个部分函数， 如果存在程序 S 计算 f ，则称 f 是部分可计算函数。 从而, 一个函数是否是可计算的,只需

13. Other

形式语言与自动机的发展

有限状态自动机

第四章　正则语言

第五章　下推自动机

第六章　图灵机

有穷自动机

13.1. 第3章 语言层次 16

3.1 定义任务：语言识别 16

3.2 编码的力量 16

3.2.1 一切都是字符串 16

3.2.2 把问题变成决策问题 19

3.3 基于机器的语言类层次 20

3.3.1 正则语言 20

3.3.2 上下文无关语言 21

3.3.3 可确定和半确定语言 22

3.3.4 计算层次及其重要性 23

3.4 语言类的可跟踪性层次 24

第3部分 上下文无关语言与压栈自动机

第11章 上下文无关文法 143

第三章　第12章 压栈自动机 177pda

14. 自动机理论与应用

第1部分 简 介

第1章 为什么学习计算理论 3

第2章 语言与字符串 7

第3章 语言层次 16

第4章 计算 26

第2部分 有限状态机与正则语言

第5章 有限状态机 39

第6章 正则表达式 88

第7章 正则文法 108

第8章 正则与非正则语言 113

第9章 正则语言的算法与决策过程 130

第10章 小结与参考资料 138

第3部分 上下文无关语言与压栈自动机

第11章 上下文无关文法 143

第12章 压栈自动机 177

第13章 上下文无关与非上下文无关语言 197

第14章 上下文无关语言的算法与决策过程 222

第15章 上下文无关解析 228

第16章 小结与参考资料 255

第4部分 图灵机与不可确定性

第17章 图灵机 259

第18章 Church-Turing命题 293

第19章 停止问题的不可解决性 303

第20章 可确定与半确定语言 309

第21章 可确定性与不可确定性证明 318

第22章 不明显提图灵机问题的语言的可确定性 345

22.1 Diophantine方程与Hilbert第十问题 345

第23章 无限制文法 361

第24章 Chomsky层次及其他 371

第25章 可计算函数 391

第26章 小结与参考资料 410

第5部分 复 杂 度

第27章 复杂度分析简介 415

第28章 时间复杂度类 439

第29章 空间复杂度类 490

第30章 难题的实用解 508

第31章 小结与参考资料 523

14.1. 编译原理四种类型文法14.2. 自动机理论automata theory15. 语言学15.1. 理论发展

美国语言学家N.乔姆斯基等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系:①若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然;②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然;③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然;④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。

这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。这是语言学对于现代自然科学发生影响的一个明证。