2012 2012 年 年 6 6 月 月 7 7 日 日

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

2012 2012 年 年 6 6 月 月 7 7 日 日

担当：酒居敬一＠Ａ４６８ 担当：酒居敬一＠Ａ４６８

( ( sakai.keiichi@kochi-tech.ac.jp sakai.keiichi@kochi-tech.ac.jp ) )

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/ 2012/ 2012/ index.html index.html

1

 テキスト

　　　『アルゴリズムとデータ構造』，

石畑清 著 ( 岩波書店 )

 参考書

　　　『アルゴリズムとデータ構造』，

平田富夫 著（森北出版）．

『アルゴリズムとデータ構造入門』，

東野勝治，臼田昭司 著（森北出版）．

『ハッカーのたのしみ』，

H.S.

赤池英夫，葛毅，藤波順久，玉井浩訳（星雲社）

『プログラミング言語Ｃ』，

B.W.

D.M.

講義計画

1.

2.

3.

4.

B

5.

6.

7.

8.

9.

10.

11.

12.

※

13.

14.

15. NP

16.

成績評価

• クオータ末試験および演習を総合的に 評価する．

• 試験や演習で持ち込めるもの

–

• 再試験はしない．

本講義の位置づけ

1. プログラムの勉強 ( 技術的な知識 )





2. アルゴリズムとデータ構造 ( 抽象的な知識 )





Σ

3. 計算機のしくみの勉強 ( 低水準の知識 )



2



4. システム設計の勉強 ( 高水準の知識 )



アルゴリズム＋データ構造＝プログ

(

ラム )

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

プログラム (Java, C, )

抽象化 具体化

この間があまりにも遠いのが現実 　　　　間を埋めるもの→想像力

　　　　　　想像力を増やす→経験を積む

　　　　　　　　経験を積むには→楽しさが必要 　　　　　　楽しさって何？

　　　　　　書いたとおり動くのが救い

プログラムとは？

• アルゴリズムとデータ構造を表現したも の

–

•

–

–

• 計算機に仕事をさせる指示・手続き

–

•

（教科書２ページ）

7

なぜ学習するか？

• すばやくコーディングするため

• 美しいコードを書くため

• わかりやすいコードにするため

• どのように表現するか、どのように処

理し目的を達成するか、を理解する

すばやくコーディングす る

• よく知られたものを使う

–

–

–

• 全体をよく考えて、既存のものが使え るようにする

–

美しいコード

• 洗練されたコードは美しい

–

–

• コーディング規則の外側に美しさがある

–

–

わかりやすいコード

• 構造がわかりやすい

–

–

–

• 構造がプログラミング言語の自然な データ型や制御文に合っている

• プログラムの共有ができる

– 3

•

1

抽象的 vs. 具体的

• ptr で指される領域から value を線形探索

• for(i = n; i; i--, ptr++)

if(*ptr == value) break;

• moveax,value movedx,ptr

movecx,n

0: cmpeax,[edx]

je 1f

lea edx,[edx+4]

loop0b

Ｅｕｃｌｉｄの互除法 ^（２

ページ 1.1 ）

1. ｍをｎで割って、余りをｒとする。

2.

このとき、ｎが最大公約数である。

3. ｍ←ｎとする（ｎの値をｍに代入する）。

次にｎ←ｒとして１に戻る。

ここでは、次の処理が使われている。

•除算 •０との比較・分岐処理

•変数への代入

•繰り返し（ループ）

