计算模型


在计算机科学领域中,特别是在可计算性理论computability theory和计算复杂性理论computational complexity theory中,计算模型 model of computation描述了一个模型,其数学函数的输出是如何在给定输入的情况下计算出来的。模型描述了其计算单元、存储器和通信的组织方式。算法的计算复杂度可以通过给定的计算模型来度量。使用计算模型可以独立于特定实现和特定技术的变体来研究算法的性能。


模型的分类

计算模型可以分为三类: 顺序模型sequential models、功能模型 functional models 和并发模型concurrent models。



顺序模型Sequential models包括:


功能模型Functional models 包括:


并发模型Concurrent models 包括:

模型的表达能力不同; 例如,有限状态机Finite State Machine可以计算的每个函数也可以由图灵机Turing machine计算,但反之行不通。

一个不确定的计算模型与其中的一些计算模型相关联。非确定性模型对实际计算没有用处,它们用于研究算法的计算复杂性。未解决的问题P/NP问题就是一个著名的例子。



使用

在算法的运行时分析领域中,通常指定一个计算模型为允许有单位成本或者简单的单位成本操作的基本操作。一个常用的例子是随机访问机器random access machine,它具有对其所有内存单元的读写访问的单位成本。在这方面,它不同于上述图灵机模型。


分类

基于不同的可容许运算集及其计算成本,计算模型它们分为以下几大类:

相关页面

参考阅读

编者推荐

集智百科词条推荐


集智课程推荐

社会计算读书会

近年来,社会计算作为一个交叉学科,受到了各个领域学者的关注。为了相关领域学者更好地讨论和交流,推动交叉学科间的合作,促进社会计算的发展和研究,集智俱乐部组织了社会计算读书会,期待和大家一起分享论文、讨论和交流碰撞


吕鹏:计算社会科学

基于ABM多智能体模拟,讲授计算社会科学核心技术与研究范式。我们的口号是“文科生也能学会计算机编程”,本门课程鲜明特征是:软的研究、硬的技术,将在此实现融合。通过课程学习,掌握计算社会科学核心技能,轻松玩转社会系统仿真模拟。本课程核心方法,将应用于计算社会学、计算政治学、计算法学、计算经济学、计算传播学、计算心理学、计算历史学等具体领域研究。


本中文词条由AvecSally审校编辑,如有问题,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。