スライド 1

アルゴリズム入門
アルゴリズムとは
•
•
•
•
問題を解くための計算手順
曖昧さのない形式的な記述
計算機による実行も可能。
通常は、問題のどのような事例に対しても、
停止することを要請。
データ構造とは
• データの計算機上での表現方法
• 同じデータにも多数の表現方法がある。
例えば、集合を表現するには、
– 辞書
– ハッシュ表
– 優先度つき待ち行列、２分探索木
– トライ、平衡木、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)
• 配列によらない。
最短経路
• 有向グラフの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;
これは、スタティック変数という。
バックトラック
• 再帰的な手続きを用いると、
パズルの解の探索など、
後戻りしながら場合を尽くす過程を
簡単に実現することができる。
• 参考例：８クイーンのパズル
演習
• 選択ソートおよびバブルソートに対して、配列
を大きくして、時間計算量を実測してみよ。
• クイックソートの計算量について考察せよ。
• クイックソートのプログラムに、既にソート済
みの配列を与えた場合、時間計算量はどの
ようになるか。
⇒ 計算量の回

Download Report