担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年6月10日 担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html

テキスト 　　　『アルゴリズムとデータ構造』， 石畑清 著(岩波書店) 参考書 　　　『アルゴリズムとデータ構造』， 平田富夫 著（森北出版）． 『アルゴリズムとデータ構造入門』， 東野勝治，臼田昭司 著（森北出版）． 『ハッカーのたのしみ』， H.S.ウォーレン Ｊｒ 著，滝沢徹，鈴木貢， 赤池英夫，葛毅，藤波順久，玉井浩訳（星雲社） 『プログラミング言語Ｃ』， B.W.カーニハン，D.M.リッチー 著， 石田晴久 訳（共立出版）．

講義の予定 アルゴリズムと計算量 （６月１０日５時限） 線形探索・２分探索 （６月１７日５時限） ２分探索木 （６月１８日２時限）※ アルゴリズムと計算量 （６月１０日５時限） 線形探索・２分探索 （６月１７日５時限） ２分探索木 （６月１８日２時限）※ 平衡木・B木 （６月２０日５時限） ハッシュ法 （６月２４日５時限） シェルソート （６月２７日５時限） クイックソート （７月１日５時限） ヒープソート （７月２日２時限）※ マージソート・ビンソート （７月４日５時限） グラフの表現法・探索 （７月８日５時限） 連結性の判定 （７月１１日５時限） 最短路の問題 （７月１６日２時限）※ 文字列のアルゴリズム （７月１８日５時限） バックトラック・幅優先探索・ゲームの木の探索 （７月２２日５時限） NP完全問題・近似アルゴリズム （７月２５日５時限） ［クォータ末試験］ （７月２９日５時限）

成績評価 クオータ末試験および演習を総合的に 評価する． 試験や演習で持ち込めるもの 教科書・ノート・配布資料 再試験はしない．

本講義の位置づけ プログラムの勉強(技術的な知識) アルゴリズムとデータ構造(抽象的な知識) 計算機のしくみの勉強(低水準の知識) 計算機言語、情報学群実験１ 背景は、表現方法としてのプログラミング言語 アルゴリズムとデータ構造(抽象的な知識) 計算機システムの基礎 数学と計算法（計算機はΣや∫を知らない） 計算機のしくみの勉強(低水準の知識) 情報学群実験2 コーディング対象を知る システム設計の勉強(高水準の知識) ソフトウェア工学、オペレーティングシステム

アルゴリズム＋データ構造＝プログラム (このように書くのは簡単) アルゴリズムとデータ構造 具体化 抽象化 この間があまりにも遠いのが現実 　　　　間を埋めるもの→想像力 　　　　　　想像力を増やす→経験を積む 　　　　　　　　経験を積むには→楽しさが必要 　　　　　　　　　　楽しさって何？ 　　　　　　　　　　　　　　書いたとおり動くのが救い プログラム(Java, C,…)

プログラムとは？ アルゴリズムとデータ構造を表現したもの 計算機に仕事をさせる指示・手続き 表現方法にはいっぱいある プログラミング言語の数だけ 構造体やレコードといったデータ構造 連接や条件文や繰り返し文といった制御構造 計算機に仕事をさせる指示・手続き 計算機は指示通りに動くように作られている 動かない場合も稀にある… （教科書２ページ）

なぜ学習するか？ すばやくコーディングするため 美しいコードを書くため わかりやすいコードにするため どのように表現するか、どのように処理し目的を達成するか、を理解する

すばやくコーディングする よく知られたものを使う 全体をよく考えて、既存のものが使えるようにする 探せばどこかに実装が存在する 既存のものを使えばデバグの手間が省ける 定番と呼ばれる書籍の存在 全体をよく考えて、既存のものが使えるようにする そのために勉強する！

美しいコード 洗練されたコードは美しい コーディング規則の外側に美しさがある 適切なアルゴリズム 適切なデータ構造 人間が読み書きするものであることを肝に銘じて きちゃないコードは読む気がするか？

わかりやすいコード 構造がわかりやすい 構造がプログラミング言語の自然なデータ型や制御文に合っている プログラムの共有ができる よくしられたデータ構造 よくしられたアルゴリズム これらの再帰的な組み合わせ 構造がプログラミング言語の自然なデータ型や制御文に合っている プログラムの共有ができる 3日後の自分は他人と同じ 記憶力のいい人は1ヶ月くらいは平気？

抽象的 vs. 具体的 ptrで指される領域からvalueを線形探索 for(i = n; i; i--, ptr++) if(*ptr == value) break; mov eax,value mov edx,ptr mov ecx,n 0: cmp eax,[edx] je 1f lea edx,[edx+4] loop 0b 1:

Ｅｕｃｌｉｄの互除法（２ページ 1.1） ｍをｎで割って、余りをｒとする。 ｒ＝０であれば、アルゴリズムは終了する。 このとき、ｎが最大公約数である。 ｍ←ｎとする（ｎの値をｍに代入する）。 次にｎ←ｒとして１に戻る。 ここでは、次の処理が使われている。 除算 ０との比較・分岐処理 変数への代入 繰り返し（ループ）

/* C言語によるgcdの例1 */ int gcd(int m, int n) { int r; 1: r = m % n; if (r == 0) goto 2; m = n; n = r; goto 1; 2: return n; } /* C言語によるgcdの例2 */ int gcd(int m, int n) { int r; while((r = m % n) != 0){ m = n; n = r; } return n; /* Java とほとんど同じ */ プログラムは、連接（文の並び順による評価）・条件分岐（たとえばif文）・繰り返し（例えばwhile文）だけで構成できるとされている。そもそも、gotoを使わないで書いたほうがわかりやすいことも多い。 そのような背景で、Javaのようにgotoを使えないプログラミング言語がある。

スタックフレーム ｓｐ＋４ ｓｐ＋２ ｓｐ ; アセンブリ言語によるgcd関数の例 引数ｎ .text 　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r1 ; 引数 m mov.w @(4,sp),r0 ; 引数 n 1: divxu.b r0l,r1 xor.b r2h,r2h mov.b r1h,r2l ; r = m % n beq 2f ; if(r == 0) goto 2 mov.w r0,r1 ; m = n mov.w r2,r0 ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数ｎ 引数ｍ 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。

スタックフレーム ｓｐ＋４ ｓｐ＋２ ｓｐ ｂｓｒ直後のスタック ; アセンブリ言語によるgcd関数の例 .text 　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r0 ; m mov.w @(4,sp),r1 ; n beq 1f ; if (n == 0) divxu.b r1l,r0 mov.b r0h,r0l xor r0h,r0h ; m % n push r0 push r1 bsr gcd adds.w #2,sp 1: rts ; return m .end 戻りアドレス 引数ｎ 引数ｍ 　ｂｓｒ直後のスタック ｓｐ＋１０ 　ｓｐ＋８ 　ｓｐ＋６ 　ｓｐ＋４ 　ｓｐ＋２ 　　　　ｓｐ 戻りアドレス 引数ｎ 引数ｍ 戻りアドレス 引数ｎ 引数ｍ レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

アルゴリズム アルゴリズムは必ず問題を解決するもの ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 いつかは停止しないといけない ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 ループ不変条件 繰り返し開始直前にこの条件が成立。 この条件が成立しているときに、 繰り返しを１回すすめると、再びこの条件が成立。

計算量の概念（7ページ 1.2節） アルゴリズムの性能を示す指標 大きな問題が少ない計算量で解ければ優秀 時間計算量 計算量の概念（7ページ　1.2節） アルゴリズムの性能を示す指標 時間計算量 (文字通り)計算に要する時間 最悪時間計算量・平均時間計算量 空間計算量（領域計算量） どれくらいの作業領域を必要とするかを表す 大きな問題が少ない計算量で解ければ優秀 漸近的に表現したものがO記法 計算量を定式化したとき、計算量に最も大きな影響を及ぼす項をとりだしたもの。

O記法 漸近的な振る舞いを表す 項の形で大きく２つに分けられる（問題:n） 定数項は無視 係数は１ 一般には最も影響力の強い項のみで表す 指数関数　　 kn

10 O(n) O(n log n) 25 10 10 100 O(n2) 2500 O(en) 10 10

基本的データ構造 スカラ ベクトル グラフ 集合 基本型として限定的に記述可能 １次元の配列として表現可能なことがある 実は、普通の計算機では演算できない グラフ 実は、普通の計算機では簡単に表現できない 集合 もちろん、集合演算はできない

メモリと配列 計算機のメモリは一種の１次元配列である プログラミング言語による多彩なデータ構造 プロセッサが扱える最小単位を要素としている 普通の計算機ではbyteを最小の単位としている 有限の大きさを持つ ただし、仮想記憶管理機構により伸長できる場合もある 配列のインデックスに相当するものがアドレス メモリへのアクセスはアドレッシングと呼ばれる 普通の計算機では、プロセスにはこの配列が1個 プログラミング言語による多彩なデータ構造 プログラミング言語のコンパイラが変換します 実はほとんどの型はbyteの配列になっている

配列（２７ページ） 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 添え字が１から始まるとは限らない 1 2 3 4 n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする（例では３）

二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて ・・・・・・・・・・・・ １　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ １　 ２　　３　　４　 ・・・・　 ｎ ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・

三次元配列 １ ２ ３ ・・・・ ｍ １ ２ ３ ・・・ ｎ ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ １ ２ ３ ・・・ ｋ １　２　３ ・・・ ｎ １ ２ ３ ・・・ ｋ １　　　 ２　　　 ３ ・・・・　　ｍ （３，１，１） 添え字を 用いて データに アクセス

値型と参照型 値型 参照型 値が定義したところに存在する 値が別に存在し、それへの参照が定義される JavaやＣ言語の基本型の変数 Ｃ言語では構造型変数(構造体)も値型 参照型 値が別に存在し、それへの参照が定義される Javaのオブジェクトはすべて参照型 newで得られる値は、実体への参照 Ｃ言語では参照型を明示的に定義できる これがいわゆるポインタで、参照する演算子が単項の＊ 値型の参照を得る演算子が単項の＆ Ｃ言語の関数や配列は参照型 名前はそれへの参照を表す

データ型 基本型, primitive type 構造型, structured type byte, word, dword, qword, tbyte void, char, int, float, double boolean, byte, int, double 構造型, structured type section(?) struct, union class

「配列オブジェクト」と「オブジェクトの配列」は違う オブジェクトと配列 Object certainObject = new Object(); // オブジェクト生成 int[] intarray = new int[100]; // 基本型intの配列の定義 Object[] objects = new Object[100]; // 配列オブジェクトの定義 objects[i-1] = new Object(); // オブジェクトを定義→配列要素 objects[i-1].method_name(arguments,…); // メソッド 「配列オブジェクト」と「オブジェクトの配列」は違う

オブジェクトと参照 1. オブジェクト変数の宣言 オブジェクト変数 メモリ領域 オブジェクト変数 オブジェクト 参照情報 メモリ領域 2. オブジェクトの生成（new） オブジェクト領域 3. オブジェクトの初期化 オブジェクト変数 オブジェクト 参照情報 メモリ領域 オブジェクト領域 初期化

この段階ではオブジェクトの配列ができてない 配列オブジェクト 配列要素となるオブジェクトの定義 配列オブジェクトの宣言 メモリ領域 配列オブジェクト変数 オブジェクト領域 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 この段階ではオブジェクトの配列ができてない

Javaにおける多次元配列 Javaにおける多次元配列は、 配列オブジェクトの配列である // 2次元配列 Object[][] array2D = new Object[3][2]; // 3次元配列 Object[][][] array3D = new Object[4][3][2]; // 1次元配列の配列として表される Object[][] array2D = new Object[3][]; array2D[0] = new Object[2]; array2D[1] = new Object[2]; array2D[2] = new Object[2]; // 2次元配列の配列として表される Object[][][] array3D = new Object[4][][]; array3D[0] = new Object[3][2]; array3D[1] = new Object[3][2]; array3D[2] = new Object[3][2]; array3D[3] = new Object[3][2]; Javaにおける多次元配列は、 配列オブジェクトの配列である /* 参考: 1次元配列の配列としてC言語で定義(Javaの2次元配列に近い) */ Object *array2D[3] ; array2D[0] = malloc(2*sizeof(Object)); array2D[1] = malloc(2*sizeof(Object)); array2D[2] = malloc(2*sizeof(Object)); /* 参考: C言語での2次元配列の定義(Javaと全く違う!) */ Object array2D[3][2] ;

2次元配列 メモリ領域 配列オブジェクト変数 配列オブジェクト達… オブジェクト 参照情報 オブジェクト 参照情報 オブジェクト 参照情報

シンタックスシュガー 本来必要ではないがコーディングの効率化のために設けられている特別な文法 array[1][3]; ((Object[])(array[1]))[3]; String[] string = new String[]{“a”, “b”, “c”}; String[] string = new String[3]; string[0] = “a”; string[1] = “b”; string[2] = “c”;

Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える 配列オブジェクト 配列オブジェクト変数 length: 配列の大きさ 配列本体へのポインタ Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える NullPointerExceptionでも存在がわかる 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列オブジェクト変数 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列本体へのポインタ 配列本体 [メモリ上の領域]

(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1 Cの配列 行と列それぞれをインデックスで指し示す Ｃコンパイラはそれをオフセットに変換する １　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ 配列名 １　 ２　　３　　４　 ・・・・　 ｎ 1 2 ・・・・・・・ m-1 m m+1 m+2 ・・・・・・・ 2*m-1 （３，２） 添え字を 用いて データに アクセス 2*m 2*m+1 ・・・・・・・・・・・・ 3*m ・・・・・ n*m-1 (n-1)*m (n-1)*m+1 ・・・・・・・・・・・・・・・・ (n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1