アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2013年6月10日
担当：酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html
テキスト
『アルゴリズムとデータ構造』，
石畑清著(岩波書店)
参考書
『アルゴリズムとデータ構造』，
平田富夫著（森北出版）．
『アルゴリズムとデータ構造入門』，
東野勝治，臼田昭司著（森北出版）．
『ハッカーのたのしみ』，
H.S.ウォーレンＪｒ著，滝沢徹，鈴木貢，
赤池英夫，葛毅，藤波順久，玉井浩訳（星雲社）
『プログラミング言語Ｃ』，
B.W.カーニハン，D.M.リッチー著，
2
石田晴久訳（共立出版）．
講義の予定
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
アルゴリズムと計算量
線形探索・２分探索
２分探索木
平衡木・B木
ハッシュ法
シェルソート
クイックソート
ヒープソート
マージソート・ビンソート
グラフの表現法・探索
連結性の判定
最短路の問題
文字列のアルゴリズム
バックトラック・幅優先探索・ゲームの木の探索
NP完全問題・近似アルゴリズム
［クォータ末試験］
（６月１０日５時限）
（６月１７日５時限）
（６月１８日２時限）※
（６月２０日５時限）
（６月２４日５時限）
（６月２７日５時限）
（７月１日５時限）
（７月２日２時限）※
（７月４日５時限）
（７月８日５時限）
（７月１１日５時限）
（７月１６日２時限）※
（７月１８日５時限）
（７月２２日５時限）
（７月２５日５時限）
（７月２９日５時限）
成績評価
• クオータ末試験および演習を総合的に
評価する．
• 試験や演習で持ち込めるもの
– 教科書・ノート・配布資料
• 再試験はしない．
4
本講義の位置づけ
1. プログラムの勉強(技術的な知識)
 計算機言語、情報学群実験１
 背景は、表現方法としてのプログラミング言語
2. アルゴリズムとデータ構造(抽象的な知識)
 計算機システムの基礎
 数学と計算法（計算機はΣや∫を知らない）
3. 計算機のしくみの勉強(低水準の知識)
 情報学群実験2
 コーディング対象を知る
4. システム設計の勉強(高水準の知識)
 ソフトウェア工学、オペレーティングシステム
