アルゴリズムイントロダクション 第 3 版 総合版（日本語・Kindle 版）を読み切った。購入日が 2018 年 1 月 22 日で、読み終えたのが 11 月 21 日なので約 10 ヶ月かかったことになる。擬似コードを Python で実装した部分 もあれば、斜め読みでほぼスキップした部分もある。

以下、読みながら取っていたメモ。

2 さあ，始めよう

正当性の証明

多くのアルゴリズムはループを利用する。こうしたアルゴリズムの正当性の証明するは初期条件、ループ内条件、終了条件の 3 つを示す必要がある。数学的帰納法と似ている。 資源（時間や記憶量）を解析するのにランダムアクセスマシンを利用する。

実行時間の解析

• 最悪実行時間か平均実行時間か
• 増加のオーダーが大事
  • だが、定数因子も無いわけではないので、問題サイズが小さい場合は敢えてオーダーの大きいアルゴリズムを利用するほうが速いことがある
  • 漸近的な asymptotic 効率とも言う

基本的アプローチ

• 逐次添加法 incremental approach
• 分割統治法 devide and conquer
  • 問題を分割し、サイズの小さな部分問題を解いた後に、それらの解を組み合わせて解を導く方法
  • 分割、統治、結合

挿入ソート insertion sort

• 逐次添加法
• O(n^2)

マージソート merge sort

• 分割統治法
• 番兵 sentinel を使うことで、プログラムがある位置まで達成したことを判定するテクニックがある。
• O(n * lg(n))
• in place ではない

3 関数の増加

漸近記法

アルゴリズムの実行時間を記述するために用いる

• Θ 記法
  • ある正の定数 n0 が存在し、すべての n>=n0 に対して...関数の値域が上からも下からも制限できる関数の集合
• O 記法 ビッグオー
  • 漸近的上界
  • ある正の定数 n0 が存在し、すべての n>=n0 に対して...関数の地域が上から制限できる関数の集合
• Ω 記法 ビッグオメガ
  • 漸近的下界
  • ある正の定数 n0 が存在し、すべての n>=n0 に対して...関数の地域が下から制限できる関数の集合
• o 記法 リトルオー
  • タイトであるとは言えない上界
• ω 記法 リトルオメガ
  • タイトであるとは言えない下界

学術的にはこのような定義だが、上界・下界両方に対して O 記法でまとめられてしまうことも

4 分割統治

• 分割: 問題をいくつかの部分問題に分割する。部分問題は元の問題と同じ構造であり、元の問題より小さい。
• 統治: 部分問題を再帰的に解く。
• 結合: 部分問題の組み合わせて、元の問題の解を求める。

しばしば漸化式で実行時間 T(n) を表現する。 漸化式を解くのに、置換え法、再帰木法、マスター法が存在する。

• 組換え法 substitution method
  • 解の形を推定し、数学的帰納法で推定が正しいことを証明する。天下り的。
• 再帰木法 recursion tree method
  • 木の深さごとにコストを求めて、そのコストを総和することで求める。
• マスター法 master method
  • T(n) = aT(n/b) + f(n) (a>=1, b>=1, f(n) は漸近的に正) を解く方法

最大部分配列問題 maximum subarray problem

総当たり戦略で解くと Ω(n^2) であるが、分割統治法で Θ(n*lg(n)) で解ける

行列積

n x n 行列 A, B の積を求める。 素直な分割統治で解くと Θ(n^3) である。 Strassen の方法では Θ(n^lg(7)) で解ける。

5 確率的解析と乱択アルゴリズム

乱択アルゴリズムを用いることで、アルゴリズムの期待実行時間を求める。

II ソートと順序統計量

ソートアルゴリズムまとめ

6 ヒープソート heap sort

ヒープ heap

ヒープはヒープ条件を満たすツリー型データ構造

• min-heap のヒープ条件
  • 子要素のキー >= 親要素のキー
• max-heap のヒープ条件
  • 子要素のキー <= 親要素のキー

最下位レベルは左から順に埋まっている。 具体的な実装は配列で実現できる。

• 2 分木の場合、ヒープの高さは Θ(lg(n))
• ヒープ条件を維持する手続き max-heapify に O(lg(n))
• 未ソートの配列から max-heap を構築する手続き build-max-heap に O(n)
• ソートする手続き heapsort に O(n * lg(n))

優先度付きキュー priority queue

優先度（key）を持った集合 S を管理するための抽象データ構造で次の操作を持つもの

• insert: S に key 付き要素を挿入する
• (option) maximum: 最大の key を持つ S の要素を返す
• extract-max: 最大の key を持つ S の要素を削除し、その要素を返す
• (option) increse-key: S の要素の key を k に増加させる。

ハッシュテーブルを実装に使った場合、insert は O(1) だが、extract-max は O(n) ヒープを実装に使った場合、insert も extra-max も O(lg(n))

7 クイックソート quick sort

最悪実行時間は Θ(n^2)だが、期待実行時間は Θ(n * lg(n)) で、かつ隠れた定数部分が小さい。 in place でできる。

分割統治法である。

• 分割: 分割点 q を決め、q より左の配列はすべて q 以下で、q より右の配列はすべて q 以上となるように配列を並び替え、分割する。
• 統治: q の左右の配列をそれぞれ再帰的にソートする。
• 結合: 何もしなくて良い。ソート済みである。

分割点の決め方を乱択化することで確率的な解析が可能になる。

8 線形時間ソート

計数ソート counting sort

要素の範囲を限定した配列のソート 入力は n 個の要素（0~k の範囲の整数）からなる配列

長さ k+1 の配列 C を一時領域として持ち、C[i] の値が i 以下の要素数となるようにカウントしていく。

このソートは安定性 stability がある。 安定性とは、同じ値の要素は入力の順序そのままの順序で出力されるというもの。

基数ソート radix sort

d 桁の m 進数の数字をソートする。 1 番目の位（1 の位）で安定ソート、2 番目の位で安定ソート...d 番目の位で安定ソート、と d 回の安定ソートを行う。

パンチカードのためのソートで、現在では見かけることはない。

バケツソート bucket sort

バケットソート、bin sort とも。 入力が一様分布 [0,1) から抽出されると仮定する。

