算法数理工学 第1回 定兼　邦彦

目的・成績評価・参考書 アルゴリズム理論による設計は，大規模なデータを高速で処理する際に特に有効 部品 (データ構造) を組み合わせてプログラムを作るだけでなく， 部品の中身を理解する 成績評価は試験とレポート メール： sada@mist.i.u-tokyo.ac.jp ホームページ： http://researchmap.jp/sada/ 居室: 工学部6号館341 参考書：アルゴリズムイントロダクション(近代科学社)など プログラミング問題集 AIZU ONLINE JUDGE 問題セットの Introduction to Algorithms and Data Structures http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=ALDS1

アルゴリズムの概念 ～ オーダーと計算量 ～ ・ 算法 = アルゴリズム (algorithm) ・ アルゴリズムの概念 ・ オーダーの定義と計算量

アルゴリズム アルゴリズムとは 明確に定義された計算問題を解くための道具 問題の記述とは 入力 (input): ある値(の集合) 出力(output): ある値(の集合) 明確に定義された計算手続き 明確に定義された計算問題を解くための道具 問題の記述とは 望むべき入出力関係を指定すること

ソーティング問題の形式的定義 入力: n 個の数の列 〈a1, a2, ..., an〉 出力: a’1 a’2  …  a’n であるような入力列の置換 〈a’1, a’2, ..., a’n〉 入力例 (具体例, instance) 入力 〈31, 41, 59, 26, 41,58〉 出力 〈26, 31, 41, 41, 58, 59〉

ソーティング 計算機科学における基本的な操作 多くのアルゴリズムが開発されている 入力例によって優劣が異なる ソートすべきデータの数 どの程度までデータがすでにソートされているか 用いる記憶装置の種類 (主記憶, ディスク, テープ)

アルゴリズムの正しさ アルゴリズムが正しい (correct) 正しくないアルゴリズム 確率的アルゴリズムも存在 ⇒全ての具体例に対して正しい出力とともに停止する 与えられた計算問題を解く (solve) という． 正しくないアルゴリズム ある具体例に対して望ましい答えを出力せずに停止 ある具体例に対して全く停止しない 確率的アルゴリズムも存在 モンテカルロ法 (高い確率で正しい答えを出す) 円周率の計算，素数判定 ラスベガス法 (高い確率で早く停止する) ランダムクイックソート

