計算模型 (數學)

可計算性理論計算複雜性理論中,計算模型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

拓展閱讀

編輯