n 個のバケツ（例えばハッシュテーブル）を用意する。[0,1) を n 個の区間に分割する。入力配列のある要素が i 番目の区間に当てはまる場合は i 番目のバケツに挿入する。バケツは挿入された順序を保持する。

9 中央値と順序統計量

配列の中の i 番目順序統計量（例えば最小値、中央値、最大値など）を探すのにソートする必要はない。

最大値、最小値は n-1 回の比較で十分なことはすぐに分かる。実は、最大値と最小値を同時に探すのは 2n-2 回ではなく 3*(n/2)回の比較でよい。配列を 2 つずつピックアップし、それらを比較（1 回目）し 、小さい方を最小値と比較（2 回目）、大きい方を最大値と比較（3 回目）すればよいからだ。

一般化した i 番目順序統計量の場合もクイックソートに似た分割と探索を繰り返すことで見つけることができる。教科書では randomized select という関数名になっている。期待実行時間は Θ(n)。

実は最悪実行時間が O(n) であるアルゴリズムも存在する。quick select とも呼ばれる。

• 入力配列を 5 個の要素からなるグループに分割する。n が 5 で割り切れないときは 1~4 個の配列がひとつできる。O(n)
• 各グループの要素を insert sort でソートする。それぞれグループの中央値を選択する。O(n)
• こうして得られた約 n/5 個の中央値の中から再帰的に中央値を見つける。T(n/5)
• randomized select の分割パートのアルゴリズムを改良し、中央値をピボットとして利用する。O(n)
• 再帰的に i 番目に小さい要素を見つける。T(7 * n / 10 + 6)

再帰する際の問題インスタンスサイズの大きさが 7 * n / 10 + 6 になるのがポイント。

次のような漸化式を得る。

• T(n) <= T(n/5) + T(7n/10+6) + O(n) (n >= 140)
• T(n) <= O(1) (n < 140)

証明は組み換え法でできる。

10 基本データ構造

スタック stack

配列に加え top 位置を保持することで、push も pop も O(1) で実現できる。

キュー queue

長さ n の配列と head と tail を保持することで enqueue と dequeue を O(1) で実現できる。

連結リスト linked list

双方向の連結リストは head と tail、各要素は next と prev を持つ。 番兵 sentinel を用いると手続きをコードを単純化できる。

2 分木 binary tree

分岐数に制約のない根付き木

左-子・右-兄弟表現を用いると良い。あるノードは子供のうち最も左の子のポインタ格納スペースと、弟のポインタの格納スペースを保持する。

11 ハッシュ表

ハッシュ表 hash table

キーのハッシュ値の枠に要素を保持する。ハッシュ関数を普遍集合 U から {0,1,...,m-1} への関数とする。衝突した場合はチェイン法 chaining によって 、unserted double linked list に保存する。

• insert
  • 最悪実行時間 O(1)
• delete
  • 最悪実行時間 O(1)
• search
  • 最悪実行時間 O(n)
  • 平均実行時間 Θ(1 + n/m)

m が n に比例するなら平均実行時間は O(1) である。

ハッシュ関数を設計する。優れたハッシュ関数は出力がおよそ均等に分布する。

除算法 division method

キーが自然数なら枠数 m で割った余り mod をキーにする方法が考えられる。 2 のべき乗に近くない素数を m に選択するとよい。

乗算法 multiplication method

キー k に定数 A(0 < A < 1) を掛け、この k*A の小数部分に m を掛けた値の小数部分を切り捨てる h(k) = {m * (k * A mod 1)} の整数部分 m の値に制限はないが、計算が速い 2 の冪乗を選択すると良い。 A は (√5-1)/2 に近いと良い（らしい）。 32bit 整数の場合、2654435769/2^32 が最も (√5-1)/2 に近い。

万能ハッシュ法 universal hashing

キーの普遍集合 U を {0,1,...m-1} へ移すハッシュ関数の有限集合 H 任意の異なるキーの組 k,l ∈ U に対して、h(k)=h(l) を満たすハッシュ関数 h ∈ H の個数がたかだか |H|/m のとき H は万能という。

万能ハッシュ法は万能ハッシュ関数の集合 H からランダムに選択する。

すべてのキーが 0~p-1 の範囲に入る大きな素数 p を選択 a ∈ {0, 1, ..., p-1} b ∈ {1, 2, ..., p-1}

h_ab(k) = ((a * k + b) mod p) mod m

このハッシュ関数全体からなる族は万能である。

オープンアドレス指定法 open addressing

チェイン法と異なり、各キーに対する枠には 1 要素しか入らない。

長さ m の配列を用意する。初期状態はすべて Nil である。

• insert

  • キーを置ける空の枠を求めて探査 probe する。
  • ハッシュ関数は引数にキーを用いる。置換である。
  • h(入力キー, i) が埋まっていたら、
  • h(入力キー, i + 1) が空いているか確認する。
  • このようにキーを巡る順序を探査列と呼ぶ。

• search

  • insert と同じように探査列を辿っていき、キーを見るけるか、Nil が返ってくるまで探索する。

• delete

  • 削除した枠に Nil ではなく、delete フラグを置く。

• 探査列の構築方法。どれも一様ハッシュではなく、近似。

