計算モデル

コンピュータ科学、特に計算可能性理論と計算複雑性理論において、計算モデルとは、入力が与えられたときに数学関数の出力がどのように計算されるかを記述するモデルです。計算モデルは、計算、メモリ、通信の単位がどのように組織されるかを記述します。 ^{[ 1 ]}アルゴリズムの計算複雑性は、計算モデルに基づいて測定できます。モデルを使用することで、特定の実装や特定のテクノロジーに特有の変動とは独立して、アルゴリズムのパフォーマンスを研究することができます。

計算モデルは、逐次モデル、関数モデル、並行モデルの3つのカテゴリに分類できる。

アルゴリズムの実行時間解析の分野では、単位コストを持つプリミティブ演算、あるいは単に単位コスト演算という観点から計算モデルを指定するのが一般的です。よく用いられる例としてランダムアクセスマシンがあり、これはすべてのメモリセルへの読み書きアクセスに単位コストを持ちます。この点で、前述のチューリングマシンモデルとは異なります。

• Fernández, Maribel (2009).計算モデル：計算可能性理論入門. コンピュータサイエンス学部トピックス. Springer. ISBN 978-1-84882-433-1。
• サベージ、ジョン・E. (1998).計算モデル：コンピューティングの力を探る. アディソン・ウェスリー. ISBN 978-0201895391。