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

アルゴリズムとデータ構造
2011年6月9日
担当：酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html
1
テキスト
『アルゴリズムとデータ構造』，
石畑清著(岩波書店)
参考書
『アルゴリズムとデータ構造』，
平田富夫著（森北出版）．
『アルゴリズムとデータ構造入門』，
東野勝治，臼田昭司著（森北出版）．
『ハッカーのたのしみ』，
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完全問題・近似アルゴリズム
［クォータ末試験］
（６月９日５時限）
（６月１３日５時限）
（６月１４日２時限）※
（６月１６日５時限）
（６月２０日５時限）
（６月２３日５時限）
（６月２７日５時限）
（６月２８日２時限）※
（６月３０日５時限）
（７月４日５時限）
（７月７日５時限）
（７月１１日５時限）
（７月１２日２時限）※
（７月１４日５時限）
（７月２１日５時限）
（７月２５日５時限）3
成績評価
• クオータ末試験および演習を総合的に
評価する．
• 試験や演習で持ち込めるもの
– 教科書・ノート・配布資料
• 再試験はしない．
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
連結リスト（２９ページ）
• データをそれぞれの要素に格納
• 要素どおし、つながってリストを形成
メモリ上に置かれた構造型データをアドレスで指す
先頭
データ次
データ次
データ次データ次
データ次
構造型データ
26
先頭
データ次
前
データ次
データ次
データ次
データ次
前
先頭
データ次
データ次
データ次
挿入対象
データ次
削除対象
データ次
27
例：メモリ割り当て（３７ページ）
最も簡単なメモリ割り当てアルゴリズム
・リストで管理
・データ領域を分断し、あらたなリスト要素として、挿入
・リストのヘッダには空きか使用中かのフラグがある
・割当てるデータ領域はリストのヘッダとヘッダの間
使用状況を示すフラグ
次のヘッダを指すポインタ
空き
空き使用中
ヘッダは左のような構造
要素としては、フラグとポインタしかない
空きの領域
使用中
28
空き
空き使用中
空き
空き
空き空き
使用中
メモリの割り付け・開放を繰り返していくとメモリが分断するようになる
・フラグメンテーションといい、大きな領域を割り当てできなくなる
・そこで、ときおり、空き領域にはさまれたヘッダを削除する
メモリ割付け技法
•連続割付け
•単一連続割付け
•分割割付け(ゾーン割り付け)
•固定区画割付け
•可変区画割付け
•非連続割付け
•ページング
•セグメンテーション
管理手法
•線形リスト
•ハッシュ表
29
スタック（LIFO）
プッシュ
ポップ
スタックポインタ
スタックポインタ
30
連結リスト操作（挿入）
リストを使ったスタック（push）
先頭
データ
次
データ
データ
データ
次
次
次
• データをそれぞれの要素に格納
• 要素どおし、つながってリストを形成
単純な連結リスト（線形リスト）データ挿入
31
連結リスト操作（削除）
リストを使ったスタック（pop）
先頭
データ
データ
データ
次
次
次
単純な連結リスト（線形リスト）データ削除 32
Postscript
•
•
•
•
プログラミング言語ではなくて、ページ記述言語
オペランドスタック、辞書スタックを持つ
オブジェクトはリテラル、エグゼキュータブル
A-WSでgsというコマンドで実行できる
• push/pop以外のスタック処理がある
• index
指定位置の内容をコピーしてpush
• rotate
指定位置までのスタックを配列とみて回転
• [] , {}, () スタックから配列オブジェクトを切り出せる
33
RPN（逆ポーランド記法）
普通は 1 + 2 と入力して 3 という答えを得ます
同じ答えを得るために、RPNで書くと 1 2 + となります。
普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + × となります。
ありがちなプログラミング言語では規則をもとに構文解析を行っている
演算子には優先順位がある
括弧は優先度を変える
変わった言語、変わったプロセッサというものがありまして
Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ
これらはスタックを基本的なデータ構造としている
34
(1 + 2) × (3 + 4)
RPNでは 1 2 + 3 4 +
(1 + 2) × (3 + 4) ÷(5×6 – 7×8)
RPNでは 1 2 + 3 4 + × 5 6 × 7 8 × - ÷
PostScriptでは、三角関数まで定義されている。
GS>1 2 add 3 4 add mul =
21
GS>1 2 add 3 4 add mul 5 6 mul 7 8 mul sub div =
-0.807692
GS>30 sin =
0.5
GS>45 cos =
0.707107
RPNで記述するとき、日本語で数式の動作を
読み上げることにかなり近い順序になる
35
/* 可変長引数を持つ関数 */
int printf(const char *fmt,…);
/* それの呼び出し */
printf(“%d %f \n”, int_number, dbl_number);
C言語では引数はスタックに積まれて、
関数に渡される。呼び出し側の責任で
引数を積んだり降ろしたりする。
呼ばれた関数にわかっていること
1. 呼ばれた関数のスタックフレームの大きさ
2. 関数の戻り先(呼び出し元PC)
3. 第1引数がconst char *fmtであること
つまりfmtが読める→以降の引数がわかる
呼ばれた関数の
スタックフレーム
← TOS
PC
fmt
int_number
dbl_number
呼んだ関数の
スタックフレーム
36
/* 可変長引数を持つ関数 */
int execl(const char *path, const char *arg, ...);
/* それの呼び出し */
execl(“/bin/ls”, “ls”, “-l”, “/home/sakai”, NULL);
呼ばれた関数にわかっていること
1. 呼ばれた関数のスタックフレームの大きさ
2. 関数の戻り先(呼び出し元PC)
3. 第1引数が“/bin/ls”であること
4. 第2引数が”ls”であること
5. 最後の引数は必ずNULLであること
スタックに何らかのマークをpushし、
TOSからマークまでをリストとして渡す
呼ばれた関数の
スタックフレーム
← TOS
PC
“/bin/ls”
“ls”
“-l”
“/home/sakai”
NULL
呼んだ関数の
スタックフレーム
37
% PostScriptにおける配列の切り出し
% [1 2 3 4 5 6 7 8 9 10] という配列を定義
GS>[
GS<1>1
GS<2>2
GS<3>3
GS<4>4
GS<5>5
GS<6>6
GS<7>7
GS<8>8
GS<9>9
GS<10>10
GS<11>]
GS<1>==
[1 2 3 4 5 6 7 8 9 10]
GS>
PostScriptでは、配列が定義できる。
スタック上の「マーク」と「マークまでを配列とする」
オペレータを組み合わせて使う。
このオペレータはマークまでをすべてpopし、
配列オブジェクトとしてふたたびpushする
[ オブジェクトの並び ] は通常の配列
{ オブジェクトの並び } は実行可能な配列(手続き)
(文字の並び) は文字の配列（文字列）
いずれも配列の基本的な性質は継承している
38
待ち行列（FIFO）（４４ページ）
データ挿入
データ取得
待ち行列（データの挿入・取得）
39
待ち行列の配列による実現
データ挿入
データ取得
新しい要素を入れようとすると入らない
→右へコピーして移動
→隙間を空ける
40
リングバッファ(46ページ)
配列の最初と最後を接続して環にしたもの
２つのポインタでデータの出し入れを管理
データの先頭を指すポインタ
head, front
データの最後尾を指すポインタ
tail, rear
２つのポインタが重なったらデータは空
領域の大きさをnとしたらポインタの位置はnとおり
データの数が0からnまでn+1とおりある
ポインタが重なったら、空か満杯の状態が重なる…41
リングバッファ
挿入口
リア
•環状のデータ格納領域
•データの存在を示すポインタ
取り出し口
フロント
42
リア
フロント
リア
満杯になったとき、
リアとフロントのポインタが
重なってしまって
空と区別が付かない
43
配列を使用したリングバッファ
配列には始まりと終わりがある
ポインタが終わりまで移動したら先頭へ戻る
（フロント－リア）の演算でも境界を考慮
ラップラウンド処理
ラップラウンド処理
条件文で判定
配列の大きさを2のべき乗にする
配列のインデックスをビットごとのAND処理
44
public class Queue
{
private Queue()
{
}
public Queue(int aMaxSize)
{
int realSize = aMaxSize + 1;
this.maxSize = realSize;
this.queueArray = new Object[realSize];
this.front = 0;
this.rear = 0;
•データのおき場所は配列
}
}
private
private
private
private
•front, rearというポインタで管理
•キューの容量はmaxSizeで管理
int front;
int maxSize;
Object[] queueArray;
int rear;
45
public Object dequeue()
{
if(this.isEmpty()){
System.err.println("待ち行列は空です");
return null;
}
Object dequedObject = this.queueArray[this.front];
this.queueArray[this.front] = null;
++this.front;
if(this.maxSize == this.front){
this.front = 0;
•frontの指すところがキューの先頭
}
•先頭と最後尾が同じ場合は空
return dequedObject;
}
•条件文でラップラウンド処理
public boolean isEmpty()
{
return (this.rear == this.front);
}
46
public boolean enqueue(Object aTarget)
{
if(this.isFull()){
System.err.println("待ち行列はいっぱいです");
return false;
}
this.queueArray[this.rear] = aTarget;
++this.rear;
if(this.maxSize == this.rear){
this.rear = 0;
}
•rearの指すところがキューの最後尾
return true;
•先頭と最後尾が同じ場合は空
}
•そうならないようにする判定が必須
•条件文でラップラウンド処理
public boolean isFull()
{
return ((this.rear + 1) == this.front);
}
47
public void printAll()
{
System.out.println("待ち行列の内容");
if(this.isEmpty()){
System.out.println();
•場合分けしてラップラウンド処理
return;
•frontから配列終わりまでの表示
}
int count = 1;
•配列先頭からrearまでの表示
int position = this.front;
int limit = (this.front > this.rear)? this.maxSize: this.rear;
while(position < limit){
System.out.println(count +"\t" + this.queueArray[position]);
++count;
++position;
}
position = 0;
limit = (this.front > this.rear)? this.rear: 0;
while(position < limit){
System.out.println(count +"\t" + this.queueArray[position]);
++count;
++position;
}
System.out.println();
48
}
// リストのデータ構造
// Java言語でアクセッサあり
public class Element1
{
public Element1(Object aData)
{
this.data = aData;
}
public Object getData()
{
return this.data;
}
public Element1 getNextElement()
{
return this.next;
}
public void setNextElement(Element1 anNextElement)
{
this.next = anNextElement;
}
private Object data; // 参照型
private Element1 next;
}
/* リストのデータ構造 */
/* C言語版その１ */
union Object {
int Integer;
double Double;
};
struct Element1 {
union Object data;
struct Element1 *next;
};
// リストのデータ構造
// Java言語でアクセッサなし
public class Element2
{
public Element2()
{
}
public Object data;
public Element2 next;
}
/* リストのデータ構造 */
/* C言語版その２ */
struct Element2 {
void *data;
struct Element2 *next;
49
};
// リストのデータ構造 // Java言語でアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
new_element1 = new Element1(new Integer(100));
new_element1. setNextElement(next_element1);
100
Integerのインスタンス
/* リストのデータ構造 *//* C言語版その１ */
100 */
/*
struct Element1 *next_element1: /* どこかで与えられている
new_element1
structElement1のインスタンス
Element1 *new_element1;
data
new_element1getData()
= malloc(sizeof (struct Element1));
next
data
new_element1->data.Integer
getNextElement() = 100;
new_element1->next
= next_element1;
next
setNextElement()
// リストのデータ構造 // Java言語でアクセッサなし
data
next_element1
100
//
Element2 next_element2; // どこかで与えられている
next
Element2 new_element2;
new_element2 = new Element2();
next_element1
next
new_element2.data = new Integer(100);
new_element2. next = next_element2;
Element1のインスタンス
getData()
getNextElement()
next_element1
data
/*
リストのデータ構造
*//*
C言語版その２
*/
new_element2
setNextElement()
Element2のインスタンス
/*
struct
Element2 *next_element2: /* どこかで与えられている */
data
struct Element2 *new_element2;
data
next
next
Element2のインスタンス
new_element2 =next
malloc(sizeof (struct Element2));
new_element2->data = malloc(sizeof (int));
data
*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い
*/
50
next
new_element2->next = next_element2;
next_element2
// リストのデータ構造
// Java言語でアクセッサあり
public class Element1
{
public Element1(int aData)
{
this.data = aData;
}
public int getData()
{
return this.data;
}
public Element1 getNextElement()
{
return this.next;
}
public void setNextElement(Element1 anNextElement)
{
this.next = anNextElement;
}
private int data; // 値型
private Element1 next;
}
/* リストのデータ構造 */
/* C言語版その１ */
struct Element1 {
int data;
struct Element1 *next;
};
// リストのデータ構造
// Java言語でアクセッサなし
public class Element2
{
public Element2()
{
}
public int data;
public Element2 next;
}
/* リストのデータ構造 */
/* C言語版その２ */
struct Element2 {
int *data;
struct Element2 *next;
};
51
// リストのデータ構造 // Java言語でアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
100
new_element1 = new Element1(100);
new_element1. setNextElement(next_element1);
/* リストのデータ構造 *//* C言語版その１ */
/*
struct Element1 *next_element1: /* どこかで与えられている */
new_element1
structElement1のインスタンス
Element1 *new_element1;
data
new_element1getData()
= malloc(sizeof (struct Element1));
next
data
new_element1->data.Integer
getNextElement() = 100;
new_element1->next
= next_element1;
next
setNextElement()
// リストのデータ構造 // Java言語でアクセッサなし
１００
//
Element2 next_element2; // どこかで与えられている
next
Element2 new_element2;
100
Element1のインスタンス
new_element2 = new Element2();
next_element1
next
new_element2.data = 100;
getData()
new_element2. next = next_element2;
data
getNextElement()
new_element2 /* リストのデータ構造 *//* C言語版その２ */
next
setNextElement()
Element2のインスタンス
/*
struct
Element2 *next_element2: /* どこかで与えられている */
data
struct Element2 *new_element2;
１００
next
Element2のインスタンス
new_element2 =next
malloc(sizeof (struct Element2));
new_element2->data = malloc(sizeof (int));
data
*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い
*/
52
next
new_element2->next = next_element2;
next_element2
木構造
ルートとそれ以外の
ノードにちょうど１つだけ
の経路しか存在しない
ルートノード
エッジ
ノード
末端ノード
53
まとめ
• データ構造
– 配列・リスト・スタック・待ち行列・木
• プログラムへの変換
– 参照型と値型の違い・利害得失
• メモリのイメージ
– 抽象的なデータ構造との対応
• プログラミング言語による違い
– Javaにもポインタは存在する
• ただし、ポインタ演算はない。
– Javaと異なり、Ｃの構造型は値型である
54
• Javaのほうが参照を多用するけど、表立って見えない

Download Report