計算資源と計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 02:20 UTC 版)
「計算資源」の記事における「計算資源と計算複雑性理論」の解説
最も単純な計算資源は、計算時間とメモリ使用量である。計算時間は問題を解くのに要するステップ数で表され、メモリ使用量は問題を解くのに要する記憶領域の量で表される。これらよりも複雑な資源も定義されている。 計算問題は一般に、妥当な入力を与えられたときの動作によって定義される。例えば、「整数 n を与えられたとき、n が素数かどうかを判定せよ」という問題、「2つの数 x と y を与えられたとき、積 x*y を求めよ」という問題などがある。入力が大きくなれば、必要な計算資源の量も増える。従って、問題を解くのに要する計算資源の量は、入力の長さや大きさの関数として表される。 問題を解くのに要する計算資源の量を研究することは重要であり、それによって、ある問題を解くアルゴリズムが最適かどうかを判断できる。ある一定の量の計算資源を使って解ける問題の集合を複雑性クラスと呼び、異なる複雑性クラス間の関係が計算複雑性理論での重要な話題となっている。 計算能力の定量化についても、様々な努力がなされてきた。制限されたチューリングマシンを使って計算をモデル化し、状態遷移数やアルファベットの大きさで特定の問題を解くのに要する計算能力を表す 。
※この「計算資源と計算複雑性理論」の解説は、「計算資源」の解説の一部です。
「計算資源と計算複雑性理論」を含む「計算資源」の記事については、「計算資源」の概要を参照ください。
ウィキペディア小見出し辞書の「計算資源と計算複雑性理論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算資源と計算複雑性理論のページへのリンク
