翻訳と辞書
Words near each other
・ 計算等価性原理
・ 計算簿
・ 計算者
・ 計算複雑性
・ 計算複雑性理論
・ 計算言語学
・ 計算誤差
・ 計算論的神経科学
・ 計算資源
・ 計算違い
計算量
・ 計算量理論
・ 計算量的安全性
・ 計算量的安全性を持つ暗号
・ 計算量的識別不能
・ 計算電磁気学
・ 計算高い
・ 計粒器
・ 計装
・ 計見一雄


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

計算量 : ミニ英和和英辞書
計算量[けいさん]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [けい]
  1. (n,n-suf) plan 
計算 : [けいさん]
  1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast 
: [りょう]
 1. amount 2. volume 3. portion (of food) 4. basal metabolic rate, quantity

計算量 ( リダイレクト:計算複雑性理論 ) : ウィキペディア日本語版
計算複雑性理論[けいさんふくざつせいりろん]
計算複雑性理論(けいさんふくざつせいりろん、)とは、計算機科学における計算理論の一分野であり、アルゴリズムスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論計算の複雑さの理論計算複雑度の理論ともいう。

== 概要 ==
計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか?」という問いに答える。これは、計算機の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、NPPといった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。
計算量 tC をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により tC以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 tC 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、暗号理論においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
現在の計算複雑性理論の最も重要な課題は、P≠NP予想の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要なオペレーションズリサーチの問題の多くが NPの部分クラスに属するNP完全問題であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解法が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。NPクラスがPクラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「計算複雑性理論」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Computational complexity theory 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.