今日のアルゴリズム:用語､基礎概念等

kindleより達人出版会から買うのがおすすめ。

tatsu-zine.com

とりあえず冒頭からp24まで読んだ。気になった用語などのメモ

アルゴリズム:ある値または値の集合を入力として取り、ある値または値の集合を出力として生成する明確に定義された計算手続き(p4)
問題のインスタンス:その問題の解を計算するのに必要な入力

この辺は組合せ最適化で読んだ決定問題の定義と似ている。組み合わせ最適化の方が厳密に書かれている気がするが。

yuyubu.hatenablog.com

ループ不変式
- 初期条件: ループの実行開始直前ではループ不変式は真である
- ループ内条件: ループの何回目かの繰返しの直前でループ不変式が真ならば,次の繰返しの
直前でも真である
- 終了条件: ループが停止したとき，アルゴリズムの正当性の証明に繋がる有力な性質が不変
  
  式から得られる
RAM(Random-Access Machine)
- 単一プロセッサの計算モデル
  - 命令は一つずつ逐次的に実行
  - 並列計算はなし
- 機能(実行時間は全て定数時間)
  - 算術演算(加算,減算,乗算,除算,剰余,切捨て,切上げ))
  - データ移動(ロード,ストア,コピー)
  - 制御(条件付分岐,無条件分岐,サブルーチンの呼び出しと, 復帰)
- データ型
  - 整数
  - 浮動小数点
- 実行時間=ステップ数
実行時間=最悪時間とするらしい
- 理由
  - それ以上時間がかからないことを保証できる
  - 最悪の場合が頻繁に生じる(検索アルゴリズムの結果見つからない時など)
増加のオーダー
- オーダーにはΘを使う
- an² + bn + cがコストのアルゴリズムの増加オーダーはΘ(n²)とする
  - 主要項から定数係数を外したものを使う
  - 定時の項はnが大きいとき相対的に重要度が低いから
分割統治:元の問題を部分問題に分割し、組み合わせて元の問題に対する解を構成する
- 分割:問題をいくつかのより小さい部分問題に分割する
- 統治:部分問題を解く
- 統合:解を組み合わせ元の問題の解を得る