Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "担当:酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年6月10日 担当:酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html."— Presentation transcript:

1 担当:酒居敬一@A468(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2013年6月10日

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

3 講義の予定 アルゴリズムと計算量 (6月10日5時限) 線形探索・2分探索 (6月17日5時限) 2分探索木 (6月18日2時限)※
アルゴリズムと計算量 (6月10日5時限) 線形探索・2分探索 (6月17日5時限) 2分探索木 (6月18日2時限)※ 平衡木・B木 (6月20日5時限) ハッシュ法 (6月24日5時限) シェルソート (6月27日5時限) クイックソート (7月1日5時限) ヒープソート (7月2日2時限)※ マージソート・ビンソート (7月4日5時限) グラフの表現法・探索 (7月8日5時限) 連結性の判定 (7月11日5時限) 最短路の問題 (7月16日2時限)※ 文字列のアルゴリズム (7月18日5時限) バックトラック・幅優先探索・ゲームの木の探索 (7月22日5時限) NP完全問題・近似アルゴリズム (7月25日5時限) [クォータ末試験] (7月29日5時限)

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

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

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

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

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

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

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

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

12 抽象的 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:

13 Euclidの互除法(2ページ 1.1) mをnで割って、余りをrとする。
r=0であれば、アルゴリズムは終了する。 このとき、nが最大公約数である。 m←nとする(nの値をmに代入する)。 次にn←rとして1に戻る。 ここでは、次の処理が使われている。 除算 0との比較・分岐処理 変数への代入 繰り返し(ループ)

14 /* 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を使えないプログラミング言語がある。

15 スタックフレーム sp+4 sp+2 sp ; アセンブリ言語によるgcd関数の例 引数n .text
 スタックフレーム sp+4 sp+2    sp ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; 引数 m mov.w @(4,sp),r ; 引数 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,r ; m = n mov.w r2,r ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数n 引数m 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、C言語では例のように、さりげなく使われている。

16 スタックフレーム sp+4 sp+2 sp bsr直後のスタック ; アセンブリ言語によるgcd関数の例 .text
 スタックフレーム sp+4 sp+2    sp ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; m mov.w @(4,sp),r ; 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 戻りアドレス 引数n 引数m  bsr直後のスタック sp+10  sp+8  sp+6  sp+4  sp+2     sp 戻りアドレス 引数n 引数m 戻りアドレス 引数n 引数m レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

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

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

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

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

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

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

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

24 二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ (3,2) 添え字を 用いて ・・・・・・・・・・・・
1      2      3     ・・・     m 1  2  3  4  ・・・・  n ・・・・・・・ ・・・・・・・ (3,2) 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・

25 三次元配列 1 2 3 ・・・・ m 1 2 3 ・・・ n ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ 1 2 3 ・・・ k
1 2 3 ・・・ n 1 2 3 ・・・ k 1    2    3 ・・・・  m (3,1,1) 添え字を 用いて データに アクセス

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

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

28 「配列オブジェクト」と「オブジェクトの配列」は違う
オブジェクトと配列 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,…); // メソッド 「配列オブジェクト」と「オブジェクトの配列」は違う

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

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

31 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] ;

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

33 シンタックスシュガー 本来必要ではないがコーディングの効率化のために設けられている特別な文法 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”;

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

35 (n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1
Cの配列 行と列それぞれをインデックスで指し示す Cコンパイラはそれをオフセットに変換する 1      2      3     ・・・     m 配列名 1  2  3  4  ・・・・  n 1 2 ・・・・・・・ m-1 m m+1 m+2 ・・・・・・・ 2*m-1 (3,2) 添え字を 用いて データに アクセス 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


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

Similar presentations


Ads by Google