CPU Algorithm周辺のメモ

数値表現

  • 固定小数点表示法
    • 小数点の位置を右端に固定する方法
  • 浮動小数表示法
    • 数値を仮数と指数の掛け算で表示する
      1. 丸め誤差
      1. 情報落ち
      1. 桁落ち
      • 有効数字で丸められた数値同士を引き算したときに有効数字が減り、これを正規化したとき、右端から0が並んでしまい、あたかも正確な数値のように見える現象
      1. 打ち切り誤差

待ち行列理論

  • 様々な混雑や滞留を表現するためのモデル
  • ケンドールの表記法
    • m/m/1, m/m/2 ... m/m/n などがある
    • nは処理を行う窓口の個数と考えることができる(同時に処理が可能な処理の個数)
  • 指標
    • 平均到着率
      • 単位時間あたりに特着するトランザクション数
    • 平均サービス率
      • 単位時間あたりに処理が可能なトランザクジョン数
    • 利用率
      • 平均到着率/平均サービス率
    • 平均待ち時間
      • 列に到着してから処理が完了するまでの時間
    • 平均サービス時間
      • 平均待ち時間 + 平均サービス時間
  • 特徴
    • 先着順に処理が行われる
    • 処理時間は指数分布に従う
    • 単位時間当たりに到着するトランザクション数はポアソン分布に従う
      • ポアソン分布
        • 平均値は一定という前提のもと、一定時間内にランダムな事象が何回発生するか
        • 具体例: 1分間におけるwebサーバーへのアクセス数 など

BFN記法

  • バッカス記法とも呼ばれる
  • プログラムの構文を形式的に記述する方法の1つ

コンパイラ理論

  • 字句解析
  • 構文解析
  • 意味解析
  • 最適化

有限オートマトン

  • 論理の流れを表現するために使用されるモデル
    • 正規表現が表す正規言語を理解するためなどに利用される

リスト

  • 単方向リスト
    • 末尾のデータを削除する場合、末尾のデータから前のデータを辿ることができないので先頭ポインタから末尾データの直前のデータまで辿っていく必要がある
  • 双方向リスト
  • 循環リスト

データ構造

  • スタック
    • 最後に格納したデータを先に取り出す
    • 後入れ先出し (LIFO: Last-In-First-Out)
    • 再帰処理といった、一時的にデータを避難させたい場面などで活用される
  • キュー
    • 最初に格納したデータを最初に取り出す
    • 先入れ先出し (FIFO: First-In-Fast-Out)
    • リングバッファ
      • 終端と先端が論理的に連結されており、循環的に利用できるバッファ

2分木

※「にぶんき」ではなく「にぶんぎ」と読みます。

  • 深さ優先探索
    • 行きがけ順
    • 通りがけ順
    • 通りがけ順
  • 幅優先探索

2分探索木

  • どの節点Nから見ても、左部分木のデータ全てがNのデータよりも小さく、右部分木のデータが全てNより大きい二分木
  • 深さ優先探索で探索を行う

完全2分木

  • 葉の深さが全て同じで、葉以外の節点が2つの子をもつ木

平衡木

  • 根から葉までの深さがほぼ等しくなるような木
  • AVL tree
    • 任期の節点において、左右部分木の高さを差が1以下であるデータ構造
    • 木の高さに変更があったときに2分探索木に対して、回転を行う
  • B-tree
    • 外部記憶装置にデータを格納するために考えられたデータ構造

オーダ

  • アルゴリズムの計算量を大まかに評価するときに使用する概念
  • n個のデータを処理する時間が an^2+bn の場合、計算量のオーダーは n^2 とみなす(最も早く増加する項に着目して評価をする)

探索アルゴリズム

  • 線形探索法
    • 先頭から順番に目的データを探す方法
    • 比較回数は最小で1, 最大でn
    • 計算量はO(n)
  • 2分探索法
    • 中央値と目的データを比較して、1/2ずつ比較して探索する方法
    • 計算量はO(logN)
  • ハッシュ探索法
    • データのキー値によって、ハッシュの格納場所を直接参照する方法
    • 計算量はO(1)
    • 衝突が発生した時の回避方法の種類
      • オープンアドレス法
      • チェイン法