/* 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

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

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 adds.w #2,sp

1: rts ; return m .end

戻りアドレ ス

引数ｎ 引数ｍ

　スタックフレーム ｓｐ＋４

ｓｐ＋２ 　　　ｓｐ

レジスタ変数

r2(

r)

再帰呼び出しでは、引数は新しい領 域に確保される。新しい領域として は、スタックが使われる。

　ｂｓｒ直後のス タック

ｓｐ＋１０ 　ｓｐ＋８ 　ｓｐ＋６ 　ｓｐ＋４ 　ｓｐ＋２ 　　　　ｓｐ

戻りアドレ ス

引数ｎ 引数ｍ

戻りアドレ ス

引数ｎ 引数ｍ

アルゴリズム

• アルゴリズムは必ず問題を解決するもの

–

• ひとつまたは複数のデータを操作し目的 の結果を得るための一連の処理手順

–

•

•

繰り返しを１回すすめると、再びこの条件が成立

。

計算量の概念 ^{（ 7 ページ　 1.2}

節）

• アルゴリズムの性能を示す指標

–

• (

)

–

–

•

• 大きな問題が少ない計算量で解ければ優秀

–

O

•

O 記法

• 漸近的な振る舞いを表す

–

–

–

• 項の形で大きく２つに分けられる（問 題 : n ）

–

n

–

k

O( n ) O( n log n )

O( n ² ) O(e ⁿ )

2500 100

25 10

10 10

基本的データ構造

• スカラ

–

• ベクトル

–

–

• グラフ

–

• 集合

–

–

メモリと配列

• 計算機のメモリは一種の１次元配列である

–

•

byte

–

•

–

•

–

1

• プログラミング言語による多彩なデータ構造

•

1 2 3 4

n

… …

配列（２７ページ）

• 添え字とデータが 1 対 1 で対応

• 添え字は連続

–

• データの挿入や削除は面倒

添え字を用いてアクセスする（例では３）

１　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ １

２ 　 　 ３ 　 　 ４ 　

・

・ ・

・ 　

・

・

・

・・

・

・・

・

・・

・

・

・

・・

・ ・・・・・・・・・・・・・・・・

・・・・・・・

・・・・・・・

二次元配列

• 行と列それぞれをインデックスで指し 示す

（３，２）

添え字を用いて データにアクセス

24

・・・・・・・・・

・・・・・

・ ・

・ ・

・ ・

・ ・

・ ・

・

・

・

・

・・

・

・

・

・

・

・

・

・・

・

・

・

・

・

・

・

・・

・

・

・

　 １ 　 ２

３

・ ・

・ ｎ

１

２

３

・

・

・

ｋ

１　　　 ２　　　 ３ ・・・・　　ｍ

三次元配列

（３，１，１）

添え字を用いて データにアクセス

25

連結リスト（２９ペー ジ）

• データをそれぞれの要素に格納

• 要素どおし、つながってリストを形成

先頭 データ 次 データ 次 データ 次 次

データ データ 次

メモリ上に置かれた構造型データをアドレスで指す

先頭

次

データ データ 次 データ 次 データ 次 データ 次 次

データ データ 次

次 データ

次 データ

次 データ

先頭 前

前 挿入対象

削除対象

例：メモリ割り当て ^（３７

ページ）

空きの領域 最も簡単なメモリ割り当てアルゴリズム

・リストで管理

・データ領域を分断し、あらたなリスト要素として、挿入

・リストのヘッダには空きか使用中かのフラグがある

・割当てるデータ領域はリストのヘッダとヘッダの間

使用中 空き使用中

空き

使用状況を示すフラグ 次のヘッダを指すポインタ

ヘッダは左のような構造

要素としては、フラグとポインタしかない

メモリの割り付け・開放を繰り返していくとメモリが分断するようになる

・フラグメンテーションといい、大きな領域を割り当てできなくなる

・そこで、ときおり、空き領域にはさまれたヘッダを削除する

使用中 空き

空き 空き 空き 空き 空き

メモリ割付け技法

•連続割付け

•単一連続割付け

•分割割付け (

)

•固定区画割付け

•可変区画割付け

•非連続割付け

•ページング

•セグメンテーション

•線形リスト

•ハッシュ表

スタック（ LIFO ）

スタックポインタ

ポップ プッシュ

スタックポインタ スタックポインタ

連結リスト操作（挿入）

リストを使ったスタック

（ push ）

単純な連結リスト（線形リスト）データ挿入

先頭 次 次 次

データ データ データ

次

データ

•

•

31

先頭 次 次 次 データ データ データ

連結リスト操作（削除）

リストを使ったスタック

（ pop ）

Postscript

•

•

•

• A-WS

gs

• push/pop

• index

push

• rotate

• [] , {}, ()

RPN （逆ポーランド記 法）

普通は

1 + 2

3

同じ答えを得るために、

RPN

1 2 +

普通の書き方の

(1 + 2) × (3 + 4)

RPN

1 2 + 3 4 + ×

ありがちなプログラミング言語では規則をもとに構文解析を行っている 演算子には優先順位がある

括弧は優先度を変える

変わった言語、変わったプロセッサというものがありまして

Forth, PostScript

x87

これらはスタックを基本的なデータ構造としている

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 (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

RPN

/*

*/

int printf(const char *fmt, … );

/*

*/

printf(“%d %f \n ” , int_number, dbl_number);

C

関数に渡される。呼び出し側の責任で

引数を積んだり降ろしたりする。 呼ばれた関数の スタックフレーム

PC fmt

dbl_number int_number

呼んだ関数の

← TOS

呼ばれた関数にわかっていること

1.

2.

(

PC)

3.

1

const char *fmt

fmt

/*

*/

int execl(const char *path, const char *arg, ...);

/*

*/

execl( “ /bin/ls ” , “ ls ” , “ -l ” , “ /home/sakai ” , NULL);

呼ばれた関数の スタックフレーム

PC

“ /bin/ls ”

“ -l ”

“ ls ”

呼んだ関数の スタックフレーム

← TOS

呼ばれた関数にわかっていること

1.

2.

(

PC)

3.

1

