翻訳と辞書 Words near each other ・ ブラマヨ衝撃ファイル ・ ブラマヨ衝撃ファイル 世界のコワ〜イ女たち ・ ブラマリのいただきっ! ・ ブラマンク ・ ブラマンジェ ・ ブラマンジェ曲線 ・ ブラマンテ ・ ブラマーナンダ ・ ブラミリ ・ ブラムの公理 ・ ブラムの加速定理 ・ ブラムウェル・フレッチャー ・ ブラム・コーエン ・ ブラム・ストーカー ・ ブラム・ストーカー賞 ・ ブラム・タンキンク ・ ブラム・チャイコフスキー ・ ブラム学園! ・ ブラム数 ・ ブラモス Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ブラムの加速定理 ： ウィキペディア日本語版 ブラムの加速定理[ぶらむのかそくていり] ブラムの加速定理（ぶらむのかそくていり、）は計算複雑性理論における計算可能関数の複雑性に関する基本定理であり、1967年にマヌエル・ブラムによって示された。 計算可能関数は無限個の相異なるプログラム表現を持つ。アルゴリズムの理論はそのようなプログラムから与えられた複雑性測度に対して最小となるプログラム（最適なプログラム）を探る。ブラムの加速定理は、いかなる複雑性測度に対しても最適なプログラムの存在しないような関数が複雑性測度に応じて存在することを述べる。これはまた任意の関数に対して''その''計算複雑性を割り当てる方法、つまり任意の関数 ''f'' に対して ''f'' を表現する最適なプログラムの複雑性を割り当てる方法が存在しないことを示している。このことは特定の具体的な関数について最適なプログラムの複雑性を探すことができないということを意味しない。 == 加速定理 == 複雑性測度 $(\backslash varphi,\backslash Phi)$ と2変数全域再帰的関数 $f$ を所与とする。このとき全域再帰的関数 $g$ （これはブール値関数にできる）が存在して、$g$ の任意の指標 $i$ に対して、$g$ の指標 $j$ が存在して、ほとんど全ての $x$ に対して次が成り立つ： :$f(x,\; \backslash Phi\_j(x))\; \backslash leq\; \backslash Phi\_i(x)$ $f$ は加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム $i$ を与える毎にそれよりも必要なだけ高速なプログラム $j$ が得られる。例えば $f(x,\; y)\; =\; 2^y$ とすれば $j$ の複雑性は $O(\backslash log\; \backslash Phi\_i(x))$ である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ブラムの加速定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.