情報工学概論 (アルゴリズムとデータ構造)

Presentation on theme: "情報工学概論 (アルゴリズムとデータ構造)"— Presentation transcript:

1 情報工学概論 (アルゴリズムとデータ構造)

2 アルゴリズムの概念 ～ オーダーと計算量 ～ ・ コンピュータの基礎 ・ アルゴリズムの概念 ・ オーダーの定義と計算量 ・ NP完全問題

3 自己紹介 名前： 定兼 邦彦 所属： 国立情報学研究所 & 総合研究大学院大学
名前： 定兼　邦彦 所属： 国立情報学研究所　&　総合研究大学院大学 経歴： 1991年理1入学，2000年理学系研究科情報科学専攻終了 2000年　東北大学情報科学研究科助手 2003年　九州大学システム情報科学研究院助教授 2009年　国立情報学研究所准教授 研究分野： データ圧縮，データ構造，情報検索 最近の研究： 簡潔データ構造 文字列検索のデータ構造 Webグラフ構造の解析，探索

4 目的・成績評価・参考書 ・ アルゴリズム理論による設計は、大規模なデータを高速で処理する際に特に有効
・ 部品 (データ構造) を組み合わせてプログラムを作るだけでなく， 部品の中身を理解する ・ 成績評価はレポート ・ 参考書：アルゴリズムイントロダクション(近代科学社)など ・ メール： ホームページ：

5 授業の内容 ・ コンピュータの仕組み、プログラムの仕組み CPU、メモリ、OS、メモリ管理、命令、変数 ・ データ構造（データの記憶方法）
　スタック、キュー、ヒープ、２分木、ハッシュ ・ 基本的なアルゴリズム 　再帰呼び出し、分割統治、列挙、動的計画法、ソート、文字列マッチング ・ 応用アルゴリズム 　計算幾何，行列演算，索引構造

6 コンピュータの基礎

7 コンピュータの基礎 CPU メモリ ・ コンピュータはいくつかの部品で成り立っているが、メインの部分はCPUとよばれる演算装置
・ 車でいえばエンジンのようなもので、これがあるかないかが、コンピュータであるかどうかの境目のようなもの ・ CPUの他にメモリという、数値を複数記録できる装置がある CPU メモリ

8 プログラム CPU メモリ ・ コンピュータができることは、 － メモリから数値を読むこと、および書くこと
　 － メモリから数値を読むこと、および書くこと 　 － 足す引く掛けるなどの算術演算をすること 　 － 数の大小の判定をして、行う処理を変えること ・ これらの操作のことを命令という ・ 命令をどのように行うかは、やはりメモリに記録する。これを プログラム と言う ・ プログラムに書かれたとおりに処理を行わせることを、プログラムを 実行する という CPU メモリ

9 プログラムの実行 CPU メモリ ・ プログラムは、メモリに書いてある命令を順次実行する
・ 命令は数値になっていて、それぞれの数値に機能が割当てられている ・ 処理中に、次から行う処理の場所を変更することができる ・ 条件によって処理を変える場合には、この機能を使って、条件を満たす場合のみ次から実行する命令を変える（条件分岐という） CPU メモリ

10 プログラミング言語 ・ CPUの命令は数値。しかも、１つ１つの処理は非常に単純（これをマシン語、あるいは機械語という）
・ これを組合せてプログラムを作るのは、かなり大変 ・ そこで、通常はもう少し抽象化して、人間に見やすくした「高級言語」とよばれるものを使う （C，JAVA，Perl, Ruby, Basic, シェルスクリプトなど） ・ 高級言語で書かれたプログラムを、CPUに実行させるには、プログラムをいったんマシン語に翻訳する（この作業をコンパイルという）か、プログラムどおりの処理をするプログラム（インタープリタという）を使う

11 概念的な例 CPU メモリ １： 場所 15 に 0 を書き込む ２： 場所 16 に 2 を書き込む
３： 場所 15 と 16 の値を足し、それを場所 15 に書き込む ４： 場所 17 の値が 10 以上ならば、８へいく ５： ３へ行く ８： ．．． ・ 3－5のように局所的に繰り返して実行される部分をループという CPU メモリ

12 メモリのアクセス ・ メモリは1バイトずつ数値が記憶されている
・ メモリには、記憶場所に0から始まる番号がついていて、好きな場所のデータに一手でアクセス（書き込み／読み出し）できる ・ このように、好きな場所に一手でアクセスできるメモリをランダムアクセスメモリという ・ ランダムアクセスでない記憶装置は、例えばCDとかビデオテープ １ ０

13 キャッシュメモリ CPU キャッシュ メモリ メモリ ディスク
・ コンピュータのメモリのアクセス速度は、演算速度よりかなり遅い（10倍以上） ・ そのため、メモリを読み出すときは、しばらく演算をとめて待つことになる。次の命令を読むときもそう。 ・ そこで、メモリを読むときはまとめてたくさん読む ・ 読んだメモリは、CPUに直結した速いメモリにしばらく取っておく（この操作をキャッシュ、キャッシュに使うメモリをキャッシュメモリという） CPU キャッシュ メモリ メモリ ディスク

14 キャッシュによる高速化 CPU メモリ HDD ・ メモリアクセスが、キャッシュに入っている場所ばかりだと計算は大幅に速くなる
　 キャッシュの効率を高めるような保存法が重要 　 引き続いて、キャッシュの中を見ることが多い計算をさせると、高速化できる ・ ディスクのアクセスにも、同じようにキャッシュを使う 　CPU直結メモリの代わりに、通常のメモリを使う。メモリのほうがディスクよりアクセス速度が速いので、高速化できる CPU メモリ HDD