^“ /bin/ls ”

4.

2

ls ”

5.

NULL

NULL

“ /home/sakai ”

スタックに何らかのマークを

push

TOS

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

[

]

{

}

(

)

(

)

待ち行列（ FIFO ） ^（４４

ページ）

待ち行列（データの挿入・取得）

データ挿入 データ取得

39

待ち行列の配列による実 現

データ挿入 データ取得

新しい要素を入れようとすると入らない

→ 右へコピーして移動

→ 隙間を空ける

リングバッファ ⁽⁴⁶

⁾

 配列の最初と最後を接続して環にしたもの

 ２つのポインタでデータの出し入れを管理



 head, front



 tail, rear



 領域の大きさを n としたらポインタの位置は n とお り

 データの数が 0 から n まで n+1 とおりある

 ポインタが重なったら、空か満杯の状態が重なる…

リングバッファ

取り出し口

•

•

フロント

リア リア

満杯になったとき、

リアとフロントのポインタが 重なってしまって

空と区別が付かない

配列を使用したリングバッ ファ

 配列には始まりと終わりがある







 ラップラウンド処理





2



AND

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 int front;

private int maxSize;

private Object[] queueArray;

private int rear;

}

•データのおき場所は配列

•front, rear

•キューの容量は maxSize

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;

}

return dequedObject;

}

public boolean isEmpty() {

return (this.rear == this.front);

}

•front

•先頭と最後尾が同じ場合は空

•条件文でラップラウンド処理

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;

}

return true;

}

public boolean isFull() {

return ((this.rear + 1) == this.front);

}

•rear

•先頭と最後尾が同じ場合は空

•そうならないようにする判定が必須

•条件文でラップラウンド処理

public void printAll() {

System.out.println("

");

if(this.isEmpty()){

System.out.println();

return;

}

int count = 1;

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;

}

•場合分けしてラップラウンド処理

•front

•配列先頭から rear

// リストのデータ構造

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

}; ⁴⁹

// リストのデータ構造 // Java 言語でアクセッサあり

// Element1 next_element1; // どこかで与えられている Element1 new_element1;

new_element1 = new Element1(new Integer(100));

new_element1. setNextElement(next_element1);

/* リストのデータ構造 *//* C 言語版その１ */

/* struct Element1 *next_element1: /* どこかで与えられている　 */

struct Element1 *new_element1;

new_element1 = malloc(sizeof (struct Element1));

new_element1->data.Integer = 100;

new_element1->next = next_element1;

/* リストのデータ構造 *//* C 言語版その２ */

/* struct Element2 *next_element2: /* どこかで与えられている　*/

struct Element2 *new_element2;

new_element2 = malloc(sizeof (struct Element2));

new_element2->data = malloc(sizeof (int));

*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い // リストのデータ構造 // Java 言語でアクセッサなし

// Element2 next_element2; // どこかで与えられている Element2 new_element2;

new_element2 = new Element2();

new_element2.data = new Integer(100);

new_element2. next = next_element2;

Element1

getData() getNextElement() setNextElement()

data next

Element2

data next

Integer

100

Element1

getData() getNextElement() setNextElement()

data next new_element1

next_element1

new_element2

Element2

data 100

data next next_element1

next 100

next_element1

next data data

next

// リストのデータ構造

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

};

// リストのデータ構造 // Java 言語でアクセッサあり

// Element1 next_element1; // どこかで与えられている Element1 new_element1;

new_element1 = new Element1(100);

new_element1. setNextElement(next_element1);

/* リストのデータ構造 *//* C 言語版その１ */

/* struct Element1 *next_element1: /* どこかで与えられている　 */

struct Element1 *new_element1;

new_element1 = malloc(sizeof (struct Element1));

new_element1->data.Integer = 100;

new_element1->next = next_element1;

/* リストのデータ構造 *//* C 言語版その２ */

/* struct Element2 *next_element2: /* どこかで与えられている　*/

struct Element2 *new_element2;

new_element2 = malloc(sizeof (struct Element2));

new_element2->data = malloc(sizeof (int));

*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い // リストのデータ構造 // Java 言語でアクセッサなし

// Element2 next_element2; // どこかで与えられている Element2 new_element2;

new_element2 = new Element2();

new_element2.data = 100;

new_element2. next = next_element2;

Element2

１００ next

Element1

getData() getNextElement() setNextElement()

data next new_element1

next_element1

new_element2

Element2

data 100

data next

Element1

getData() getNextElement() setNextElement()

１００ next

next 100

next data data

next

ルートノード

末端ノード エッジ

ノード

木構造

ルートとそれ以外の

ノードにちょうど１つだけ の経路しか存在しない

53

まとめ

• データ構造

–

• プログラムへの変換

–

• メモリのイメージ

–

• プログラミング言語による違い

– Java

•

– Java