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

Presentation on theme: "算法数理工学 第1回 定兼　邦彦."— Presentation transcript:

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

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

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

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

5 ソーティング問題の形式的定義 入力: 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〉

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

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

8 挿入ソート 入力: 長さ 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

9 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;

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

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

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

13 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; コスト 回数 c n c n-1 c n-1 c5 c6 c7 c n-1 tj : while ループが j の値に対して実行される回数

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

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

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

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

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

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

20

21

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

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

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

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

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

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

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

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

30 マージソート 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] を統合 }

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

32 マージ 一時的な配列 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]; // 元の配列に書き戻す

33 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");

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

35 マージソートの解析 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) となる

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

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

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

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

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

41 クイックソートの記述 分割統治法に基づく 部分配列 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] はすでにソートされているので何もしない

42 クイックソートのコード 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);

43 配列の分割 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; }

44 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

45 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

46 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 となることを保障する必要がある

47 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

48 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

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

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

51 再帰木

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

53

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

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

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

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

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

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

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

61 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);

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

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

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

65 分割の解析 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

66 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] は右の分割に入る

67 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)

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

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

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

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

72 の証明