维基百科

计算模型 (数学)

关于以计算机模型模拟复杂系统，请见「计算模型」。

在可计算性理论和计算复杂性理论中，计算模型（model of computation）描述了如何根据一组输入值计算函数的输出[1]，包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法的计算复杂度，总结出算法的性能，而不受特定技术和实现方式的性能差异所误导。

模型

编辑

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

顺序模型

编辑

顺序模型包括

函数式模型

编辑

函数式模型包括

同步模型

编辑

同步模型包括

各模型的表现不盡相同；例如，有限状态机可以计算的函数，图灵机也可以计算，反之亦然。

使用

编辑

在算法分析领域，定义一个计算模型通常用具有单位成本的原始操作（也称单位成本操作）。一个常见例子是随机存取机器，任何存储单元的读写访问，都有着单位成本。在这方面，它与图灵机模型不同。

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

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

分类

编辑

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

参见

编辑

参考资料

编辑
  1. ^ 计算模型 (PDF). [2024-01-09]. （原始内容存档 (PDF)于2024-03-29）. 
  2. ^ Examples of the price of abstraction? （页面存档备份，存于互联网档案馆）, cstheory.stackexchange.com

拓展阅读

编辑
检索自“https://zh.wikipedia.org/w/index.php?title=计算模型_(数学)&oldid=82172176”