計算資源

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

計算の複雑さの理論では計算リソースは、計算問題の解決においていくつかの計算モデルによって使用されるリソースです

最も単純な計算リソースは、計算時間、問題を解決するために必要なステップ数、およびメモリスペース、問題を解決するために必要なストレージの量ですが、より多くの複雑なリソースが定義されています。[要出典]

計算問題は、一般に、有効な入力に対するアクションの観点から定義されます[要出典] 。問題の例としては、「整数nを指定して、 nが素数であるかどうかを判断する」、または「2つの数値xyを指定して、積x * yを計算する」などがあります。入力が大きくなると、問題を解決するために必要な計算リソースの量が増加します。したがって、問題を解決するために必要なリソースは、入力の長さまたはサイズの関数としてリソースを識別することにより、漸近解析の観点から説明されます。リソース使用量は、BigO表記を使用して部分的に定量化されることがよくあります

計算リソースは、各計算リソースの特定の量でどの問題を計算できるかを調べることができるため、便利です。このようにして、問題を解決するためのアルゴリズムが最適であるかどうかを判断し、アルゴリズムの効率についてステートメントを作成できます。特定の計算リソースを一定量使用して解決できるすべての計算問題のセットは複雑度クラスであり、異なる複雑度クラス間の関係は複雑度理論で最も重要なトピックの1つです。

一般的にアクセス可能なコンピューティング機器の説明

「計算リソース」という用語は、アクセス可能なコンピューティング機器およびソフトウェアを説明するために一般的に使用されます。ユーティリティコンピューティングを参照してください

コンピューティング能力の正式な定量化

コンピューティング機能を正式に定量化するための努力がなされてきました。有界チューリングマシンは、特定の問題を解決するために必要な計算量を定量化するために、状態遷移の数とアルファベットサイズを使用して特定の計算をモデル化するために使用されています。[1] [2]

参照

  1. ^ Gregory J.、Chaitin(1966)。「有限バイナリシーケンスを計算するためのプログラムの長さについて」 (PDF)ACMのジャーナル13(4):547–569。土井10.1145/321356.321363S2CID207698337 _ 2007-02-05にオリジナル (PDF)からアーカイブされました2007年9月25日取得
  2. ^ 雌豚、デイビー; エレフテリアディス、アレクサンドロス(1998)。「計算資源の限界による情報の表現」(PDF)信号、システム、コンピューター。に関する第32回アシロマー会議の会議記録1. pp。452–456。ISBN  0-7803-5148-710.1109/ACSSC.1998.750904 2007年9月25日取得