|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 加 ： [か] 【名詞】 1. addition 2. increase ・ 加速 ： [かそく] 【名詞・動詞】acceleration, accelerate ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
計算複雑性理論における加速定理（かそくていり、）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、より少ない資源しか使用しない算法）の存在を示す定理である。 == 例 == 例として回文（palindrome）を受理する1-テープチューリング機械を考える。次のアルゴリズムは の時間計算量を持つ。 # 入力の左端の記号を読み取り空白記号を書き込む。このとき読み取った記号を記憶しておく。 # 入力の右端までヘッドを動かして、記号を読み取る。このとき左側にあった記号と異なるなら拒否して停止する。さもなくば空白記号を書き込む。 # 空白で埋まったら受理する。さもなくば(1)に戻る。（左端に戻るのは非効率であるから、左右を入れ替えて同じことを繰り返してもよいが、計算量のオーダーは変わらない。） 同じ問題を で解く次のような2-テープチューリング機械が考えられる。 # 入力を作業用テープにコピーする。 # 入力用テープのヘッドを左端に、出力用テープのヘッドを右端に設定する。 # 入力用テープの記号と読み取り、作業用テープの記号を読み取る。このとき異なる記号を読み取ったならば拒否して停止する。さもなくば入力用テープのヘッドを右に進め、作業用テープのヘッドを左に進める。 # もし(3)において（同時に）空白を読み取ったならば受理して停止する。さもなくば(3)に戻る。 なおこの計算量は最適である。回文であるか否かは少なくともその文字列の長さ分はテープ上を走査しないと判定できない。チューリング機械が入力に対してその長さ未満の時間で受理（または拒否）したなら、その入力の末尾にいかなる文字列を付け加えても受理（または拒否）する。ところが、いかなる文字列も末尾に適当な文字列を付け加えることで回文にも非-回文にもできるので、したがってこのチューリング機械は回文を受理しない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「加速定理」の詳細全文を読む スポンサード リンク
|