注意: このページは最後に更新されてから 1589 日が経過している記事です。 文章が腐敗している可能性があります。その点を考慮した上で確認ください。

読書記録/アルゴリズムイントロダクション

提供: kimoto's wiki

書籍

言葉の整理

  • instance
    • 問題の記述で課された制約を満たす入力列
  • correctness of an algorithm
    • すべてのインスタンスに対して常に出力が正しい時のこと
  • computational problem
    • 計算問題
  • solve
    • 解く
  • ループ不変式
    • 繰り返されるループ内で毎回変化しない式を定義することで、それが初期、繰り返しの最中、終了時において変わってないことが保証されれば、そのアルゴリズムは正当であるということが証明できる。というもの
      • 初期条件
      • ループ内条件
      • 終了条件

アルゴリズムの効率

  • 挿入ソート
    • 最悪の実行時間はΘ(n^2)
  • 選択ソート
    • 最良でも最悪でも実行時間はΘ(n^2) (※いずれにせよ最悪)

#1

  • p4-p11についてのまとめ
  • アルゴリズムの有益さについての例示
  • 挿入ソートとマージソートを比較すると、要素が少ない時は挿入ソートが良いけど増えてくるとマージソートが勝つ、と。

練習問題

  • 1.1-1
    • ソートが必要とされていたのは図書館、凸包はなんかの電子部品の生成、型取りで使えそう
  • 1.1-2
    • 空間(メモリ使用量、ディスク使用量など)
  • 1.1-3
    • stack、出したり入れたり出来る。けど最初に追加したやつを最初に取り出せない
  • 1.1-4
    • よくわからない
  • 1.1-5
    • そんなのねーよ
    • だいたいどの程度生産すれば、売り切れずに済むかとかそういうのは近似解でよいよね
    • 多少売り切れてもいい、みたいな
  • 1.2-1
    • ユーザーの作ったTODOリストを優先度順で並び替えする例
  • 1.2-2
    • n = 2以上43以下
  • 1.2-3
    • n = 15

#2

上の範囲なので割愛

#3

#4

  • 体調不良のためまだ記載できず
  • p22の最悪時と平均時の解析という項目から、p24のアルゴリズムの設計、直前まで。
  • たった2ページ分なので追いつけない感じでもない
  • 2.2-1
    • Θ(n^3)
  • 2.2-2
    • 選択ソート
      • ループ不変式は、挿入ソートの時と同じで良い
    • 最良時も最悪時もΘ(n^2)実行時間
    • 最初のn-1個でよいのは、このアルゴリズムだと最後の要素nはすでにソートされている状態になるから。
  • 2.2-3
    • まず探索すべき要素のなかで等確率でマッチする、というのは1/nで表せる
    • この場合、調べられる要素数の平均は、n/2で表せる
      • たとえば6個要素があるとすれば、3個要素を調べれば発見できる
    • 最悪の場合最終要素まで調べないといけないが、平均時の場合(n/2)でも、Θ記法で表すといずれもΘ(n)で変わらない。要はnという入力の要素数がどれだけ増えてもその効率がどのように変化するかというのがΘなので。
  • 2.2-4
    • キャッシュ使うようにする

#5

  • p24の 「2.3 アルゴリズムの設計」から、p31の練習問題直前までやった。
  • 逐次添加法
    • 挿入ソートのように、部分列A[1..j-1]をソートした後
      • これはいわゆる本文中の例でいうところの、ソート済みの左手に持ってるカード達のこと
  • 分割統治法
    • 4章で説明される分割統治法の長所
    • 処理効率が推定しやすい
    • 分割統治パラダイムは再帰で実装しやすい
  • 漸化式(ざんかしき、ぜんかしき)
  • 再帰方程式

#6

  • p31の練習問題の2.3-1から2.3-3までをやった
  • 2.3-1
    • マージソートの手続きをホワイトボードに書いた。
      • 二分割していって枝の末尾まで展開してからそれぞれの部分をソートしながら結合していく感じ。
  • 2.3-2
    • 番兵を使わないように書き直す
    • 番兵は∞だったが、これはありえない最大値を配列の最後に入れておくことにより、最大値比較して低い方をスタックに詰む、という処理の記載を楽にするためのものだった。
      • それを示すということが出来た。
  • 2.3-3
    • 漸化式と、それを帰納法で証明するための方法の習得のための問題
    • T(n) = n lg nという数学的特性があることを、これに漸化式の1行目と2行目を当てはめて計算し、数学的帰納法で証明するというもの
    • T(1)のときと、T(k)のときと、T(k+1)のときを証明すれば良い。