计算模型
在计算机科学领域中,特别是在可计算性理论computability theory和计算复杂性理论computational complexity theory中,计算模型 model of computation描述了一个模型,其数学函数的输出是如何在给定输入的情况下计算出来的。模型描述了其计算单元、存储器和通信的组织方式。算法的计算复杂度可以通过给定的计算模型来度量。使用计算模型可以独立于特定实现和特定技术的变体来研究算法的性能。
模型的分类
计算模型可以分为三类: 顺序模型sequential models、功能模型 functional models 和并发模型concurrent models。
顺序模型Sequential models包括:
- Finite state machines 有限状态机
- Random access machines 随机存取机器
- Turing machines 图灵机
功能模型Functional models 包括:
- General recursive functions 一般递归函数
- Abstract rewriting systems 摘要重写系统
并发模型Concurrent models 包括:
模型的表达能力不同; 例如,有限状态机Finite State Machine可以计算的每个函数也可以由图灵机Turing machine计算,但反之行不通。
一个不确定的计算模型与其中的一些计算模型相关联。非确定性模型对实际计算没有用处,它们用于研究算法的计算复杂性。未解决的问题P/NP问题就是一个著名的例子。
使用
在算法的运行时分析领域中,通常指定一个计算模型为允许有单位成本或者简单的单位成本操作的基本操作。一个常用的例子是随机访问机器random access machine,它具有对其所有内存单元的读写访问的单位成本。在这方面,它不同于上述图灵机模型。
分类
基于不同的可容许运算集及其计算成本,计算模型它们分为以下几大类:
- 抽象机器Abstract machine和与之等价的模型(例如lambda微积分lambda calculus相当于图灵机Turing machine)-用于证明可计算性和算法计算复杂度的上界。
- 决策树模型Decision tree models-用于算法问题计算复杂度下界的证明。
相关页面
- Stack machine (0-operand machine)
- Accumulator machine (1-operand machine)
- Register machine (2,3,... operand machine)
参考阅读
- Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
- Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Addison-Wesley. ISBN 978-0201895391.
编者推荐
集智百科词条推荐
集智课程推荐
近年来,社会计算作为一个交叉学科,受到了各个领域学者的关注。为了相关领域学者更好地讨论和交流,推动交叉学科间的合作,促进社会计算的发展和研究,集智俱乐部组织了社会计算读书会,期待和大家一起分享论文、讨论和交流碰撞
基于ABM多智能体模拟,讲授计算社会科学核心技术与研究范式。我们的口号是“文科生也能学会计算机编程”,本门课程鲜明特征是:软的研究、硬的技术,将在此实现融合。通过课程学习,掌握计算社会科学核心技能,轻松玩转社会系统仿真模拟。本课程核心方法,将应用于计算社会学、计算政治学、计算法学、计算经济学、计算传播学、计算心理学、计算历史学等具体领域研究。
本中文词条由AvecSally审校编辑,如有问题,欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。