  |
まず定義から始めます。アルゴリズムとは、定義された入力集合から出発し、定義された出力集合に到達する写像 (関数)である。
形式的には： f: X → Y
ここで、
アルゴリズムの「良し悪し」は何か？数学的には次の 3 本柱です。
1. 正確性 (Correctness)定義域内のすべての入力 x ∈ X に対して、仕様通りの出力f(x) を保証する。命題論理的には：「∀x ∈ X,f(x) ∈Spec(Y)」
2.計算量 (Complexity)時間計算量：入力サイズを n として、処理に要するステップ数を T(n) とする。空間計算量：必要なメモリ量を S(n) とする。漸近表記で記述：O(T(n)), O(S(n))
3. 停止性 (Termination)任意の入力に対して有限時間で処理が終了すること。数学的には停止性問題（チューリング停止性問題）に該当。
最後に、任意のアルゴリズム設計における究極の目標：入力集合 X に対して定義される最小限の T(n), S(n) を達成しつつ、正確性と停止性を保証する f を構築すること。
Find f: X → Y
Such that:
∀x ∈ X, f halts // 停止性
はい、先生、「良し悪し」が良くわかりません！ 良いとされるアルゴリズムだと何かうれしいことがあるのでしょうか？ 例えば正確性に関して、内部状態は持たない前提でしょうか？関...
はい先生！最適化が微妙に納得いきません！ CPUには投機的実行を行うものがあります ステップの実行能力に余力があるのであれば、並行的にまとめて処理してしまって、有用な結果だけ...
8