挿入ソート 入力: 長さ n の配列 A[0..n-1] 出力: ソートされた配列 A[0..n-1] 入力 出力 void INSERTION-SORT(data *A, int n) { data key; int i, j; for (j=1; j < n; j++) { key = A[j]; // A[j] をソート列 A[0..j-1] に挿入する i = j – 1; while (i >= 0 && A[i] > key) { A[i+1] = A[i]; i = i -1; } A[i+1] = key; 入力 5 2 4 6 1 3 2 5 4 6 1 3 2 4 5 6 1 3 2 4 5 6 1 3 1 2 4 5 6 3 出力 1 2 3 4 5 6

C言語の場合 int main(int argc, char *argv[]) #include <stdio.h> { data A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}; int i,n; n = 14; INSERTION_SORT(A,n); for (i=0;i<n;i++) printf("%d ",A[i]); printf("\n"); } #include <stdio.h> #include <stdlib.h> typedef int data; void INSERTION_SORT(data *A, int n) { data key; int i, j; for (j=1; j < n; j++) { key = A[j]; // A[j] をソート列 A[0..j-1] に挿入する i = j - 1; while (i >= 0 && A[i] > key) { A[i+1] = A[i]; i = i - 1; } A[i+1] = key;

アルゴリズムの解析 アルゴリズムの実行に必要な資源を予測したい 解析を行うにはモデルを仮定する必要がある メモリ量 通信バンド幅, 論理ゲート 計算時間 解析を行うにはモデルを仮定する必要がある RAM (random access machine) モデル 命令は1つずつ実行 どのメモリ番地も一定の時間で読み書き可

挿入ソートの解析 INSERTION-SORTの手続きに要する時間は入力によって変わる. 一般に, プログラムの実行時間は入力のサイズの関数で表す. 入力サイズの定義 ソーティング, 離散フーリエ変換など: データ数 整数の積の計算など: 入力のビット数 グラフの問題: グラフの頂点と辺の数

実行時間の定義 実行される基本的な演算の回数 プログラムの第 i 行の実行に ci 時間かかるとする (ci は定数) 注: サブルーチン呼び出しは定数時間ではない

tj : while ループが j の値に対して実行される回数 void INSERTION-SORT(data *A, int n) { data key; int i, j; for (j=2; j <= n; j++) { key = A[j]; // A[j] をソート列 A[1..j-1] に挿入する i = j – 1; while (i > 0 && A[i] > key) { A[i+1] = A[i]; i = i -1; } A[i+1] = key; コスト 回数 c1 n c2 n-1 c4 n-1 c5 c6 c7 c8 n-1 tj : while ループが j の値に対して実行される回数

INSERTION-SORTの実行時間 n の線形関数 (linear function) tj の値は入力によって変化する. 最良の場合 = 配列が全てソートされている場合 tj = 1 n の線形関数 (linear function)

最悪の場合 配列が逆順にソートされている場合 tj = j n の2次関数 (quadratic function)

時間計算量 (Time Complexity) アルゴリズムの実行時間は入力に依存する アルゴリズムの解析では通常最悪時の実行時間を考える 最悪時の実行時間は任意の入力に対する実行時間の上界 最悪時の実行時間を保証する 「最悪時」は頻繁に起きる (データベース検索など) 平均時も最悪時と同じくらい悪い (挿入ソートで数をランダムに挿入)

増加のオーダ 実行時間の解析を容易にするための抽象化 挿入ソートは (n2) という最悪実行時間を持つ あるアルゴリズムが他より効率がよい 各行の実行時間 (コスト) を定数 ci とする 最悪の実行時間を an2+bn+c と表す 実行時間の増加率をみるには主要項 an2 で十分 定数係数も無視 (n2) と表す 挿入ソートは (n2) という最悪実行時間を持つ あるアルゴリズムが他より効率がよい ⇔最悪実行時間の増加率が低い

関数のオーダ アルゴリズムの効率を実行時間のオーダで 特徴付け, 相対的な比較を行う 入力サイズ n が大きいときの挙動を知りたい アルゴリズムの効率を実行時間のオーダで 特徴付け, 相対的な比較を行う 入力サイズ n が大きいときの挙動を知りたい アルゴリズムの漸近的 (asymptotic) な効率を 調べる

漸近記号 -記法 ある関数 g(n) に対し, (g(n)) は次のような集合と定義する 　(g(n)) = {f(n): 全ての n  n0に対して 　　 0c1 g(n)  f(n)  c2 g(n) となるような 　　 正の定数c1 , c2 , n0 が存在} f(n) = (g(n)) は f(n)  (g(n)) を意味する 2n2+3n+1 = 2n2 + (n) という表現も用いる

O-記法 ある関数 g(n) に対し, O(g(n)) は次のような集合と定義する 　O(g(n)) = {f(n): 全ての n  n0に対して 　　 0  f(n)  c g(n) となるような 　　 正の定数c, n0 が存在} f(n) = (g(n)) ならば f(n) = O(g(n)) n = O(n2) も正しい表現

実行時間がO(n2)であるという場合, 最悪実行時間について言っている 実行時間は入力データに依存するため 最悪実行時間はデータ数 n のみに依存

-記法 ある関数 g(n) に対し, (g(n)) は次のような集合と定義する 　  (g(n)) = {f(n): 全ての n  n0に対して 　　 0  c g(n)  f(n) となるような 　　 正の定数c, n0 が存在} f (n), g(n) に対して f(n) = (g(n)) であるための必要十分条件は f(n) = O(g(n)) かつ f(n) = (g(n))

挿入ソートの最良の実行時間は(n)とは -記法は下界を表す 挿入ソートの最良の実行時間は(n)とは このアルゴリズムではどのような入力に対しても n に比例した時間が必ず必要という意味 アルゴリズムの実行時間が(n2)とは どのような入力に対しても少なくとも n2 に比例する時間がかかるという意味

o-記法 (リトルオー) ある関数 g(n) に対し, o(g(n)) は次のような集合と定義する 　o(g(n)) = {f(n): 任意の定数 c > 0 に対し ある定数 n0 が存在し, 全ての n  n0に対して 　 0  f(n)  c g(n)}

-記法 　(g(n)) = {f(n): 任意の定数 c > 0 に対し ある定数 n0 が存在し, 全ての n  n0に対して 　 0  c g(n)  f(n)} n2/2 = (n) n2/2  (n2)

アルゴリズムの設計 挿入ソート: 逐次添加法 (incremental approach) 分割統治法 (divide-and-conquer) に基づく方法 →マージソート 実行時間の解析が容易であることが多い

分割統治法 問題の再帰的な (recursive) 構造を利用 マージソートでは 分割：問題をいくつかの小さな部分問題に分割 統治：各部分問題を再帰的に解く 統合：それらの解を組合わせて元の問題の解を構成 マージソートでは 分割： n 要素の列を n/2 要素の2つの部分列に分割 統治：マージソートを用いて2つの部分列をソート 統合：2つのソートされた部分列を統合して答を得る

マージソート void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート { int q; if (p < r) { // p==r ならソートする必要なし q = (p+r)/2; MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合 }

1 2 2 3 4 5 6 6 マージ 2 4 5 6 1 2 3 6 マージ マージ 2 5 4 6 1 3 2 6 マージ マージ マージ マージ 5 2 4 6 1 3 2 6

マージ 一時的な配列 B[0,n-1] を用いる void MERGE(data *A, int p, int q, int r, data *B) { // ソートされた部分列 A[p..q] と A[q+1..r] を統合 int i,j,k; data t; k = p; i = p; j = q+1; while (k <= r) { if (j > r) t = A[i++]; // 前半のみにデータがある else if (i > q) t = A[j++]; // 後半のみにデータがある else if (A[i] <= A[j]) t = A[i++]; // 前半のほうが小さい else t = A[j++]; // 後半のほうが小さい B[k++] = t; // 一時的な配列に保存 } for (i=p; i<=r; i++) A[i] = B[i]; // 元の配列に書き戻す

void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート { int q; if (p < r) { // p==r ならソートする必要なし q = (p+r)/2; MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合 } int main(int argc, char *argv[]) data A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}; data B[14]; int i,n; n = 14; MERGE_SORT(A,0,n-1,B); for (i=0;i<n;i++) printf("%d ",A[i]); printf("\n");

分割統治アルゴリズムの解析 全体の実行時間は問題のサイズに関する漸化式 (recurrence) で記述できることが多い サイズ n の問題に関する実行時間を T(n) とする n  c (ある定数) ならば定数時間((1)) 問題を a 個の部分問題に分割し, それぞれが元のサイズの 1/b 倍になったとすると D(n), C(n): 問題の分割, 統合にかかる時間

マージソートの解析 T(n)= (n lg n) となる n は2のべき乗と仮定する n = 1のとき T(n) = (1) 分割： D(n) = (1) 統治：再帰的にサイズn/2の部分問題を解く 2T(n/2) 統合：MERGEは C(n) = (n) T(n)= (n lg n) となる

アルゴリズムの重要性 コンピュータが速くても, 実行時間のオーダが大きいアルゴリズムは役に立たない スーパーコンピュータで挿入ソートを実行 1秒間に1億命令実行 2n2 命令必要 パーソナルコンピュータでマージソートを実行 1秒間に100万命令実行 50 n lg n 命令必要

100万個の数の配列のソート ス－パーコンピュータで挿入ソート パーソナルコンピュータでマージソート オーダの低いアルゴリズムの開発が重要

問題の計算量 アルゴリズムの計算量ではなく，問題の計算量 （計算複雑度）という概念がある ある問題の計算量が O(f(n)) とは その問題を解くあるアルゴリズム A が存在し， 任意の入力に対する計算時間が O(f(n)) である． 例：ソーティングの計算量は O(n log n) (マージソートはどんな入力でも O(n log n) 時間だから)

計算量の議論をする場合は，計算モデルを明確にする必要がある ある問題の計算量が Ω(f(n)) とは その問題に対するどんなアルゴリズムにも，計算時間が Ω(f(n)) となる入力が存在する 例：比較ソートの計算量は Ω(n log n) 証明は後日行う ある問題の計算量が (f(n)) とは O(f(n)) かつ Ω(f(n)) 例：比較ソートの計算量は (n log n) 計算量の議論をする場合は，計算モデルを明確にする必要がある

クイックソート n 個の数に対して最悪実行時間(n2)のソーティングアルゴリズム 平均実行時間は(n log n) 記法に隠された定数も小さい in-place (一時的な配列が必要ない)

クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング 部分問題への分割: 部分問題の解決 (統治): 配列 A[p..r] を2つの部分配列 A[p..q] と A[q+1..r] に再配置する． A[p..q] のどの要素も A[q+1..r] の要素以下にする． 添字 q はこの分割手続きの中で計算する． 部分問題の解決 (統治): 部分配列 A[p..q] と A[q+1..r] を再帰的にソート 部分問題の統合 A[p..r] はすでにソートされているので何もしない

クイックソートのコード void QUICKSORT(data *A, int p, int r) { int q; if (p < r) { q = PARTITION(A,p,r); QUICKSORT(A,p,q); QUICKSORT(A,q+1,r); } main() QUICKSORT(A,0,n-1);

配列の分割 int PARTITION(data *A, int p, int r) // O(n) 時間 { int q, i, j; data x, tmp; x = A[p]; i = p-1; j = r+1; while (1) { do {j = j-1;} while (A[j] > x); do {i = i+1;} while (A[i] < x); if (i < j) { tmp = A[i]; A[i] = A[j]; A[j] = tmp; } else { return j; }

A[p..r] 初期状態： i と j は配列の範囲外 x = A[p] = 5 によって分割 x: 枢軸 (pivot) と呼ぶ 5 3 2 6 4 1 3 7 i j A[i]  x A[j]  x となる最初の i, j 7 は正しい分割位置にある 5 3 2 6 4 1 3 7 i j A[i] と A[j] を交換 正しい分割位置になる 3 3 2 6 4 1 5 7 i j

A[i]  x A[j]  x となる最初の i, j 3 3 2 6 4 1 5 7 i j 3 3 2 1 4 6 5 7 A[i] と A[j] を交換 i j i  j となったので q = j を返す A[p..q] は x 以下 A[q+1..r] は x 以上 3 3 2 1 4 6 5 7 j i

PARTITIONの正当性 PARTITIONの返り値を q とする A[p..r] の分割後に満たされるべき条件 A[p..q] はある pivot x 以下 A[q+1..r] は x 以上 p  q < r q = r となると，QUICKSORTは停止しないため，どんな A に対しても q < r となることを保障する必要がある

do {j = j-1;} while (A[j] > x); 初期状態は i < j do {j = j-1;} while (A[j] > x); 　 do {i = i+1;} while (A[i] < x);　の終了後 p  i, j  r A[j+1..r] は x 以上 A[p..i-1] は x 以下 A[i]  x  A[j] i < j のとき，A[i] と A[j] を交換すると A[j..r] は x 以上 A[p..i] は x 以下 i  j のとき q = j

PARTITIONの終了時に q = j = r とする while (1) のループを実行する毎に j は1以上減る 終了時に j = r ならばこのループは1度しか実行されていない しかし1回目のループでは x = A[p] なので i = p PARTITIONは p < r の場合のみ呼ばれるので， 1回目のループでは p = i < j = r つまり1回目のループでは終了しない よってPARTITION終了時に q = r とはならない． つまり q < r

クイックソートの性能 クイックソートの実行時間は分割が平均化されているかどうかに依存 これはpivotの選択に依存 分割が平均化されていれば実行時間は漸近的にマージソートと同じ ((n log n)) 最悪時は (n2)

最悪の分割 最悪の場合は，PARTITIONによって領域が 1 要素と n-1 要素に分けられる場合 分割には (n) 時間かかる 実行時間に対する漸化式は T(n) = T(n1) + (n), T(1) = (1) T(n) = (n2) 最悪実行時間は挿入ソートと同じ 入力が完全にソートされているときに起こる (挿入ソートなら O(n) 時間)

再帰木

最良の分割 クイックソートが最も速く動作するのは，PARTITIONによってサイズ n/2 の2つの領域に分割されるとき. T(n) = 2T(n/2) + (n) T(n) = (n lg n) ちょうど半分に分割される場合が最速

平衡分割 PARTITIONで常に 9 対 1 の比で分割されると仮定する T(n) = T(9n/10) + T(n/10) + (n) 再帰の深さは 漸近的には中央で分割するのと同じ 分割の比が 99 対 1 でも同じ (定数比なら良い)

クイックソートの 確率的アルゴリズム クイックソートの平均的な場合の実行時間を解析する場合，入力の頻度を仮定する必要がある． 通常は，すべての順列が等確率で現れると仮定 しかし実際にはこの仮定は必ずしも期待できない この仮定が成り立たなくてもうまく動作するクイックソートの確率的アルゴリズムを示す

確率的 (randomized) アルゴリズム 動作が入力だけでなく乱数発生器 (random-number generator)に依存するアルゴリズム 関数 RANDOM(a,b): a 以上 b 以下の整数を等確率で返すとする． プログラミング言語は擬似乱数発生器 (pseudorandom-number generator) を備える 擬似乱数: 統計的にはランダムに見えるが，決定的に作られる数(の列)

乱数発生法 {0, 1, …, p1} の整数を一様ランダムに生成 C言語 int x; x = rand() % p; // 整数乱数を p で割った余り

乱数の種の設定 現在時刻を乱数の種にする C言語 srand((int)clock()); srand((int)time(NULL));

確率的アルゴリズム1 クイックソートを行う前に入力配列の要素をランダムに並び替える 実行時間は入力順序に依存しなくなる アルゴリズムがうまく動作しないのは，乱数発生器によって運の悪い順列を作る場合のみ 最悪の実行時間は改善されない ((n2)) 最悪の場合はほとんど起きない

確率的アルゴリズム2 配列を A[p..r] を分割する前に， A[p] と A[p..r] からランダムに選んだ要素を交換 pivotが rp+1 個の要素から等確率で選ばれることを保障する 分割が平均的にはバランスのとれたものになることが期待できる

int RANDOMIZED_PARTITION(data *A, int p, int r) { int i; data tmp; i = RANDOM(p,r); tmp = A[i]; A[i] = A[p]; A[p] = tmp; // 値の交換 return PARTITION(A,p,r); } void RANDOMIZED_QUICKSORT(data *A, int p, int r) int q; if (p < r) { q = RANDOMIZED_PARTITION(A,p,r); RANDOMIZED_QUICKSORT(A,p,q); RANDOMIZED_QUICKSORT(A,q+1,r);

最悪の場合の解析 T(n): サイズ n の入力に対するQUICKSORTの最悪実行時間 T(n) = O(n2) を示す m < n に対し T(m)  cm2 と仮定

c は 2c(n1) が (n) の項よりも大きくなるように 十分大きくとる よって T(n) = O(n2) が示された

平均的な場合の解析 T(n): サイズ n の入力に対するRANDOMIZED QUICKSORTの平均実行時間 入力データはすべて異なる数とする

分割の解析 RANDOMIZED_PARTITIONでPARTITIONが呼ばれるとき，A[p] の要素は A[p..r] のランダムな要素と置き換えられている． 観察：PARTITIONによって返される q の値は A[p..r] の中での x = A[p] のランクのみに依存 x のランク rank(x) = 集合中の x 以下の要素数 要素数 n = rp+1 rank(x) = i となる確率は 1/n

rank(x) = 1 のとき，PARTITIONでのループは i = j = p で終了 このとき q = j = p つまり分割の小さい方のサイズは 1．この事象が起きる確率は 1/n rank(x)  2 のとき，x = A[p] より小さい値が少なくとも1つ存在 PARTITIONでの最初のループ実行後は i = p，j > p A[i] と A[j] を入れ替えるため，x = A[p] は右の分割に入る

PARTITIONが停止したとき，左の分割には rank(x)1 個の要素があり，それらは x より小さい rank(x)  2 のとき，左の分割のサイズが i である確率は 1/n (i = 1,2,...,n-1) rank(x) が1の場合と2以上の場合を合わせると， 左の分割のサイズ rp+1 が 1 になる確率: 2/n i になる確率: 1/n (i = 2,3,...,n-1)

平均時に対する漸化式 T(n): n 要素の入力配列をソートするのに必要な平均時間 T(1) = (1) 統治: 長さ q と nq の部分配列を再帰的にソート

T(1)=(1), T(n1) = O(n2) より よって T(n) は次のように書ける

m < n に対し T(m)  am lg m + b (a>0, b>0) と仮定 を用いる が (n)+b 以上になるように a を選ぶと

T(n) においても成り立つ よってクイックソートの平均実行時間は O(n lg n)

の証明