• 線形探索法 linear probing

  • ハッシュ関数: (h'(k) + i) mod m
  • 実装は簡単だが、主クラスタ化という探査時間が悪化する問題を抱えている。
  • 探査列集合のサイズ: Θ(m)

• 2 次関数探査法 quadratic probing

  • ハッシュ関数: (h'(k) + c1 * i + c2 * i^2) mod m
  • 線形探査法よりはるかに良いが、副クラスタ化と呼ばれる問題を抱えている。
  • ハッシュ表を完全に利用するためには c1, c2, m を上手く選ぶ必要がある。
    • m が 2 のべき乗なら、c1=c2=1/2 がよい。
  • 探査列集合のサイズ: Θ(m)

• ダブルハッシュ法

  • ハッシュ関数: (h1'(k) + i * h2'(k)) mod m
  • h1'(k) と h2'(k) は m の倍数ではないようにする。
  • 探査列集合のサイズ: Θ(m^2)

12 2 分探索木

2 分探索木 binary search tree

左の子のキー <= 自身のキー <= 右の子のキー の条件を満たす 2 分木

木の高さを h とする。削除と挿入を用いて構築された 2 分木の高さの平均については何も知られていない。

• 中間順序木巡回 inorder tree walk
  • Θ(n) キーがソートされた列にできる
• search
  • O(h) 最大 h 回の比較をして子ノードへ進む
• minimum (maximum)
  • O(h) 左（右）のノードをたどる
• successor (predecessor)
  • O(h)右のノードがあれば、その中の minimum を、なければ 1 つ親のノードへ移り、...と進める
• insert
  • O(h) 挿入すべき位置へ最大 h 回の比較をして子ノードへ進む
• delete
  • O(h) 複雑。子・孫の有無によってパターン分けして考える

基数木 radix tree (trie)

 長さ m の文字列をキーにして考える。 文字列がビット列の場合は、深さ i の接点で下から i 桁目のビットが 0 なら左、1 なら右となる 2 分木。 辞書順でソートできる。

13 2 色木

2 色木 red black tree

赤黒木とも。 接点が赤 or 黒の色を持つ 2 分探索木。root から leaf までの長さが最短のものと最長のもので 2 倍以内に収まっている。平衡二分木のひとつ。以下の条件を満たす

• root は黒
• leaf は Nil であり、黒
• 赤の子供は黒
• ある node から leaf までに含まれる黒 node の数はすべて同じ

insert, delete 時は rotate 操作を行うことで、木が条件を満たせるように保つ。高さ h が 2 * lg(n + 1) 以下なので、2 分探索木の各種操作が O(lg(n)) で実現できる。操作の実装は割と複雑。

ALV 木 AVL tree

平衡二分木のひとつ。leaf までの高さの違いが高々 1 という制約がある。2 色木と同様に、insert, delete で高さの差が 2 以上になったら balance という操作によって平衡を保つ。

14 データ構造の補強

新しいデータ構造の開発

• 基礎となるデータ構造の選択
• 追加情報を定める
• 基本操作が維持できるか確認する。計算量オーダーはどうなるかを検討する
• 新しい操作を開発する

順序統計量木 order-statistic tree

順序統計量操作（集合の中で i 番目に小さい要素の選択など）を高速に行うために 2 色木を改良したもの。各 node に size 属性を持つ。これは各 node を root とする部分技の内部 node 数を格納する。これによって i 番目要素の選択が O(lg(n)) で実行できる。

区間木 interval tree

各 node が閉区間 [t1, t2] （ただし t1<=t2）を保持する 2 色木の改良版。ある node の下端点<=左の子の上端点、ある node の上端点<=右の子の下端点を満たす。また各 node はそれを root とする部分木の最大値を格納する。

15 動的計画法 dynamic programming

動的計画法の開発

• 最適解の構造を特徴づける
• 最適解の値を再帰的に定義する
• （多くの場合はボトムアップで）計算する
• 計算結果から 1 つの最適解を構成する

動的計画法を使うときに注意することは、部分構造最適性 optimal substructure が適用できること。また部分問題重複性 overlapping subproblems を持つこと。可能なら部分問題の総数が入力サイズの多項式であるとよい。

ロッド切出し問題 rod-cutting problem

長さ n の棒がある。これを切り出す。切り出した棒は長さ i によって価格 pi が決まっている。合計金額を最大化したい。

この問題は部分構造最適性がある。

長さnの最適解 = max(pi + 長さn-iの最適解)

トップダウンでメモ化もせずに再帰的に解くと計算量が 2^n のオーダーになってしまう。解決策を 2 つ検討する。

• 履歴管理によるトップダウン方式 top-down with memoization
  • トップダウン（n が大きい方からの計算）だが、ある i での最適解が求まった場合はそれを保存しておく（memoize）。再度同じ i の最適解が必要になったら保存した値を利用する。
• ボトムアップ方式 bottom-up method
  • ボトムアップ（n が小さい方からの計算）で進める。こちらも一度求めた最適解をメモに保存しておき、2 回目以降はメモの値を利用する。問題の部分構造性質によるが、ボトムアップのほうがオーバーヘッドが小さいことが多い。

問題の構造を理解するのに部分問題グラフを使うと良い。サイズ n の最適化問題がサイズ m とサイズ l に依存するといった依存関係の有向グラフである。ボトムアップ型の動的計画法では、この有向グラフをトポロジカルソートした順に説いていけば良い。

最適値を求めた後に、最適値を出力するための切り出した棒の長さの組み合わせも出力できる。

連鎖行列積問題 matrix-chain multiplication problem

行列の列 A1, A2, ... An の行列積を求める。行列積は結合的なので、どのペアから計算をしてもよい。

• e.g. 2 つは同じ
  • A1 (A2 A3)
  • (A1 A2) A3

ただし要素（スカラー）同士の乗算の回数は順番によって異なる。どのようなカッコ付をするとスカラー乗算を最小化できるか？というのが連鎖行列積問題。n 個の行列の括弧の付け方は Ω(4^n/n^1.5)なので総当たりではできない。

Ai, Ai+1, ..., Ak, ..., Aj という列の行列積の計算を考える。スカラー乗算の最小値を m[i, j] とする。Ai は pi-1 x pi 型の行列。

部分構造は次のようになり、部分構造最適性がある。

• 漸化式
  • m[i, j] = min(m[i, k] + m[k+1, j] + pi-1 * pk * pj) (i < j のとき)
  • m[i, j] = 0 (i = j のとき)

最悪実行時間は Ω(n^3) で、メモのために Θ(n^2) の保存領域が必要。

最長共通部分列問題 longest-common-subsequence problem

与えられた 2 つの列 X と列 Y の最長共通部分列 LCS を求める問題。共通部分列は順序さえ一致していれば、飛び飛びでよい。

• 次のような列 X, Y, Z を考える
  • Xm = [x1, x2, ..., xm]
  • Yn = [y1, y2, ..., yn]
  • Zk = [z1, z2, ..., zk] X と Y の任意の LCS
• 部分構造最適性
  • xm = yn なら Zk = Xm-1 と Yn-1 の LCS Zk-1 + 1
  • xm != yn かつ zk != xm なら Zk = Xm-1 と Yn の LCS
  • xm != yn かつ zk != yn なら Zk = Xm と Yn-1 の LCS
• 漸化式
  • c[i, j] = 0 (i = 0 or j = 0)
  • c[i, j] = c[i - 1, j - 1] + 1 (i > 0 and j > 0 and xi = yj)
  • c[i, j] = max(c[i, j - 1], c[i - 1, j]) (i > 0 and j > 0 and xi != yj)

最悪実行時間は O(n^3) である。

最適 2 分探索木 optimal binary search tree

言語 A から言語 B への翻訳用の辞書を考える。言語 A で単語はソートされている。2 分探索でもよいが、単語の頻度は異なる。頻度の高い単語を root に近づけることで合計探索回数の期待値を最適化できる。

各ソート済のキーの列 K = [k1, k2, ... kn] から 2 分探索木を構築する。各キー ki が起こる確率 pi が与えられている。また ki < di < ki-1 となるダミーキーの列を考える。これはどのキーにもマッチしない場合のことを想定している。

探索コストの期待値 = Σ(あるキーの確率 * キーの深さ)

この探索コストの期待値を最小化する木、最適 2 分探索木を構築したい。

w(i, j) = Σt=i~j(キーtの確率) + Σt=i~j(ダミーキーtの確率) と表すと

• 最適 2 分探索木の探索コストの期待値 e[i, j] の漸化式
  • e[i, j] = ダミーキーi-1 j = i - 1 のとき
  • e[i, j] = min(e[i, r - 1] + e[r + 1, j] + w(i, j)) j <= i のとき

最悪実行時間は Ω(n^3) となる。

その他の DP

• バイトニック順回路 bitonic tour
  • 章末問題 15-3
• 編集距離 edit distance
  • 章末問題 15-5
• Viterbi algorighm
  • 章末問題 15-7
• シームカービング
  • 章末問題 15-8
  • 画像を（グニャグニャでもよいが垂直または斜めにつながっている）幅 1px 分の縦線分だけ画像の横幅を省略する。pixel ごとの重要度があり、省略する際は重要度ができるだけ減らないようにしたい。

16 貪欲アルゴリズム greedy algorighms

• 貪欲アルゴリズムを利用するときに検討する
  • 部分構造最適性
  • 貪欲な選択によって、ただ 1 つの部分問題が残る
  • 貪欲な選択が安全であることを証明する

活動選択問題 activity-selection problem

n 個の活動の集合 S = {a1, a2, ..., an} があり、各活動 ai には開始時刻 si と終了時刻 fi がある。同時刻にできる活動は 1 つである。活動数を最大化する組み合わせを求める。集合 S を終了時刻が速い順でソートしておく。

貪欲な戦略では、選択できる活動の集合の中から最も終了時刻が速いものを選択していく。これだけで活動数最大になることは定理 16.1 で証明される。

区間グラフ彩色問題 interval graph coloring problem

問題 16.1-4 開始時刻と終了時刻をもった活動の集合がある。同時に利用する最大会議室数を最小化したい。これは活動を頂点、活動時刻が重なる活動同士を辺で結んだグラフで、隣接した頂点が同じ色にならないように彩色する最小の色数をもとめる問題と同じ。

0-1 ナップサック問題 0-1 knapsack problem

n 個の品物があり、各品物 i は vi の価値があり、wi の重さがある。ナップサックには最大積載量 W がある。どの品物の組み合わせが価値の和を最大化できるか。vi, wi, W は整数。ある品物 i を取る・取らないの 0-1 なので 0-1 ナップサック問題と呼ぶ。貪欲アルゴリズムでは最適解にたどり着けないことがある。総当たりの場合 O(2^n)。動的計画法を使うと O(n*W) で解ける。

有理ナップサック問題 fractional knapsack problem

ナップサック問題で各品物の積載量が連続値になったもの。単位重さ当たりの価値が最も高いものを限界まで積み、残りのスペースに次に単位重さあたりの価値が高いものを貪欲に積んでいけば最適化できる。単位重さあたりの価値でソートすれば、O(n * lg(n)) で解ける。問題 16.2-6 によれば O(n) 時間で解ける。

ハフマン符号 Huffman code

文字列データの圧縮手法。各文字を出現頻度によって与える表を用いてビット列に変換する。頻度が高い文字は短いビット列にすると効率的。どの符号語も別の符号語の接頭語にならない符号 "接頭語符号" を利用する。2 分木で表現できる。貪欲アルゴリズムによって構築できる。図 16.5 を読めば実行の流れが見える。

マトロイド matroid

16.4 章参照

その他貪欲アルゴリズム関連問題

• 釣り銭問題
  • 章末問題 16-1
• 最小平均完了時刻スケジューリング
  • 章末問題 16-2
• オフラインキャッシュ問題
  • 多数のデータのうち何をキャッシュに載せるか、キャッシュミスを最小化する問題。通常の計算機ではオンラインの問題になるが、オフラインを仮定すると、貪欲法のひとつ、最遠要求優先 furthest-in-future 戦略で解ける。

17 ならし解析 amortized analysis

ある操作 1 回のコストではなく、操作列の総コストを計算する。操作列の総コストは各操作の最悪時コストの和ではない。計算の仕方が何種類かある。

• 集計法 aggregate method
• 出納法 accounting method
• ポテンシャル法 potential method

この解析を学ぶのは B 木やフィボナッチヒープの性能・特徴をより深く理解するためである。

スタック操作

スタック S を操作する。push(S, x)とpop(S)は O(1) で実行できるので、長さ n の (push or pop) の操作列のコストは Θ(n) で実行できる。

multipop(S, k)を考える。スタック S から k 個 pop するが、スタック S 内の要素が k 個未満のときはすべて pop する。pop の回数に比例するので min(S, k) 回の操作が行われる。長さ n の(push, pop, or multipop) の操作列のコストを考える。このときスタックの長さの最大値は n なので multipop の最悪実行時間は O(n) である。muptipop が n 回連続で続くとき、操作列全体の最悪実行時間は O(n^2) である...。この計算量の計算は雑。ならし解析によって O(n) という結果に改良できる。

2 進カウンタによる係数

0 から計数を開始する k bit の 2 進カウンタを考える。カウンタを 1 進める increment 操作を考える。n 回連続して increment したときビットのフリップ回数の和を求める。1 回の increment 操作コストは Θ(k) である。n 回の increment なら O(n*k) である...。これも正確にはフリップ回数は 2n 回以内でありオーダーは O(n) である。

動的な表

サイズを予め決めたテーブルにコスト O(1) である insert と delete 操作を行う。サイズが不足すると新たに大きなサイズのテーブルを確保し、コピーしなければならない。この拡大、もしくは縮小のコストは大きい。拡大・縮小の戦略を間違えると、操作列の総コストは O(n^2) などになってしまう。

テーブルサイズを 2^n 倍だけ考えることにしよう。飽和したらテーブルサイズを 2 倍にし、占有率が 1/4 以下になったらサイズを 1/2 にする戦略では、n 個の insert, delete の操作列の総コストはならし解析で O(n) とわかる。

18 B 木

ディスクアクセス回数を小さくしたいというモチベーションがある。

B 木 B tree

内部 node x が n 個のキーをもつ場合、n+1 個の子 node を持つ。leaf 場合は子を持たない。キーの個数もその node が保持する。

各 node が持てるキー数に上限と下限を定め、最小次数 minimum dgree である t を用いて表す。root 以外の node は t - 1 ~ 2 * t - 1 個のキーを持つことができる。

最も単純な t=2 の場合 2-3-4 木と呼ぶ。木を低くしたいなら大きな t を利用する。

高さ h は logt((n+1)/2) 以下になる。

• search
  • ディスクアクセス数 O(logt(n))
  • CPU 時間 O(t * logt(n))
• create new B-tree
  • ディスクアクセス数 O(1)
  • CPU 時間 O(1)
• splic child
  • 子 node のキーが飽和した場合は、自身の node にキーを追加し、子 node を 2 つに分割する
  • ディスクアクセス数 O(1)
  • CPU 時間 Θ(t)
• insert
  • ディスクアクセス数 O(logt(n))
  • CPU 時間 Θ(t * logt(n))
• delete
  • ディスクアクセス数 O(logt(n))
  • CPU 時間 Θ(t * logt(n))

19 フィボナッチヒープ

マージ可能ヒープ

• 以下の 5 つの操作ができるヒープ
  • make_heap() 空のヒープの作成
  • insert(H, x) x をヒープ H に挿入。x のキーはすでに書き込まれている
  • minimum(H) ヒープ H に属する最小のキーを持つポインタを返す
  • extract-min(H) ヒープ H の最小のキーを抽出し、そのポインタを返す
  • union(H1, H2) 2 つのヒープ H1, H2 を合併し、それを返す。元のヒープは削除される

フィボナッチヒープ fibonacci heap

マージ可能ヒープのひとつ

• 上記の 5 つに加え、次の操作も可能
  • descrease_key(H, x, k) ヒープ H に属する x のキーを k に下げる
  • delete(H, x) ヒープ H から x を削除する

2 分ヒープの最悪実行時間と比べて、フィボナッチヒープのならし評価はよい性能を示す。特に union

• make_heap()
  • 2 分ヒープ Θ(1)
  • フィボナッチヒープ Θ(1)
• insert(H, x)
  • 2 分ヒープ Θ(lg(n))
  • フィボナッチヒープ Θ(1)
• minimum(H)
  • 2 分ヒープ Θ(1)
  • フィボナッチヒープ Θ(1)
• extract-min(H)
  • 2 分ヒープ Θ(lg(n))
  • フィボナッチヒープ Θ(lg(n))
• union(H1, H2)
  • 2 分ヒープ Θ(n)
  • フィボナッチヒープ Θ(1)
• descrease_key(H, x, k)
  • 2 分ヒープ Θ(lg(n))
  • フィボナッチヒープ Θ(1)
• delete(H, x)
  • 2 分ヒープ Θ(lg(n))
  • フィボナッチヒープ Θ(lg(n))

グラフ問題のアルゴリズムでは decrease key をよく用いるのでフィボナッチヒープは良さそうに見えるが、定数部分が大きく、プログラムも複雑なので現実的にはそこまで魅力的ではないらしい。

各 node は親へのポインタと任意の子へのポインタを持つ。子リストは巡回双方向連結リストで互いに連結している。すべての子のキーは親のキーよりも大きい。また node は子の数 degree と、ある接点の子になったあとに子を失ったかを表す mark を持つ。

node の次数の最大値を考える。自明ではないが、19.4 の証明によって D(n)<= logφ(n) であることがわかる。オーダー的には O(lg(n)) である。

20 van Emde Boas 木

van Emde Boas Tree

キーは 0 ~ n-1 の相異なる整数である。各種操作が O(lg(lg(n))) で実行できる。 n 個の要素を保持する木の root node は、クラスタと呼ばれる √n 個の子 node を持つ。各子 node は √n 個の要素を保持する部分木の root でもある。 さらに各 node は最大値、最小値、クラスタのサマリーも持つ。

21 互いに素な集合族のためのデータ構造

互いに素な集合の族を管理するデータ構造。各集合の代表元によって集合を識別する。次の操作を持つ。

• make-set(x)
  • x を唯一の要素として持つ集合を生成する。
• union(x, y)
  • x を含む集合と y を含む集合を合併する。
• find-set(x)
  • x を含む集合の代表元へのポインタを返す 。

n 回の make-set 含み、合計 m 回の make-set, union, find-set からなるの操作列を考える。当然 m>=n。かつ n-1 回 union を行うと集合が 1 つになるので union の回数も高々 n-1 回。

各集合を uni-directional linked-list で表す。linked-list の各要素は集合のメタデータオブジェクトへのポインタを持つ。linked-list の先頭 head を代表元とみなす。集合のメタデータは head と tail のポインタを持つ。

合計 m 回の make-set, union, find-set からなるの操作列における 1 操作あたりのならしコストは Θ(n) である。

union はメタデータオブジェクトへのポインタの更新が必要。合併するときは短いリストの方を更新したほうがコストが低い。そこで集合のメタデータオブジェクトに集合サイズをもたせる。

これによって合計 m 回の make-set, union, find-set からなるの操作列における 1 操作あたりのならしコストは Θ(m + n * lg(n)) である。

22 基本グラフアルゴリズム

• グラフの表現方法
  • 隣接リスト表現
    • スパースなとき（ |E| << |V|^2 ）はコンパクトに表現できる。
    • 有効グラフの場合、隣接リストの長さの合計は |E|
    • 無効グラフの場合、隣接リストの長さの合計は 2*|E|
  • 隣接行列表現
    • 密なとき（ |E| と |V|^2 が近い ）や、ある 2 頂点間に辺が存在するかをすばやく判定するのに有利。
    • 行列サイズは Θ(V^2) となる

幅優先探索 breadth-first search

グラフ G=(V,E) と始点 s が与えられたとき、s から探索可能な頂点を発見かつ s からの最小距離を計算し、幅優先木と呼ばれる木を構築する。s からあらゆる頂点への最短路がわかる。

隣接リスト表現を用いた探索アルゴリズムを考える。幅優先探索において頂点はその隣接頂点が探索済みなのかを知るために白、灰、黒のどれかに彩色されている。灰色頂点の集合を管理するためにキュー Q を利用する。

• 初期化
  • 始点 s 以外すべての頂点の色 color は白、s からの距離 d は ∞、親頂点 π は Nil である。
  • 始点 s の color は灰、d は 0、π は Nil である。
  • キュー Q は s のみ保持している。
• while Q が空ではない
  • u = dequeue(Q)
  • for v of u の隣接頂点:
    • もし v が白なら、v.color を灰色に、v.d を u.d+1 に、v.π を u にし、v を Q に挿れる
  • u.color を黒にする

各頂点はキューに高々 1 回だけ挿入され、削除される。キュー操作合計で O(V)。隣接リストの長さの和は Θ(V)なので BFS の総実行時間は O(V+E) である。

深さ優先探索 depth-first search

先行部分グラフは深さ優先森（複数の深さ優先木）である。各頂点に 2 種類のタイムスタンプを押す。そのひとつ d はその頂点 v を発見して灰に彩色したときであり、もうひとつの f は隣接リストすべてを調べ上げて黒に彩色するとき。|V|*2 回分タイムスタンプが押されることになる。

• 初期化
  • すべての頂点の色 color は白、親頂点 π は Nil である。
  • time を 0 にする
• for u of すべての頂点:
  • もし u.color が白なら dfs-visit(G,u) を実行。u.color が白以外なら何もしない
• function dfs-visit(G,u):
  • time += 1
  • u.d = time（タイムスタンプ 1 つ目：発見時刻）
  • u.color = 灰
  • for v of u の隣接頂点:
    • もし v.color が白なら v.π を u にして、dfs-visit(G,v) を実行。v.color が白以外なら何もしない
  • u.color = 黒
  • time += 1
  • u.f = time （タイムスタンプ 2 つ目：終了時刻）

各頂点は 1 回ずつしか visit されないので実行時間は Θ(E) となる。

開始時刻と終了時刻は括弧構造 parenthesis structure となる。

• 辺(u,v) を探索することで初めて v を発見したなら、辺(u,v) は木辺 tree edge である。
• ある頂点 u とその祖先 v を結ぶ辺(u,v) を後退辺 back dege という。
• ある頂点 u とその子孫 v を結ぶ辺(u,v) で木辺ではないものを前進辺 forward edge という。
• その他の辺を横断辺 cross edge という。

無向グラフの深さ優先探索森は木辺または後退辺で構成され、前進辺と横断辺は存在しない。

トポロジカルソート topological sort

依存関係を表すグラフ G で、どの順番でやればすべての依存関係を満たした順序に並べられるか。有向非巡回グラフ DAG の深さ優先探索を用いる。

• dfs(G) を行う
  • ある頂点の探索が終わるたびに linked-list の先頭に挿入する
• できあがった linked-list はトポロジカルソートされている

強連結成分 strongly connected components

有向グラフを強連結成分に分解するのに 2 回深さ優先探索を行う方法がある。

• dfs(G) を行う
• G の転置グラフ G^T を計算する
• dfs(G^T) を行うが、終了時刻の降順で探索する
• 深さ優先森の頂点をそれぞれ分離された強連結成分として出力する

23 最小全域木

グラフ G の全域木 spanning tree （すべての頂点を結ぶ辺の集合）で、重みの和が最小のものを求める。貪欲戦略を用いた 2 つが紹介されている。

• Kruskal のアルゴリズム
• Prim のアルゴリズム

辺を 1 つずつ辺集合 A に加えていく。A は常に最小全域木の部分集合である。

無向グラフ G=(V,E) のカット(S,V-S) は、V の分割である。ある辺が S と V-S 2 つの集合をまたぐとき、その辺はカット(S,V-S) と交差するという。辺集合 A のどのへんもカットと交差しないとき、そのカットは A を尊重するという。カットと交差する辺の中で最も重みの低い辺を軽い辺 light edge という。

G の最小全域木の部分集合 A、A を尊重する G のカット(S,V-S)、カット(S,V-S) と交差する軽い辺(u,v) を考える。このとき辺(u,v) は A に対して安全であるという定理 23.1 を利用する。

Kruskal's Algorithm

成長させる森に加える安全な辺は、森に属する 2 つの木 C1, C2 を連結する辺の中で、重みが最小の辺を用いる。

• 初期化
  • 最小全域木の部分集合 A = ∅
  • 互いに素な集合族のためのデータ構造を用意する
    • グラフ G の頂点ひとつひとつが 1 つの集合を形成する
  • G.E を重み順にソートする
• for 辺(u,v) of G.E（重みの非減少順で）:
  • u と v が異なる集合に属するなら
    • 辺(u,v) を A に加える
    • u の集合と v の集合を合併する
• A は最小全域木となっている

Prim's Algorighm

• 初期化
  • すべての頂点の key = ∞
  • すべての頂点の π = Nil
  • ある頂点を r と呼ぶ r.key = 0
  • min 優先度付きキュー Q = G.V
• while Q が空ではない:
  • u = extract-min(Q)
  • for v of u の隣接頂点:
    • もし v が Q に含まれていて辺(u,v) の重みが v.key より小さいなら
      • v.π = u
      • v.key = 辺(u,v) の重み

出来上がった木が最小全域木になっている。

extract-min のコストによるが、、Q が 2 分ヒープなら全体のコストは O(E * lg(V))

24 単一始点最短路問題

重み付き有向グラフ G=(V,E) において u から v への最短路重み δ(u,v) を求める。パスがなければ ∞ と定義する。最短路は部分構造最適性を持つので、動的計画法と貪欲アルゴリズムが使えるかもしれない。実際 Dijkstra は貪欲アルゴリズム、全頂点間の最短路を求める Floyd-Warshall は動的計画法である。

負の重みを持つ閉路を含む場合、重み和が無限に小さくなる。

• 緩和 relax
  • 辺(u,v) の緩和は u を経由することで v への既知の最短路を改善できるかを判定し、改善できるなら更新する。

Bellman-Ford Algorithm

重みが負である辺の存在を許す単一始点最短路問題を解くアルゴリズム。負の閉路が存在すれば解がないことを報告し、負の閉路がなければ最短路とその重みを返す。グラフとその最短路は三角不等式を満たすとする。

• 初期化
  • すべての頂点の上界 d を ∞、π を Nil にする
  • 開始点 s.d = 0
• for |G.V| - 1 回 繰り返す:
  • for 辺(u,v) of G.E:
    • relax(u,v,辺(u,v) の重み)
• for 辺(u,v) of G.E:
  • v.d > u.d + 辺(u,v) の重み なら"解無し"
• "解あり"

実行時間は O(VE) である

有向非巡回グラフの単一視点最短路

• トポロジカルソートを行う
• ソートされた順に各頂点 u に対し、その隣接頂点をすべて緩和する

実行時間 Θ(V + E)

Dijkstra Algorighm

すべての辺の重みが 0 以上の場合は Bellman-Ford よりも高速に解くことができる。

• 初期化
  • すべての頂点の上界 d を ∞、π を Nil にする
  • 開始点 s.d = 0
  • 最短経路が決定された頂点の集合 S = ∅
  • min 優先度付きキュー Q = G.V
• while Q が空ではない:
  • u = extract-min(Q)
  • S = S ∪ {u}
  • for v of u の隣接頂点:
    • relax(u,v,辺(u,v) の重み)

実行時間は O(V^2)。ただしグラフが疎 |E| = o(V^2 / lg(V)) ならば min 優先度付きキュー Q を 2 分 min ヒープを用いることで O((V + E) * lg(V)) となる。

線形計画問題

差分制約式系 Ax<=b は、線形計画法の m x n 型行列 A の各行が 1 と-1 を 1 つずつ含み、それ以外は 0。これは制約グラフ constraint graph に対応づけることができる。

• 制約グラフ G は重み付き有向グラフで
  • V = {v0, v1, ..., vn}
  • E = {(vi,vj): xj-xi<=bk はある制約} ∪ {(v0,v1), (v0,v2), ..., (v0,vn)}
• x = (δ(v0,v1), δ(v0,v2), ..., δ(v0,vn)) は実行可能解の 1 つである

25 全点対最短路

単一始点の最短路アルゴリズムを頂点数分実行すれば解けるが、もっとうまく解ける。アルゴリズムには隣接行列表現を用いる。 n x n 型の重み行列 W を定める。全点対最短路を n x n 型行列 D に出力する。

動的計画法による解法

高々 m 本からなる、頂点 i から j への道の中で最小のものを lij(m) とする。lij(m) は lij(m-1) から導くことができる。lij(0) は明らか。lij(m) からなる行列を L(m) と置く。最短路が閉路になることはないので m は最大でも頂点数 |V|=n である。これを利用してボトムアップで全対の最短路を計算できる。ただし L(m-1) から L(m) を導くのに Θ(n^3) の時間がかかるので、全体では Θ(n^4) のオーダーとなってしまう。

反復 2 乗法 repeated squaring を用いると L(1)->L(2)->L(4)->L(8)...と計算を省略できるので、Θ(n^3 * lg(n)) のオーダーになる。

Floyd-Warshall Algorithm

i から j へのパスの中間頂点を考慮した部分構造最適性を利用する。実行時間 O(V^3) で解ける。

Johnson's Algorighm

疎なグラフの場合は上記 2 手法より漸近的に速い。O(V^2 _ lg(V) + V _ E)

• すべての重み 0 以上の場合、各頂点を始点として 1 回ずつ Dijkstra を使えば、、すべての頂点間の最短路を計算できる。フィボナッチヒープによる min 優先度付きキューを用いれば O(V^2 _ lg(V) + V _ E) で実行できる。
• 負の重みが存在するときは、1 組の非負の辺重みを新しく計算する。更新する際は全対の最短路が変わらないようにする。

26 最大フロー

有向グラフ G を考える。入口 source と出口 sink があり、辺を通じて通じて何かを流す。この流れる量をフローと呼ぶ。入口と出口以外の各頂点への流入量と出力量が等しいという条件と、各辺のキャパシティを超えない条件のもとで最大フローを探す問題。

逆並列辺が存在する場合は、仮想頂点を追加することで解決できるので、逆並列辺がない場合のみを考える。

複数の入口（出口）をもつ問題も考えられるが、これも仮想の超入口（超出口）を追加し、各入口（出口）に対して無限のキャパシティを持つ辺を追加することで対応可能になる。

Ford-Fulkerson method

フローネットワーク G とフロー f が与えられた。このとき、辺(u,v) の容量 c(u,v) とフロー f(u,v) の差を残余容量 residual capacity cf(u,v) とする。各辺に対し残余容量>0 の辺を残余ネットワーク residual network Gf に加える。

• cf(u,v)
  • c(u,v) - f(u,v) ((u,v) ∈ E)
  • f(v,u) ((v,u) ∈ E)
  • 0 (それ以外)

f を G のフロー、f'を Gf のフローとする。f の f'による増加 f↑f'を次のように定義する

• (f↑f')(u,v)
  • f(u,v) + f'(u,v) - f'(v,u) ((u,v) ∈ E)
  • 0 (それ以外)

増加可能経路 p は Gf 上の始点 s から終点 t への単純路である。p 上の最小残余容量だけ f を増やすことができる。 Ford-Fulkerson method の概略は以下のようである。

• フロー f を 0 に初期化する
• while 増加可能経路 p が残余ネットワーク Gf に存在
  • f を p に沿って増やす
• return f

この方法でなぜ最大フローが得られるのか？それは最大フロー最小カット定理 定理 26.6 に基づいている。

カット(S,T) と交差する純フロー net flow f(S,T) = Σu∈S (Σv∈T (f(u,v))) - Σu∈S (Σv∈T (f(v,u))) カット(S,T) の容量 c(S,T) = Σu∈S (Σv∈T (c(u,v)))

最小カットはネットワークのすべてのカットの中で最小容量のカット。

|f| = f(S,T) <= c(S,T)

計算量は増加可能経路の探索アルゴリズムによる。

Edmonds-Karp algorighm

Ford-Fulkerson method 増加可能経路を幅優先探索を用いて探索する。O(V*E^2)

2 部グラフの最大マッチング

無向グラフ G=(V,E) について、辺の部分集合 M で、すべての頂点について接続する M の辺が高々 1 つしかないものをマッチングという。|M| を最大化するマッチングを最大マッチングという。 2 部グラフは、頂点集合 V を互いに素な集合 L, R に分割し、辺 E がすべて L と R の間に張られているグラフである。 2 部グラフの最大マッチング問題は、最大フローネットワーク問題に変換できる。

27 マルチスレッドアルゴリズム

• 並列コンピュータのアーキテクチャ
  • 共有記憶 shared memory
  • 分散記憶 distributed memory
• 並行性プラットフォーム
  • 並列計算資源を調整、スケジュール、管理するためのソフトウェア
  • そのうちのひとつが動的マルチスレッド

並行性キーワード concurrency keyword を用いてマルチスレッドアルゴリズムの解析を行う

• マルチスレッド化キーワード
  • spawn 子手続きを生成する
  • sync spawn で生成された子手続きが終了されるのを待つ
• 並列ループキーサード
  • parallel すべてのループが並列実行可能を意味する
  • new parallel の中で共有記憶内で同じデータにアクセスしないように完全に分離する

マルチスレッド実行では命令の集合を計算 DAG computation dag というグラフとして考えるとわかりやすい。

マルチスレッドの理論的な効率

• 仕事量 work
  • 1 台のプロセッサで全体の計算を実行するのに必要な総時間
• スパン span
  • 計算 DAG の任意のパスに沿って実行するときの時間の最大値。DAG の最長路・クリティカルパスの頂点数に等しい。

p 台のプロセッサ上での実行時間を Tp と表す

• 仕事量の法則
  • Tp >= T1 / p
  • p 台のプロセッサを使っても、実行時間は 1/p 未満にはできない
• スパンの法則
  • Tp >= T∞
  • 理想的な環境で、無限台数を使った場合より速くすることはできない

解析に次の指標を定める

• 高速化率 speedup
  • T1/Tp で定義する。
  • 仕事量の法則より T1/Tp <= p。
  • T1/Tp = Θ(p) なら線形高速化といい、T1/Tp = pなら完全線形高速化という。
• 余裕度 parallel slackness
  • (T1/T∞)/p = T1/(p*T∞) で定義する
  • 計算の並列度がプロセッサ数を超えている程度を表す。
  • T∞ = T1 / 5 かつ p = 3 なら T1/(p*T∞) は 5/3
  • T∞ = T1 / 5 かつ p = 5 なら T1/(p*T∞) は 1
  • T∞ = T1 / 5 かつ p = 10 なら T1/(p*T∞) は 1/2

スケジューリング

貪欲スケジューラはどの時点でもできるだけ多くのストランドをプロセッサに割り当てる。p 個以上のストランドがある時間ステップに実行可能なら、このステップを完全ステップと呼ぶ。それ以外を不完全ステップと呼ぶ。

• 定理 27.1
  • p 台のプロセッサを持つ理想並列コンピュータ上で貪欲スケジューラは仕事量 T1、スパン T∞ のマルチスレッド計算を Tp <= T1/p + T∞ で実行する
• 系 27.2
  • 貪欲スケジューラは任意のマルチスレッドけい s 名を最悪の場合の 2 倍以内の実行時間で実行できる。

28 行列演算

Ax = b という連立一次方程式を解く

x = A^(-1)b を解けばいいのだが、これは数値的に不安定（計算途中で丸め誤差が増大する）。代わりに LUP 分解法 という方法を使う。これは数値的に安定し、逆行列を使った計算よりも高速。

• PA = LU となる n x n 行列 P, L, U を求める。
  • L は単位下三角行列（下三角行列で対角成分が全て 1）
  • U は上三角行列
  • P は置換行列（各行、各列に 1 がひとつだけ、それ以外は 0 となるもの）
• ステップ
  • Ax = b
  • PAx = Pb
  • LUx = Pb
  • Ux = y と置く
  • Ly = Pb
  • これを前進代入法で解く。Θ(n^2) である。
  • Ux = y を後退代入法で解く。Θ(n^2) である。

前進代入法も後退代入法も中学校レベルの計算

29 線形計画法

• 標準形
  • c, b, x はベクトル A は行列
  • maximize c^T x
  • subject to
    • Ax <= b
    • x >= 0
  • もし等式条件があれば不等式条件に治す
  • ax + bx = c は
  • ax + bx <= c かつ ax + bx >= c と同値
• スラック形
  • いくつかの"等式"といくつかの"一変数>=0"の形

単一始点最短路問題や最大フロー問題は線形計画法として定式化できる。線形計画法で解くのが最速ではないが。

シンプレックス法 simplex algorighm

• 制約を満たす基底解を取る。この時点では基底解は(0, 0, 0...)
• z を大きくするため x1 を制約の中で大きくしていく。最もタイトな制約の非基底変数と x1 を交換して新しいスラック形をとる（ピボット）。
• つぎに x3 を増やすことを考えよう。...

なぜこの方法で停止するのか、最適解が得られるのか、最初の実行可能基底解の見つけ方が書かれている。29.3

30 多項式と FFT

多項式 Polynominal の乗算

高々 n 次の多項式 A(x), B(x) の乗算の結果である C(x) を求める。

係数表現と座標表現という 2 つの表現方法を使うことで効率的に Θ(nlogn) で計算する。 係数表現（Σajxj）でそのまま計算すると Θ(n^2)

31 整数論的アルゴリズム

32 文字列照合

33 計算幾何学

34 NP 完全性

35 近似アルゴリズム