多項式時間(Polynomial)アルゴリズムが知られていない問題を解くときに用いる。用いると言っても、『答えとして受け入れられる答え』が出ることが知られている必要がある。 『答えとして受け入れられる答え』の担保が示されていることが条件で、かつ、計算量…

時間計算量はステップ数、領域計算量は情報の保持量(メモリ負荷) 実際の実行にあたってはそれぞれの計算量により制約があり、アルゴリズムは、それらの負荷により分類される 計算量も『決定的(Deterministic)』か『非決定的(Non-deterministic)』かで２分さ…

書きかけ 計算可能性と実際に計算して答えを求める努力をすることとは同じではない。「いつかは終わるかもしれないけれど、あまりに時間がかかりすぎる方法」は、はなから始めない方がよい。この『かかる時間の予想』を数値化したもの。入力情報量によって計…

この記事は表現、非常に曖昧かつ、うそを含む可能性高し！ 計算可能性とは、 『数学的には』(数学者でない者が数学的説明を読んで、いきなり数学的な厳密性をはしょって説明するときの枕詞である)、次のように言えるのだろう・・・ 『アルゴリズムが、１つの…

Wikipediaではこう： 「アルゴリズム」の概念を定式化する為の数学モデルのこと。チューリングマシン、帰納的関数、λ計算などがある。

問題を解く手順であり、次の性質を満たすものと定義されている 有限個の演算・操作の列のこと ここの演算・操作の終了時に次の演算・操作が決まっている 有限回の演算・操作の後、必ず、手順は終了する 手順の終了時に問題の正当な答が得られている

臨時別冊・数理科学 SGCライブラリ43『アルゴリズムと計算量』 谷 聖一 サイエンス社