5
アルゴリズム＋データ構造＝プログラム
(このように書くのは簡単)
アルゴリズムとデータ構造
この間があまりにも遠いのが現実
具体化
間を埋めるもの→想像力
想像力を増やす→経験を積む
経験を積むには→楽しさが必要
楽しさって何？
抽象化
書いたとおり動くのが救い
プログラム(Java, C,…)
6
プログラムとは？
• アルゴリズムとデータ構造を表現したもの
– 表現方法にはいっぱいある
• プログラミング言語の数だけ
– 構造体やレコードといったデータ構造
– 連接や条件文や繰り返し文といった制御構造
• 計算機に仕事をさせる指示・手続き
– 計算機は指示通りに動くように作られている
• 動かない場合も稀にある…
7
（教科書２ページ）
なぜ学習するか？
• すばやくコーディングするため
• 美しいコードを書くため
• わかりやすいコードにするため
• どのように表現するか、どのように処理し
目的を達成するか、を理解する
8
すばやくコーディングする
• よく知られたものを使う
– 探せばどこかに実装が存在する
– 既存のものを使えばデバグの手間が省ける
– 定番と呼ばれる書籍の存在
• 全体をよく考えて、既存のものが使えるよ
うにする
– そのために勉強する！
9
美しいコード
• 洗練されたコードは美しい
– 適切なアルゴリズム
– 適切なデータ構造
• コーディング規則の外側に美しさがある
– 人間が読み書きするものであることを肝に銘じて
– きちゃないコードは読む気がするか？
10
わかりやすいコード
• 構造がわかりやすい
– よくしられたデータ構造
– よくしられたアルゴリズム
– これらの再帰的な組み合わせ
• 構造がプログラミング言語の自然なデータ
型や制御文に合っている
• プログラムの共有ができる
– 3日後の自分は他人と同じ
• 記憶力のいい人は1ヶ月くらいは平気？
11
抽象的 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:
12
Ｅｕｃｌｉｄの互除法（２ページ 1.1）
1. ｍをｎで割って、余りをｒとする。
2. ｒ＝０であれば、アルゴリズムは終了する。
このとき、ｎが最大公約数である。
3. ｍ←ｎとする（ｎの値をｍに代入する）。
次にｎ←ｒとして１に戻る。
ここでは、次の処理が使われている。
•除算
•０との比較・分岐処理
•変数への代入
•繰り返し（ループ）
13
/* 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を使えないプログラミング言
語がある。
14
スタックフレーム
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w
@(2,sp),r1
mov.w
@(4,sp),r0
1:
divxu.b r0l,r1
xor.b
r2h,r2h
mov.b
r1h,r2l
beq
2f
mov.w
r0,r1
mov.w
r2,r0
bra
1b
2:
rts
.end
ｓｐ＋４
; 引数 m
; 引数 n
;
;
;
;
;
;
ｓｐ＋２
ｓｐ
引数ｎ
引数ｍ
戻りアドレス
r = m % n
if(r == 0) goto 2
m = n
n = r
goto 1
return n
簡単なアルゴリズムであればアセンブリ言語でも記述できる。
ただし、アルゴリズムが必要とする処理をプロセッサが知っ
ていれば…
ちなみに、スタックというデータ構造は、Ｃ言語では例のよう
に、さりげなく使われている。
15
; アセンブリ言語によるgcd関数の例
.text
gcd:
mov.w @(2,sp),r0
mov.w
@(4,sp),r1
beq
1f
divxu.b r1l,r0
mov.b
r0h,r0l
xor
r0h,r0h
push
r0
push
r1
bsr
gcd
adds.w #2,sp
adds.w #2,sp
1:
rts
.end
スタックフレーム
ｓｐ＋４
; m
; n
; if (n == 0)
ｓｐ＋２
ｓｐ
引数ｎ
引数ｍ
戻りアドレス
; m % n
ｂｓｒ直後のスタック
; return m
レジスタ変数r2(変数r)が、不要になっ
ている。
再帰呼び出しでは、引数は新しい領域
に確保される。新しい領域としては、ス
タックが使われる。
ｓｐ＋１０
引数ｎ
ｓｐ＋８
引数ｍ
ｓｐ＋６
戻りアドレス
ｓｐ＋４
引数ｎ
ｓｐ＋２
引数ｍ
ｓｐ
戻りアドレス
16
アルゴリズム
• アルゴリズムは必ず問題を解決するもの
– いつかは停止しないといけない
• ひとつまたは複数のデータを操作し目的の
結果を得るための一連の処理手順
– ループ不変条件
• 繰り返し開始直前にこの条件が成立。
• この条件が成立しているときに、
繰り返しを１回すすめると、再びこの条件が成立。
17
計算量の概念（7ページ
1.2節）
• アルゴリズムの性能を示す指標
– 時間計算量
• (文字通り)計算に要する時間
– 最悪時間計算量・平均時間計算量
– 空間計算量（領域計算量）
• どれくらいの作業領域を必要とするかを表す
• 大きな問題が少ない計算量で解ければ優秀
– 漸近的に表現したものがO記法
• 計算量を定式化したとき、計算量に最も大きな影響
を及ぼす項をとりだしたもの。
18
O記法
• 漸近的な振る舞いを表す
– 定数項は無視
– 係数は１
– 一般には最も影響力の強い項のみで表す
• 項の形で大きく２つに分けられる（問題:n）
– 多項式
– 指数関数
ｋ
n
n
k
19
10
25
O(n)
O(n log n)
10
100
10
2500
O(e )
n
2
O(n )
20
10
10
基本的データ構造
• スカラ
– 基本型として限定的に記述可能
• ベクトル
– １次元の配列として表現可能なことがある
– 実は、普通の計算機では演算できない
• グラフ
– 実は、普通の計算機では簡単に表現できない
• 集合
– 実は、普通の計算機では簡単に表現できない
21
– もちろん、集合演算はできない
メモリと配列
• 計算機のメモリは一種の１次元配列である
– プロセッサが扱える最小単位を要素としている
• 普通の計算機ではbyteを最小の単位としている
– 有限の大きさを持つ
• ただし、仮想記憶管理機構により伸長できる場合もある
– 配列のインデックスに相当するものがアドレス
• メモリへのアクセスはアドレッシングと呼ばれる
– 普通の計算機では、プロセスにはこの配列が1個
• プログラミング言語による多彩なデータ構造
• プログラミング言語のコンパイラが変換します
• 実はほとんどの型はbyteの配列になっている
22
配列（２７ページ）
• 添え字とデータが1対1で対応
• 添え字は連続
1
2
– 添え字が１から始まるとは限らない
3
• データの挿入や削除は面倒
4
…
…
添え字を用いてアクセスする（例では３）
n
23
二次元配列
• 行と列それぞれをインデックスで指し示す
１
２
１
（３，２）
添え字を
用いて
データに
アクセス
ｎ
ｍ
・・・・・・・
３
・
・
・
・
・・・
・・・・・・・
２
４
３
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・・・・・・・・・・・・・・・
24
三次元配列
１
２
３
・・・・
・・・・・
・
・
・
・
・
・
・
・
・
・・・・・・・・・
１
２
３
・
・
・
ｋ
・
・
・
・
・
・
・
・
・
ｍ
・
・
・
・
・
・
・
・
・
（３，１，１）
添え字を
用いて
データに
アクセス
25
値型と参照型
• 値型
– 値が定義したところに存在する
• JavaやＣ言語の基本型の変数
• Ｃ言語では構造型変数(構造体)も値型
• 参照型
– 値が別に存在し、それへの参照が定義される
• Javaのオブジェクトはすべて参照型
– newで得られる値は、実体への参照
• Ｃ言語では参照型を明示的に定義できる
– これがいわゆるポインタで、参照する演算子が単項の＊
– 値型の参照を得る演算子が単項の＆
• Ｃ言語の関数や配列は参照型
– 名前はそれへの参照を表す
26
データ型
• 基本型, primitive type
– byte, word, dword, qword, tbyte
– void, char, int, float, double
– boolean, byte, int, double
• 構造型, structured type
– section(?)
– struct, union
– class
27
オブジェクトと配列
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,…);
// メソッド
「配列オブジェクト」と「オブジェクトの配列」は違う
28
オブジェクトと参照
1. オブジェクト変数の宣言
オブジェクト変数
2. オブジェクトの生成（new）
オブジェクト変数
オブジェクト
参照情報
3. オブジェクトの初期化
オブジェクト変数
オブジェクト
参照情報
メモリ領域
メモリ領域
オブジェクト領域
メモリ領域
オブジェクト領域
初期化
29
配列オブジェクト
配列オブジェクトの宣言
配列要素となるオブジェクトの定義
メモリ領域
配列オブジェクト変数
オブジェクト領域
オブジェクト
初期化
参照情報
オブジェクト
参照情報
オブジェクト
参照情報
オブジェクト
参照情報
初期化
初期化
初期化
この段階ではオブジェクトの配列ができてない
30
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] ;
31
2次元配列
メモリ領域
配列オブジェクト変数
オブジェクト
参照情報
配列オブジェクト達…
オブジェクト
参照情報
オブジェクト
参照情報
オブジェクト
参照情報
32
シンタックスシュガー
• 本来必要ではないがコーディングの効率
化のために設けられている特別な文法
array[1][3];
String[] string = new String[]{“a”, “b”, “c”};
((Object[])(array[1]))[3];
String[] string = new String[3];
string[0] = “a”;
string[1] = “b”;
string[2] = “c”;
33
配列オブジェクト変数
Javaの配列
length: 配列の大きさ
• Javaにはポインタが陽に説明されていない…
配列本体へのポインタ
– 「～への参照」という形でポインタの存在が見える
– NullPointerExceptionでも存在がわかる
配列オブジェクト
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
length: 配列の大きさ
length: 配列の大きさ
配列本体へのポインタ
length: 配列の大きさ
配列本体へのポインタ
length: 配列の大きさ
配列オブジェクト
配列本体へのポインタ
配列本体へのポインタ
配列オブジェクト
配列オブジェクト
配列本体
[メモリ上の領域]
配列本体
[メモリ上の領域]
配列本体34
[メモリ上の領域]
配列本体
Cの配列
• 行と列それぞれをインデックスで指し示す
• Ｃコンパイラはそれをオフセットに変換する
１
配列名
１
（３，２）
添え字を
用いて
データに
アクセス
２
３
４
・
・
・
・
ｎ
２
３
・・・
ｍ
0
1
2
・・・・・・・
m-1
m
m+1
m+2
・・・・・・・
2*m-1
2*m
2*m+1
3*m
・
・
・
・
・
(n-1)*m
(n-1)*m+1
・・・・・・・・・・・・・・・・
・
・
・
・
・
・
・
・
・
・
・
・
n*m-1
(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1 35

Download Report