15 変数 ・ 高級言語では、数値を記憶する際に変数というものを使う ・ 変数には、何か値が１つ入る
・ コンパイルして実行するときに、各変数にメモリの場所が割当てられる。以後、変数をアクセスするときには、その場所にアクセスするようになる

16 配列 ・ 大量のデータを扱う場合、全てのデータに直接変数を割当てるのは、大変。プログラムを書くのも大変 ・ そこで、配列を使う ・ 配列を使うと、変数＋添え字、という形でデータにアクセスできる。添え字のところは変数を入れられるので、例えば、100個の変数を0にする、といった作業も、ループを使って楽にできる A[0] = 1 A[1] = 0 A[2] = 1 … １ ０

17 OS ・ コンピュータは、機種によって、入出力の方法が違う
・ ディスプレイに文字を書くためには、文字の形になるよう、データを書き込まなければいけない ・ こういった、ハードウェアによる違いを吸収する、低レベルの処理を行う、実行するプログラムの管理、などをするプログラムがある ・ これをOSという （Windows、UNIXなど） ・ 固有の接続機器を、標準的な入出力方法を用いて扱うプログラムをデバイスドライバという ・ メモリの管理もOSが行う

18 メモリの確保 ・ 普通、コンピュータでは、複数のプログラムが同時に実行されている（含デバイスドライバ）
・ そのため、メモリの適当な場所に適当に数値を書き込むと、他のプログラムの実行を阻害する（下手をすると動きが止まる） ⇒まともなOSはそのような動作を禁止している ・ そのため、メモリを使いたいときには、OSにお願いして、必要な分だけ使える場所をあてがってもらう（これをメモリを確保するという）

19 数値の表現（バイト） ・ メモリは数値を覚えられるが、実は 0 と 1 しか覚えられない　（ビットという） ・ しかし、大量に 01 の数値を記憶できる ・ 実際は、01しか記憶できないのでは用をなさないので、01の数値を8個セットにして、それを2進数とみなす。（0-255が表現できる） 　－ これを １バイトという ・ 足す引く掛けるの算術演算の結果、 2進数9桁目に繰り上がったとき、あるいはマイナスになったときは、その部分は無視して計算する １ ０ = 181

20 データの記憶 ・ メモリには、記録されている数値が整数か、文字か、といった、データの種類を覚えておく機能はないので（数値として付加的に記録することはできるが）、自分（プログラム）が何を書いたか管理する ・ つまり、「何のデータはどこに書いた」ということを決めておく。プログラムでは、データの計算をする際には、場所を決めて書く ・ 常に0か1の値が書いてあるので、「書き込まれていない」ということも検出できない 点数 20 点数 20 点数 20 １ ０

21 整数小数文字 － 整数： 01の数値をいくつかセットにして、それを2進数とみなす。通常、32ビット ＝ 4バイト。 (0-40億くらい) － 実数： 整数と小数点の位置をセットで記憶。小数点は2進数の位置で記憶。通常、整数が56ビット、小数点が8ビット（256桁分） 　　演算誤差が生じる (1/3 * 3 = …) － 文字：　文字と整数値を対応させたコード表があり、それを使って整数値として記憶する １ ０ = 181 + ０ １ (4+1)/16 =

22 負の数の表現（バイト） － 負の数： 最上位のビットが1になった数は、256を引いて、負の数とみなす。通常の数と思って計算したときと、負の数と思って計算したときの結果が同じなので、結果を変換する必要がない 例：　255 は-1 になる。1を足すと、 = 。9桁目は無視するので、0 これは、実際の の答えと一致する 例：　-2 は 254、-5 は 251。両者を足すと、505。256の剰余を求めると249。これは-7に対応。両者を掛けると 63754。剰余を求めると 10。

23 C言語では char: 符号ありバイト -128 から 127 を表す unsigned char: 符号なしバイト 0 から 255を表す
桁あふれ (overflow) に注意 符号なし: 30 * 5 = 150 符号あり: 30 * 5 = 間違い

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

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

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

27 アルゴリズムの正しさ アルゴリズムが正しい (correct) 正しくないアルゴリズム 確率的アルゴリズムも存在
⇒全ての具体例に対して正しい出力とともに停止する 与えられた計算問題を解く (solve) という． 正しくないアルゴリズム ある具体例に対して望ましい答えを出力せずに停止 ある具体例に対して全く停止しない 確率的アルゴリズムも存在 高い確率で正しい答えを出す or 早く停止する

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

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

30 Rubyの場合 def insertion_sort(a) for j in 1..(a.length-1) do key = a[j]
i = j-1 while i >= 0 && a[i] > key do a[i+1] = a[i] i = i-1 end a[i+1] = key a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0] insertion_sort(a) p a

31 Fortran 90の場合 program main do j = s+1, t key = a(j)
integer :: a(14) = (/ 27,17,3, 16,13,10,1,5,7,12,4,8,9,0 /) print *, "a = ", a print *, "insertion sort" call insertionsort(a) contains subroutine insertionsort(a) integer a(:) integer i, j, key integer s, t s = lbound(a,1); t = ubound(a,1) do j = s+1, t key = a(j) i = j-1 do if (.not. (i >= s .and. a(i) > key)) exit a(i+1) = a(i) i = i - 1 end do a(i+1) = key end subroutine insertionsort end program main

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

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

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

35 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 の値に対して実行される回数

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

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

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

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

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

41 漸近記号 -記法 ある関数 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) という表現も用いる

42

43

44 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) も正しい表現

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

46 -記法 ある関数 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))

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

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

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