コンピュータ基礎
アルゴリズムとは
－ 人間の作業を通じて考察する
成蹊大学 理工学部
情報科学科
アルゴリズム（algorithm, 算法）
A
well-ordered collection of unambiguous
and effectively computable operations that,
when executed, produces a result and halts
in a finite amount of time.
－ G. Michael Schneider
誰でもわかるように書かれた“道案内”や
“料理のレシピ”は，一種のアルゴリズム
手順だけでなくて，作業に必要な場所，道具，
材料についても述べないといけない
»カウンタ，メモ用紙，. . .
アルゴリズム（algorithm, 算法）
A
well-ordered collection of unambiguous
and effectively computable operations that,
when executed, produces a result and halts
in a finite amount of time.
well-ordered : 手順をはっきりさせる
unambiguous : 「何回か繰り返す」「以下同
様に」は曖昧
effectively computable : できない作業は指示
しない
halts in a finite amount of time : 永遠に終わら
ないのはだめ
アルゴリズムの語源
Abu‘Abd
Allah Muhammad
ibn Musa
.
al-Khwarizmi
“Father of Abudullah, Mohammed, son of
Moses, native of Khwarizm”
８～９世紀のペルシャの数学者，教科書著者
“手順”の基本パターン（制御構造）
一連の作業（作業1，作業2，...,
番に処理する
ある（一連の）作業を繰り返す
作業n）を順
... を ○ 回繰り返す
... を x = x1, x2, ..., xn について行う
...（条件）が成り立っている間 ... を繰り返す
状況に応じて処理内容を変える
...（条件）が成り立っていれば作業1，［さも
なければ作業2 ］を行う
すでに定義してある他の処理を実行する
簡単な例題 － 答案の集計
100枚の採点済み答案用紙の束の中から最高
点の答案を（表彰したいので）全部抜き出せ
使えるもの：
答案３枚分の机スペース（A, B, C）
片手
簡単な例題 － 答案の集計
Aに答案の束を置く
Aの頭の1枚をCに移動
Aに答案が残っている限り以下を繰り返す
Aの頭の1枚がCの頭の1枚と同得点以上なら
ば
Aの頭の1枚をCに移動
さもなければ
Aの頭の1枚をBに移動
簡単な例題 － 答案の集計
Cの頭の1枚をAに移動
Cに答案が残っている限り以下を繰り返す
Cの頭の1枚がAの頭の1枚と同得点ならば
Cの頭の1枚をAに移動
さもなければ
Cの頭の1枚をBに移動
Aに積まれた答案が最高点である．B, Cには
最高点の答案はない．
正しいことを証明する
これくらいの例ならば，正しいかどうかが直
観的にもわかる．しかし
アルゴリズムにはちゃんとした説明や証明が
必要
» 複雑になってくると直観ではわからない
» 証明なしのプログラムに命は託せない
正しいことをきちんと説明するにはどうすれ
ばいいか？
「なぜこれでいいの？」と聞かれて「明らか
じゃないですか」では非科学的
Cの束の答案は，
いつも上から見て得
点の良い順に並んで
いる
簡単な例題 － 再訪
Aに答案の束を置く
Bの束には，Cの
Aの頭の1枚をCに移動
頭の１枚よりも高得
Aに答案が残っている限り以下を繰り返す
点の答案はない
Aの頭の1枚がCの頭の1枚と同得点以上なら
すべての答案はA,
ば
B, C のいずれかに
Aの頭の1枚をCに移動
存在する
さもなければ
Aの頭の1枚をBに移動
ここでは何が常に成立？
ここでは何が成立？
Aには答案が残っ
ていない
簡単な例題 － 再訪
Cの頭の1枚をAに移動
Cに答案が残っている限り以下を繰り返す
Cの頭の1枚がAの頭の1枚と同得点ならば
Cの頭の1枚をAに移動
さもなければ
Cの頭の1枚をBに移動
ここでは何が常に成立？
繰返し作業のあいだじゅう不
変な“性質”を探せばよい
Aに積まれた答
案は最高点である
Bには最高点の
答案はない
すべての答案は
A, B, C のいずれ
かに存在する
例題２－ 最大公約数
紙に並べて書かれた二つの正整数の最大公約
数（greatest common divisor, gcd）を求めよ．
使えるもの：紙の余白と鉛筆
素因数分解をするには大変な手間がかかる
大変なことが暗号技術に利用されるほど
のとき gcd(x,y) = gcd(x ｰ y,y) であること
を利用 － 互減法（2500年以上前！）
x>y
引算のかわりに剰余算を使うとEuclidの互除
法（2300年以上前）
例題２－ 互減法
左右の一番下の整数の値が異なる間，以下を
繰り返す
大きい方の値の下に，その値
と小さい方の値との差を記入
残っている（同一の）値が答
20
68
12
48
4
28
8
4
例題２－ 互減法
左右の一番下の整数の値が異なる間，以下を
繰り返す
大きい方の値の下に，その値
と小さい方の値との差を記入
一番下の二数のgcd
＝ 元の二数のgcd
残っている（同一の）値が答
繰返しは必ず終わるの
だろうか？
20
68
12
48
4
28
8
4
例題２－ 互減法
左右の一番下の整数の値が異なる間，以下を
繰り返す
大きい方の値の下に，その値
と小さい方の値との差を記入
一番下の二数のgcd 記入され
＝元の二数のgcd
た値は正
残っている（同一の）値が答
繰返しは必ず終わるのだろうか？
⇒ 一番下の二数の和が必ず減る
20
68
12
48
4
28
8
4
互減法（x と y の最大公約数）
x y である間
x > y ならば
x←xｰy
さもなければ
y ← y ｰ x
を繰り返す
while (x != y) {
if (x > y)
x = x ｰ y;
else
y = y ｰ x;
}
Java 言語・C/C++言語
値の交換
x と y の内容を交換するには
どうすればよいか？（計算機は一度に一つの
ことしかできない）
クイズ：変数
78
90
x
y
値の交換
78
90
x
y
z
例
方法１
z←x
x←y
y←z
方法2
x←yｰx
y←yｰx
x←x+y
x
12
12
90
y
90
78
78
値の交換
方法2
x←yｰx
y←yｰx
x←x+y
(x0,
(x1,
(x1,
(x2,
y0)
y0)
y1)
y1)
正しいことをどのよ
うに示せばよいか？
数学の変数と数学の
等式で書き直してみる
x1 = y0 ｰ x0
y1 = y0 ｰ x1
x2 = x1 + y1
x2 = y0
y1 = x0
最短経路を求める
10
B
12
20
7
start
8
A
D
11
14
10
C
15
E
F
15
仮定：各地点間のコストは負でない
cf. 運賃計算，インターネットの経路制御
最短経路を求める ― Step 1
12
B
10
12
8
A
20
7
start
0
D
11
14
10
C
10
15
E
F
15
最短経路を求める ― Step 2
18
12
B
10
12
8
A
20
7
start
0
24
D
11
14
10
C
10
15
E
25
F
15
最短経路を求める ― Step 3
12
B
10
12
8
A
20
7
start
0
22
24
D
11
14
10
C
10
15
E
25
19
F
15
最短経路を求める ― Step 4
12
B
10
12
7
start
0
8
A
22 30
24
D
20
11
14
10
C
10
15
E
25
19
F 34
15
最短経路を求める ― Step 5
12
B
10
12
8
A
20
7
start
0
22
24
D
11
14
10
C
10
42
F 34
15
E
25
19
15
最短経路を求める ― Step 6
12
B
10
12
8
A
20
7
start
0
22
24
D
11
14
10
C
10
15
E
25
19
F 34
15
最短経路を求める － Dijkstra法
∞ とする）
スタート点の旅程を 0 とする
赤丸のついていない地点が残っている限り
（すべての地点の旅程を
赤丸のついていない地点の中で旅程が最小の
地点（p とする）に赤丸をつける
p 地点の各隣接地点（q とする）について
p 地点経由の旅程の方が既知の旅程より短
ければ，q 地点の旅程を更新する
まとめ
プログラミングの基本はアルゴリズム設計
アルゴリズムを書いたら，その正当性を論理
的に検討しよう．
ほとんどのアルゴリズムは繰返し作業を含む
毎回の繰返しの前後で変わらない性質をたく
さん発見しよう
»その性質は繰返しの開始前にも終了後にも
成り立つ
毎回の繰返しによって減少するものを一つ発
見しよう
© Copyright 2024 ExpyDoc
