补充资料：计算理论

计算理论
theory of computation

　　1 ISuan lllun计算理论(theo灯of col旧putation)关于计算和计算机械的数学理论。 1936年，为了讨论对于每个问题是否都有求解的算法，数理逻辑学家提出了几种不同的计算模型的定义。K.G改」el和5.C.Kleene等人创立了递归函数论，将数论函数的算法可计算性刻画为递归可枚举性。A.M.Turing和E.L.l入粥t彼此独立地提出了理想计算机的概念，将问题的算法可解性刻画为在具有严格定义的理想计算机上的可解性。这一时期提出的通用图灵机在很大程度上影响了1946年出现的程序存储式计算机的设计思想。近代计算机的诞生使研究的焦点从理论可计算性转移到现实可计算性。因而，对一般算法设计方法的研究以及对一类问题的算法解的难度的分析与研究便成为计算机科学的热点。由此产生了算法学和计算复杂性理论等新兴的研究领域。自A.M厂1汕ring提出图灵机，E.L.Pe巧t提出波斯特机以后，直到1948年才由美籍匈牙利数学家J.VOnN~n提出建立自动机的一般数学理论，对各种人造自动机和天然自动机进行比较、分析，探索其共同规律。他还研究了自动机的自繁殖和自恢复问题。1954年前后形成了时序机的概念，1963年后概率自动机的理论有了新的发展。1960年后，细胞自动机在生物学和大规模集成电路技术的基础上有了重要的进展，成为自动机理论中的一个活跃领域。形式语言的研究始于20世纪初，把形式语言用于描述自然语言则是20世纪50年代中期的事。1956年，N.Cllonlsky发表了用形式语言方法研究自然语言的第一篇文章。在1960年发表的户J工X)L60报告中，首次使用与上下文无关文法等价的巴克斯范式系统来描述程序设计语言的局部语法，从而使形式语言理论在程序设计语言的设计与实现中发挥了重要的基础作用。 计算理论主要内容包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。 算法解题过程的精确描述。它由有限条可完全机械执行的、有确定结果的指令(或命令、语句)构成并具有以下性质:(l)将算法作用于特定的输人集或问题描述上将产生由有限个动作构成的动作序列;(2)该动作序列具有唯一的初始动作;(3)除末尾的动作外，序列中的每个动作都有一个或多个后继动作;(4)序列或者终止于问题的解，或者终止于指出对给定输人集原问题无解。最常用的算法有排序算法，求解组合问题和组合最优化问题的组合算法等，而动作具有随机性的概率算法可望比确定型算法更高效。随着并行处理机的出现，一类适应于并行操作的并行算法便应运而生，并且日益成为热门的研究领域。 算法学系统地研究算法的设计、分析与验证的学科。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。