アルゴリズム入門

アルゴリズムとは 問題を解くための計算手順 曖昧さのない形式的な記述 計算機による実行も可能。 通常は、問題のどのような事例に対しても、 停止することを要請。

データ構造とは データの計算機上での表現方法 同じデータにも多数の表現方法がある。 例えば、集合を表現するには、 様々なデータ構造 辞書 ハッシュ表 優先度つき待ち行列、２分探索木 トライ、平衡木、MFSET 様々なデータ構造 リスト、スタック、待ち行列、写像 木 グラフ

アルゴリズムとデータ構造 アルゴリズム＋データ構造＝プログラム 具体的なデータ構造に対して、 アルゴリズムを計算機に実行可能な形式、 すなわちプログラミング言語によって 記述したものがプログラムである。 データ構造が違えば、アルゴリズムも異なる。 すると、プログラムの効率も違って来る。

アルゴリズムの計算量 入力のサイズに従って、 計算の手間がどのように増えるか。 時間計算量 領域計算量 計算にかかる時間 計算に費やされるメモリの量 つまり、計算の過程において、 中間結果を保持するためにどのくらいの メモリが必要か。

例：線形探索 static int search(int[] a, int key) { int n = a.length; for (int i = 0; i < n; i++) if (a[i] == key) return i; return -1; } 等しさは== 代入は=

配列について 整数の配列 int[] a; このように変数を宣言しただけでは、 配列の本体はまだない。（aの値はnull） 配列の生成 a = new int[100]; 変数aは、配列への参照（reference）を保持している。 宣言＋生成 int[] a = new int[100]; 配列の長さ a.length 配列を引数として渡したり、配列をメソッドの値として返したりりすることができるが、それはすべて、 参照をやりとりしている。 sort(a, 0, a.length-1)

for文 for (int 制御変数 = 初期値; 条件; 更新部) { ... } 条件 更新部 i<n i<=n i++ i = i+1 i += 1 i += 2

例：二分探索 static int search(int[] a, int key) { int low = 0; int high = a.length-1; while (low <= high) { int middle = (low + high) / 2; if (key == a[middle]) return middle; else if (key < a[middle]) high = middle -1; else low = middle + 1; } return -1;

二分探索の計算量 配列の大きさをnとする。 whileループを回る度に、 探索する範囲が半分（以下）に減るので、 log2nに比例した時間（以下）で keyが見つかるか、 keｙが見つからずに終了して-1が返る。 時間計算量はO(log2n) この場合は、最悪の計算量 線形探索の計算量はO(n)

バブルソート static void bubblesort(int[] a, int from, int to) { for (int i = from; i <= to; i++) for (int j = to; j > i; j--) if (a[j-1] > a[j]) { int w = a[j]; a[j] = a[j-1]; a[j-1] = w; }

配列のランダムな初期設定 static void random(int[] a, int from, int to) { java.util.Random r = new java.util.Math.Random(); for (int i = from; i <= to; i++) a[i] = r.nextInt(65536); }

public static void main(String[] args) { int[] a = new int[10]; random(a, 0, 9); print(a, 0, 9); bubblesort(a, 0, 9); }

ソーティングの計算量 選択ソートおよびバブルソートは、 配列の大きさをnとしたとき、 時間計算量はO(n2) 配列によらない。

最短経路 有向グラフのstart点から与えられたgoal点までの最短の経路を求める。ここでは、各辺の長さは１とする。 点の数はn。各点は0～n-1の番号で参照。 for (int i = 0; i < n; i++) step[i] = -1; step[start] = 0; for (int s = 0; step[goal] == -1; s++) for (step[i]==sを満たす各iについて) for (iと隣接する各kについて) if (step[k] == -1) { step[k] = s+1; prev[k] = i; } プログラムは後ほど

古典的な教科書 データ構造とアルゴリズム 基本的なデータ構造とそのアルゴリズム ソート アルゴリズムの解析法 アルゴリズムの設計法 A.V.エイホ・J.E.ホップクロフト・J.D.ウルマン著 大野義夫訳 培風館 基本的なデータ構造とそのアルゴリズム ソート アルゴリズムの解析法 アルゴリズムの設計法

基本的なデータ構造 リスト、スタック、待ち行列、写像 木 集合を表現するデータ構造 有向グラフ 無向グラフ ２分木 辞書 ハッシュ表 優先度つき待ち行列、２分探索木 トライ、平衡木、MFSET 有向グラフ 無向グラフ

基本的なアルゴリズム 有向グラフ 無向グラフ ソート 最短経路問題 強成分 コスト最小の極大木 関節点と二重連結成分 グラフのマッチング クイックソート、ヒープソート ビンソート、基数ソート 比較によるソートの下限

アルゴリズムの設計法 分割統治アルゴリズム 動的計画法（ダイナミックプログラミング） 欲ばりアルゴリズム バックトラッキング ワールドシリーズの賭け率 三角形分割問題 欲ばりアルゴリズム 巡回セールスマン問題 バックトラッキング ゲームの木・巡回セールスマン問題 局所的な探索アルゴリズム 最小コストの極大木・巡回セールスマン問題

より新しい教科書 Introduction to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest The MIT Press and McGraw-Hill Book Company, 1989

C言語を対象とした教科書 Cプログラマのための アルゴリズムと データ構造 近藤嘉雪【著】 SOFT BANK Publishing 具体的なプログラムが豊富。

再帰的手続き

再帰 自分自身を参照すること。 再帰的な定義 再帰的な手続き ユダヤ人とは、ユダヤ教徒であるか、 ユダヤ人を母とする者。 自分自身を呼び出す手続き。 常に自分を呼び出していては停止しない。 static void loop() { loop(); }

組み合わせの数 m個の中からn個を選ぶ組み合わせの数 漸化式 mCn = 1 (n=0 or n=m) mCn = m-1Cn-1 + m-1Cn (0<n<m) static int comb(int m, int n) { if (n == 0) return 1; if (n == m) return 1; int c1 = comb(m-1, n-1); int c2 = comb(m-1, n); return c1+c2; }

クイックソート static void quicksort(int[] a, int p, int q) { int i = p; int j = q; int x = a[(p+q)/2]; do { while (a[i] < x) i++; while (x < a[j]) j--; if (i <= j) { int w = a[i]; a[i] = a[j]; a[j] = w; i++; j--; } } while (i <= j); if (p < j) quicksort(a, p, j); if (i < q) quicksort(a, i, q);

変数について メソッドの中で宣言される変数は、そのメソッドに局所的であり、メソッドの呼出しごとに別の領域が割り当てられる。 従って、再帰呼び出しの間で変数が混乱することはない。 このようなメソッドに局所的な変数の他に、クラスのメソッドの間で共有される変数がある。 static int n; これは、スタティック変数という。

バックトラック 再帰的な手続きを用いると、 パズルの解の探索など、 後戻りしながら場合を尽くす過程を 簡単に実現することができる。 参考例：８クイーンのパズル

演習 選択ソートおよびバブルソートに対して、配列を大きくして、時間計算量を実測してみよ。 クイックソートの計算量について考察せよ。 クイックソートのプログラムに、既にソート済みの配列を与えた場合、時間計算量はどのようになるか。 ⇒ 計算量の回