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

(1)

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

2012 年 6 月 7 日

担当：酒居敬一＠Ａ４６８ ([email protected])

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

(2)

ü  テキスト 

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

石畑清著 ( 岩波書店 )

ü  参考書 

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

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

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

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

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

H.S. ウォーレンＪｒ著，滝沢徹，鈴木貢， 

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

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

B.W. カーニハン， D.M. リッチー著， 

(3)

講義計画

1.  

アルゴリズムと計算量（６月７日５時限）

2.  

線形探索・２分探索（６月１１日５時限）

3.  

２分探索木（６月１４日５時限）

4. 

平衡木・

B

木（６月１８日５時限）

5.  

ハッシュ法（６月２１日５時限）

6. 

シェルソート（６月２５日５時限）

7.  

クイックソート（６月２８日５時限）

8.  

ヒープソート（７月２日５時限）

9. 

マージソート・ビンソート（７月５日５時限）

10.  

グラフの表現法・探索（７月９日５時限）

11. 

連結性の判定（７月１２日５時限）

12.  

最短路の問題（７月１７日２時限）※

13.  

文字列のアルゴリズム（７月１９日５時限）

14. 

バックトラック・幅優先探索・ゲームの木の探索（７月２３日５時限）

15.   NP

完全問題・近似アルゴリズム（７月２６日５時限）

16. 

［クォータ末試験］（７月３０日５時限）

(4)

成績評価

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

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

–   教科書・ノート・配布資料

•   再試験はしない．

(5)

本講義の位置づけ

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

ü  計算機言語、情報学群実験１

ü  背景は、表現方法としてのプログラミング言語

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

ü  計算機システムの基礎

ü  数学と計算法（計算機は Σ や∫を知らない）

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

ü  情報学群実験 2

ü  コーディング対象を知る

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

ü  ソフトウェア工学、オペレーティングシステム ⁵

(6)

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

( このように書くのは簡単 )

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

(Java, C, )

抽象化具体化

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

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

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

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

(7)

プログラムとは？

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

–   表現方法にはいっぱいある

•   プログラミング言語の数だけ

–   構造体やレコードといったデータ構造

–   連接や条件文や繰り返し文といった制御構造

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

–   計算機は指示通りに動くように作られている

•   動かない場合も稀にある …

7

