アルゴリズム入門.

Presentation on theme: "アルゴリズム入門."— Presentation transcript:

1 アルゴリズム入門

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

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

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

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

6 例：線形探索 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; } 等しさは== 代入は=

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

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

9 例：二分探索 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;

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

11 バブルソート 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; }

12 配列のランダムな初期設定 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); }

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

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

15 時間の計測 SystemクラスのcurrentTimeMillis()という スタティック・メソッドを用いることができる。
long t0 = System.currentTimeMillis(); ... long t1 = System.currentTimeMillis(); System.out.println(t1-t0);

16 演習 Sortingにおいて、 long t0 = System.currentTimeMillis();
bubblesort(a, 0, 19999); long t1 = System.currentTimeMillis(); System.out.println(t1-t0); のようにして、ソーティングにかかる時間を 計測してみよ。

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

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

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

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

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

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

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