アルゴリズム入門

アルゴリズム入門
アルゴリズムとは
•
•
•
•
問題を解くための計算手順
曖昧さのない形式的な記述
計算機による実行も可能。
通常は、問題のどのような事例に対しても、
停止することを要請。
データ構造とは
• データの計算機上での表現方法
• 同じデータにも多数の表現方法がある。
例えば、集合を表現するには、
– 辞書
– ハッシュ表
– 優先度つき待ち行列、２分探索木
– トライ、平衡木、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 += 2
i += 1
例：二分探索
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);
print(a, 0, 9);
}
ソーティングの計算量
• 選択ソートおよびバブルソートは、
配列の大きさをnとしたとき、
時間計算量はO(n2)
• 配列によらない。
時間の計測
• SystemクラスのcurrentTimeMillis()という
スタティック・メソッドを用いることができる。
long t0 = System.currentTimeMillis();
...
long t1 = System.currentTimeMillis();
System.out.println(t1-t0);
演習
• Sortingにおいて、
long t0 = System.currentTimeMillis();
bubblesort(a, 0, 19999);
long t1 = System.currentTimeMillis();
System.out.println(t1-t0);
のようにして、ソーティングにかかる時間を
計測してみよ。
古典的な教科書
• データ構造とアルゴリズム
– 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
具体的なプログラムが豊富。
演習
• 選択ソートおよびバブルソートに対して、配列
を大きくして、時間計算量を実測してみよ。
• クイックソートの計算量について考察せよ。
• クイックソートのプログラムに、既にソート済
みの配列を与えた場合、時間計算量はどの
ようになるか。
⇒ 計算量の回

Download Report