(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 

(13)

Ｅｕｃｌｉｄの互除法 ^{（２ページ} _1.1 ^）

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

2.   ｒ＝０であれば、アルゴリズムは終了する。 

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

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

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

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

•   除算

•   ０との比較・分岐処理

•   変数への代入

•   繰り返し（ループ）

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

; アセンブリ言語による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

戻りアドレス引数ｎ引数ｍ

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

ｓｐ＋２ｓｐ

簡単なアルゴリズムであればアセンブリ言語でも記述できる。

ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば

…

ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。

(16)

; アセンブリ言語による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 adds.w #2,sp

1: rts ; return m .end

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

ｓｐ＋２ｓｐ

レジスタ変数

r2(

変数

r)

が、不要になっている。 

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

ｂｓｒ直後のスタック

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

(17)

アルゴリズム

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

–   いつかは停止しないといけない

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

–   ループ不変条件

•   繰り返し開始直前にこの条件が成立。

•   この条件が成立しているときに、

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

(18)

計算量の概念 ^（ ₇ ^ページ _1.2 ^節）  

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

–   時間計算量

•   ( 文字通り ) 計算に要する時間

–  

最悪時間計算量・平均時間計算量

–   空間計算量（領域計算量）

•   どれくらいの作業領域を必要とするかを表す

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

–   漸近的に表現したものが O 記法

•   計算量を定式化したとき、計算量に最も大きな影響

を及ぼす項をとりだしたもの。

(19)

O 記法 

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

–   定数項は無視 –   係数は１

–   一般には最も影響力の強い項のみで表す

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

–   多項式 n

^ｋ

–   指数関数 k ⁿ

(20)

O( n ) O( n log n )

O( n ² ) O(e ⁿ )

2500 100

25 10

10 10

(21)

基本的データ構造

•   スカラ

–   基本型として限定的に記述可能

•   ベクトル

–   １次元の配列として表現可能なことがある –   実は、普通の計算機では演算できない

•   グラフ

–   実は、普通の計算機では簡単に表現できない

•   集合

–   実は、普通の計算機では簡単に表現できない

–   もちろん、集合演算はできない ²¹

(22)

メモリと配列 

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

–   プロセッサが扱える最小単位を要素としている

•   普通の計算機では byte を最小の単位としている

–   有限の大きさを持つ

•   ただし、仮想記憶管理機構により伸長できる場合もある

–   配列のインデックスに相当するものがアドレス

•   メモリへのアクセスはアドレッシングと呼ばれる

–   普通の計算機では、プロセスにはこの配列が 1 個

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

•   プログラミング言語のコンパイラが変換します

(23)

1 2 3 4

n

… …

配列（２７ページ） 

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

•   添え字は連続

–   添え字が１から始まるとは限らない

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

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

(24)

１２３・・・ｍ

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

・・・・・・・

二次元配列 

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

（３，２）

添え字を

用いて

データに

アクセス

(25)

・・・・・・・・・

・・・・・

１２３・・・・ｍ

三次元配列 

（３，１，１）

添え字を用いてデータに

アクセス

(26)

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

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

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

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

データデータ次

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

(27)

先頭

次

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

データデータ次

次データ

先頭前

挿入対象前

削除対象

(28)

例：メモリ割り当て ^{（３７ページ）}

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

・リストで管理

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

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

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

使用中空き使用中

空き

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

ヘッダは左のような構造

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

(29)

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

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

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

使用中空き

空き空き空き空き空き

使用中

メモリ割付け技法

•  

連続割付け

•  

単一連続割付け

• 

分割割付け

(

ゾーン割り付け

)

• 

固定区画割付け

•  

可変区画割付け

•  

非連続割付け

•  

ページング

• 

セグメンテーション管理手法

•  

線形リスト

•  

ハッシュ表

(30)

スタック（ LIFO ） 

スタックポインタ

ポッププッシュ

スタックポインタ

(31)

連結リスト操作（挿入） 

リストを使ったスタック（ push ）

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

先頭次次次

データデータデータ

次

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

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

31

(32)

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

連結リスト操作（削除） 

リストを使ったスタック（ pop ）

(33)

Postscript

•   プログラミング言語ではなくて、ページ記述言語

•   オペランドスタック、辞書スタックを持つ

•   オブジェクトはリテラル、エグゼキュータブル

•   A-WS で gs というコマンドで実行できる

•   push/pop 以外のスタック処理がある

•   index 指定位置の内容をコピーして push

•   rotate 指定位置までのスタックを配列とみて回転

•   [] , {}, () スタックから配列オブジェクトを切り出せる

(34)

RPN （逆ポーランド記法） 

普通は

1 + 2

と入力して

3

という答えを得ます

同じ答えを得るために、

RPN

で書くと

1 2 +

となります。

普通の書き方の

(1 + 2) × (3 + 4)

を

RPN

にすると

1 2 + 3 4 + ×

となります。

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

括弧は優先度を変える

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

Forth, PostScript

といった言語、インテル

x87

数値演算プロセッサ

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

(35)

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 で記述するとき、日本語で数式の動作を

読み上げることにかなり近い順序になる

(36)

/*

可変長引数を持つ関数 *

/

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

が読める→以降の引数がわかる

(37)

/*

可変長引数を持つ関数 *

/

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

(38)

% 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

する

[

オブジェクトの並び

]

は通常の配列

{

オブジェクトの並び

}

は実行可能な配列

(

手続き

)

(

文字の並び

)

は文字の配列（文字列）

(39)

待ち行列（ FIFO ） ^{（４４ページ）}  

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

データ挿入データ取得

39

(40)

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

データ挿入データ取得

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

→右へコピーして移動

→隙間を空ける

(41)

リングバッファ ₍₄₆ ^ページ ₎

Ø   配列の最初と最後を接続して環にしたもの Ø  ２つのポインタでデータの出し入れを管理

Ø  データの先頭を指すポインタ

Ø  head, front

Ø  データの最後尾を指すポインタ

Ø  tail, rear

Ø  ２つのポインタが重なったらデータは空

Ø  領域の大きさを n としたらポインタの位置は n とおり Ø  データの数が 0 から n まで n+1 とおりある

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

(42)

リングバッファ 

挿入口リア

取り出し口

•  

環状のデータ格納領域

•  

データの存在を示すポインタ

(43)

フロント

リアリア

満杯になったとき、

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

空と区別が付かない

(44)

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

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

ü  ポインタが終わりまで移動したら先頭へ戻る ü  （フロント‐リア）の演算でも境界を考慮

ü  ラップラウンド処理

ü  条件文で判定

ü  配列の大きさを 2 のべき乗にする

ü  配列のインデックスをビットごとの AND 処理

(45)

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 で管理

(46)

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 の指すところがキューの先頭

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

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

(47)

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 の指すところがキューの最後尾

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

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

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

(48)

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 までの表示

(49)

//

リストのデータ構造

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

}; ⁴⁹

(50)

//

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

//

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

};

(52)

//

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

１００

Element1

getData() getNextElement() setNextElement()

data next new_element1

next_element1

new_element2

Element2

data 100

data next

Element1

getData() getNextElement() setNextElement()

１００

next 100

next data data

木構造 

ルートとそれ以外のノードにちょうど１つだけの経路しか存在しない

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

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

2012 年 6 月 7 日

担当：酒居敬一＠Ａ４６８ ([email protected])

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

ü テキスト

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

石畑清 著 ( 岩波書店 )

ü 参考書

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

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

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

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

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

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. システム設計の勉強 ( 高水準の知識 )

ü ソフトウェア工学、オペレーティングシステム 5

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

( このように書くのは簡単 )

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

(Java, C, )

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

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

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

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

プログラムとは？

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

– 表現方法にはいっぱいある

• プログラミング言語の数だけ

– 構造体やレコードといったデータ構造

– 連接や条件文や繰り返し文といった制御構造

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

– 計算機は指示通りに動くように作られている

• 動かない場合も稀にある …

7

なぜ学習するか？

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

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

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

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

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

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

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

– 探せばどこかに実装が存在する

ü  テキスト 

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

石畑清著 ( 岩波書店 )

ü  参考書 

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

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

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

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

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

H.S. ウォーレンＪｒ著，滝沢徹，鈴木貢， 

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

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

B.W. カーニハン， D.M. リッチー著， 

1.  

2.  

3.  

4. 

5.  

6. 

7.  

8.  

9. 

10.  

11. 

12.  

13.  

14. 

15.   NP

16. 

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

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

–   教科書・ノート・配布資料

•   再試験はしない．

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

ü  計算機言語、情報学群実験１

ü  背景は、表現方法としてのプログラミング言語

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

ü  計算機システムの基礎

ü  数学と計算法（計算機は Σ や∫を知らない）

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

ü  情報学群実験 2

ü  コーディング対象を知る

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

ü  ソフトウェア工学、オペレーティングシステム ⁵

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

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

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

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

–   表現方法にはいっぱいある

•   プログラミング言語の数だけ

–   構造体やレコードといったデータ構造

–   連接や条件文や繰り返し文といった制御構造

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

–   計算機は指示通りに動くように作られている

•   動かない場合も稀にある …

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

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

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

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

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

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

–   探せばどこかに実装が存在する

–   既存のものを使えばデバグの手間が省ける –   定番と呼ばれる書籍の存在

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

–   そのために勉強する！

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

–   適切なアルゴリズム –   適切なデータ構造

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

–   人間が読み書きするものであることを肝に銘じて

–   きちゃないコードは読む気がするか？

•   構造がわかりやすい

–   よくしられたデータ構造 –   よくしられたアルゴリズム

–   これらの再帰的な組み合わせ

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

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

–   3 日後の自分は他人と同じ

•   記憶力のいい人は 1 ヶ月くらいは平気？

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

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

•  mov eax,value  mov edx,ptr 