アルゴリズム(3章)

  • バイオインフォマティクス

    バイオインフォマティクス

    チューリングマシン:アルゴリズム用に定式化された数学的なモデル。以下の4つから成り立つ。(ⅰ) 入力データと出力データを含む二重の無限に長い記号のテープ。(ⅱ)読み/書きするヘッド。(ⅲ)可能な状態の一覧。(ⅳ)データを与えられたとき、実際にアルゴリズムのステップを指定するプログラム。チューリングマシンはアルゴリズムを開発するための実用的なツールではない。数学的定理の証明、問題の算法的複雑さの評価、異なるアルゴリズム間の比較などに役に立つ。
  • アルゴリズムは一般的に様々なデータセットに適用でき、実行時間は入力データの長さ(大きさ)に依存する。アルゴリズムの実行時間と入力データ長とを関連付ける規則はアルゴリズムの複雑さ、またはアルゴリズムの計算時間と呼ばれる。
  • 実行中にアルゴリズムは中間データを算出する。中間データはコンピュータのメモリに格納されなければならない。アルゴリズムが必要とするメモリ格納容量(占有量)は、アルゴリズムの効率を特徴付ける第2のパラメータ。中間データの量もまた入力データの大きさに関連づけられ、メモリ占有効率はこれらの2つの量の関係によって記述される。
  • 単純ソートとクイックソート:逐次並び替え K(K-1)/2回の比較が必要。O(K^2)。一方、クイックソートでは、X→[X1 xs X2]→[X11 x1 X12 x2 X21 x2 X22]→…のようにスプリッターxの大小で分割を繰り返す。分割にはKのオーダー、分割の回数はlog2Kのオーダーなので、速さはO(Klog2K)のオーダー。
  • 単純検索と高速検索: