コンピュータ基礎 アルゴリズムとは - 人間の作業を通じて考察する 成蹊大学理工学部情報科学科
アルゴリズム (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 8~9 世紀のペルシャの数学者, 教科書著者
手順 の基本パターン ( 制御構造 ) 一連の作業 ( 作業 1, 作業 2,..., 作業 n ) を順番に処理する ある ( 一連の ) 作業を繰り返す... を 回繰り返す... を x = x 1, x 2,..., x n について行う...( 条件 ) が成り立っている間... を繰り返す 状況に応じて処理内容を変える...( 条件 ) が成り立っていれば作業 1,[ さもなければ作業 2 ] を行う すでに定義してある他の処理を実行する
簡単な例題 - 答案の集計 0 枚の採点済み答案用紙の束の中から最高点の答案を ( 表彰したいので ) 全部抜き出せ 使えるもの : 答案 3 枚分の机スペース (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に答案の束を置く Aの頭の1 枚をCに移動 Aに答案が残っている限り以下を繰り返す Bの束には,Cの頭の1 枚よりも高得点の答案はない 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 のいずれかに存在する
例題 2- 最大公約数 紙に並べて書かれた二つの正整数の最大公約数 (greatest common divisor, gcd) を求めよ. 使えるもの : 紙の余白と鉛筆 素因数分解をするには大変な手間がかかる 大変なことが暗号技術に利用されるほど x>y のとき gcd(x,y) = gcd(x ー y,y) であることを利用 - 互減法 (2500 年以上前!) 引算のかわりに剰余算を使うとEuclidの互除法 (2300 年以上前 )
例題 2- 互減法 左右の一番下の整数の値が異なる間, 以下を 繰り返す 大きい方の値の下に, その値と小さい方の値との差を記入 20 68 48 残っている ( 同一の ) 値が答 4 28 8 4
例題 2- 互減法 左右の一番下の整数の値が異なる間, 以下を 繰り返す 大きい方の値の下に, その値と小さい方の値との差を記入 20 68 一番下の二数の gcd = 元の二数の gcd 4 48 28 残っている ( 同一の ) 値が答 繰返しは必ず終わるのだろうか? 8 4
例題 2- 互減法 左右の一番下の整数の値が異なる間, 以下を 繰り返す 大きい方の値の下に, その値と小さい方の値との差を記入 20 68 一番下の二数の gcd = 元の二数の gcd 記入された値は正 残っている ( 同一の ) 値が答 繰返しは必ず終わるのだろうか? 一番下の二数の和が必ず減る 4 48 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 方法 1 z x x y y z y 方法 2 x y ー x y y ー x x x + y z 例 x y 90 78 90 78
値の交換 方法 2 x y ー x y y ー x x x + y (x 0, y 0 ) (x 1, y 0 ) (x 1, y 1 ) (x 2, y 1 ) x 1 =y 0 ー x 0 y 1 = y 0 ー x 1 x 2 = x 1 + y 1 正しいことをどのように示せばよいか? 数学の変数と数学の等式で書き直してみる x 2 =y 0 y 1 = x 0
最短経路を求める start A 8 B 14 7 D 11 20 F 15 C E 15 仮定 : 各地点間のコストは負でない cf. 運賃計算, インターネットの経路制御
最短経路を求める Step 1 start 0 A B 8 14 7 D 11 20 F C 15 E 15
最短経路を求める Step 2 start 0 A 18 B 8 14 7 24 D 11 20 F C 15 E 25 15
最短経路を求める Step 3 start 0 A B 8 14 7 22 24 D 11 20 F C 15 E 25 19 15
最短経路を求める Step 4 start 0 A 8 B 14 7 22 30 24 D 20 11 F 34 C 15 E 25 19 15
最短経路を求める Step 5 start 0 A B 8 14 7 22 24 D 11 20 F 42 34 C 15 E 25 19 15
最短経路を求める Step 6 start 0 A B 8 14 7 22 24 D 11 20 F 34 C 15 E 25 19 15
最短経路を求める - Dijkstra 法 ( すべての地点の旅程を とする ) スタート点の旅程を 0 とする 赤丸のついていない地点が残っている限り 赤丸のついていない地点の中で旅程が最小の地点 (p とする ) に赤丸をつける p 地点の各隣接地点 (q とする ) について p 地点経由の旅程の方が既知の旅程より短ければ,q 地点の旅程を更新する
まとめ プログラミングの基本はアルゴリズム設計 アルゴリズムを書いたら, その正当性を論理的に検討しよう. ほとんどのアルゴリズムは繰返し作業を含む 毎回の繰返しの前後で変わらない性質をたくさん発見しよう» その性質は繰返しの開始前にも終了後にも成り立つ 毎回の繰返しによって減少するものを一つ発見しよう