计算机科学

首页 > 计算机科学

计算模型 (数学)

2018-08-30 09:59:51     所属分类:计算理论

在可计算性理论和计算复杂性理论中,计算模型model of computation)描述了如何根据一组输入值计算得出输出值,也包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量一个算法在时间和/或空间上的复杂度。通过计算模型的抽象化总结,我们可以分析出算法的性能,而避免在具体程序层面,被不同的技术和实现方式造成的性能差异所误导。

目录

  • 1 模型
  • 2 使用
  • 3 分类
  • 4 参见
  • 5 参考资料
  • 6 拓展阅读

模型

计算模型可以分为三大类:顺序模型,函数式模型,以及同步模型。

顺序模型:

  • 图灵机
  • 有限状态机

函数式模型:

  • 递归函数
  • Λ演算
  • 组合子逻辑
  • 细胞自动机
  • 抽象重写系统英语Abstract rewriting system

使用

在算法分析领域,研究者们通常用具有单位成本的原始操作(也称单位成本操作),定义一个计算模型。一个常见例子是随机存取机器,它读取和写入其任何存储单元的操作,都有着单位成本。在这方面,它与图灵机模型不同。

在模型驱动工程中,计算模型解释了整个系统的行为是如何由每个组件的行为所共同造成的。

一个经常被忽略的关键点是,一些已知计算复杂度下限的问题是由较为局限的运算集得出的,实践中可使用的运算集可能更加广泛而强大,因而一些算法的实际性能,可能比高度抽象的计算模型得出的结果要好。[1]

分类

计算模型有很多,它们在各自容许的运算集和计算成本方面不同。它们可以被分为几大类:抽象机器和与其等同的模型(例如Λ演算相当于图灵机),用于可计算性、算法计算复杂性上限的证明;还有决策树模型英语Decision tree model,用于证明算法问题计算复杂度的下限。

参见

  • 堆栈结构机器(零操作数机器)
  • 累加器(一操作数机器)
  • 寄存器机(二、三、…操作数机器)
  • 随机存取机器
  • 细胞探针模型英语Cell-probe model

参考资料

  1. ^ Examples of the price of abstraction?, cstheory.stackexchange.com

拓展阅读

  • Fernández, Maribel. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. 2009. ISBN 978-1-84882-433-1. 
  • Savage, John E. Models Of Computation: Exploring the Power of Computing. 1998 [2016-12-23]. (原始内容存档于2016-10-12). 

相关推荐