アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月15日

Presentation on theme: "アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月15日"— Presentation transcript:

1 アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月15日
アルゴリズムとデータ構造 第1章　アルゴリズムと計算量 4月15日 情報知能学科 白井英俊

2 復習 アルゴリズム＋データ構造＝プログラム 本講義は「プログラミング」の講義ではない。
使用するプログラミング言語に（あまり）依存しない、いろいろな種類のプログラムを作るための 「基本的な知識と技術の習得」 が本講義の目的 その基本知識と技術が アルゴリズム　と　データ構造

3 例えて言えば... 復習 アルゴリズムは料理のレシピ 入力 ... 料理の材料 （小麦粉、キャベツなど)
入力 ... 料理の材料　（小麦粉、キャベツなど) 出力 ... 料理 （お好み焼き、カレーライスなど) 料理を作るには材料をどんな手順でどのように調理するか、が必要 ... アルゴリズム データ構造は、料理のための道具 レシピが読めても、料理を作れないのでは意味がない！⇒　ちゃんと動くプログラムを書けなければ意味がない。。。さらに効率性も大事。。。

4 前回の問題：配列を使ったプログラム 問題１．変数aには配列が値として入っている。
　　たとえば、 a= [ 1, 2, 3,“a”,“ab”,“abc” ] ここで、a[1]とa[2]の値を取り換えるコード（プログラムの断片）は？ 問題２．変数aには配列が値として入っている。 　　aの偶数番目の要素と奇数番目の要素をすべて取り換えるコードは？ 　たとえば、 a= [ 1, 2, 3,“a”]ならa= [ 2,1, “a”,3]となる

5 問題１． a[1]とa[2]の値を取り換える 例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ]
これは確かに例題には適用できるが 　aがどんな値でもできるものではない --- 解として不適

6 問題１の関連問題 変数x と y の値を取り替える(swap) ダメな解答: x = y ; y = x
x=3, y=5ならば、これによりx=5, y=3になる ｘ，ｙの値に関係なくちゃんと動くことが条件 ダメな解答:　x = y ; y = x その理由が即答できない人は『よく考えてみよう』 ; は複数のコードを一行で書くためのもの 正解：使われていない変数（ここではｚとする）を用いる 　　z = x; x = y ; y = z 別解(Rubyの特性): x, y = y, x

7 プログラミング言語における＝の意味 プログラミング言語の等号（＝）の左辺と右辺は意味が異なる
＊例えば、数学的には、 x = x+1 はありえない 　　= の右側は「値」（変数なら、それが記憶している数値や文字列） 　　=の左側は「記憶場所」 だから、アルゴリズムの記述では代入に←を使ったりする ＊ x = x+1 　xの値に１を足した結果を記憶場所xに記憶 ＊a[1] = a[2] a[2]の「値」をa[1]の場所に書き込む x ← x+1 と書いた方がしっくりくる？

8 問題１． a[1]とa[2]の値を取り換える 例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ]
一案:　使われていない変数ｘを用いて 　　　　　x = a[1] ; a[1] = a[2] ; a[2] = x 別解:　　　a[1], a[2] = a[2], a[1] Rubyでは多重代入と呼びます

9 問題２．配列aの偶数番目の要素と奇数番目の要素をすべて取り換えるコード
a= [ 1, 2, 3,“a”] なら a= [ 2,1, “a”,3] となる ダメな解答(1)： a[2n] = a[2n+1]; a[2n+1] = a[2n] ダメな解答(2): a[0], a[1], a[2], a[3] = a[1], a[0], a[3], a[2] 配列の要素の個数だけ、「値の取替」の必要がある ⇒　繰り返し　を使う 解答例： i = 0 while ( i < a.length) a[i], a[i+1] = a[i+1],a[i] i = i+2 end # while 例題だけではなく、より広い範囲で（「一般的」に）適用できる解を求める！

10 アルゴリズムの例 入力 出力 問題（教科書p.1)： n個の実数x1, x2, …, xnが与えられて、その中の最大値を求める

11 アルゴリズムの例（続) より明確な記述(p.2) 入力： 正の整数nとn個の実数値x1, x2, …, xn
　手続き： 1. y ← x1 (yは「それまでの最大値」を記録） 2. i = 2,3,…,nに対して順に次を行う： 　　 xi > y ならば y ← xi 3. yを出力する 「変数y に x1の値を代入する」

12 アルゴリズムの例（続) 「プログラム」風(p.3) Algorithm MAX(n, x1, x2, …, xn)：
入力（Input): 正整数 n と n 個の実数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　 if xi > y then y ← xi ; 3. return y; 記法の注意：ここではプログラムの 命令の後に「；」を書く ここでの記法についてはウェブページの「教科書のアルゴリズムの記述とRUBY言語の対応」参照 アルゴリズムにおいて「出力する」とは、 printするという意味でなく、returnによって 値を「返す」ということ

13 アルゴリズムの検証 このアルゴリズムがちゃんと動くかは 頭で考え、手を動かす アルゴリズムを反映したプログラムを作り、
アルゴリズムを反映したプログラムを作り、　 　　適切な入力を与えて動かし、結果を調べる ことで検証する、つまり、正しいかどうかを確認する

14 アルゴリズムからRubyプログラムへ 2ページと3ページのどちらの記述でもよいがそれに基づいてRubyプログラムを書く
君たちはちゃんとマスターしていると信じたい！

15 アルゴリズムからRubyプログラムへ(続き：代入と配列の使用）
入力は、変数nとxとする。ただし、nの値は正整数、xの値は実数を要素とする配列 手続きの最初をRubyで書くのは簡単… Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; ←　はアルゴリズムの記述における『代入』の書き方。Rubyプログラムでは＝を使う y = x[1] 実はこれだと問題があるが、今はこれで進める

16 アルゴリズムからRubyプログラムへ(続き：繰り返し）
2番目の手続きは「繰返し」 　Rubyには、『繰り返し』のメソッドはいろいろある: while, for, downto, times, … (適切なものを選べるようにしよう！） ここではforを使うのが適切 Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; 実はこれだと問題があるが、今はこれで進める 書き方：　for i in 2..n 繰り返される処理 end

17 アルゴリズムからRubyプログラムへ(続き：条件分岐）
「繰り返される処理」は ここでは「条件分岐」である。 　Ｒｕｂｙの条件文の書き方： 　if (条件式） 　　「条件式が成り立つ時の処理」 　else 　 「条件式が不成立の時の処理」 end Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; elseと「条件式が不成立の時の処理」は、なくても可

18 アルゴリズムからRubyプログラムへ(2番目の処理のまとめ）
2番目の処理をまとめると以下のように書ける： for i in 2..n if (x[i] > y) y = x[i] end #if end #for Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; これらは本来必要ないものだが、 プログラムを書くときには役に立つもの

19 アルゴリズムからRubyプログラムへ(３番目の処理）
3番目の return y はyの値を返すもの。 でも、どこに返すのか？ ここでの選択 　(1) 画面に表示する(printを使う） 　(2) アルゴリズムＭＡＸの結果としてMAXを呼び出したモノに返す ここでは(2)を考える。 でも、「アルゴリズムＭＡＸの結果として返す」とはどういうこと？ Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y;

20 アルゴリズムからRubyプログラムへ （関数／メソッド）
「アルゴリズムＭＡＸの結果として返す」とは、 Ruby の関数（メソッド）をつくり、それにmaxと名をつけ、maxの関数の処理として1から3までの処理をやらせる、 ということ Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; Ｒｕｂｙでは関数名を大文字にできないのでmaxとする return文が大事

21 アルゴリズムを関数として表現 関数：　入力を取り、それに基づいて一連の手続き（計算）を行い、その結果を出力する（返す）、というプログラムの単位

22 は仮引数という。『定義』のための仮のもの
関数について 関数定義の引数(xとｙ) は仮引数という。『定義』のための仮のもの 関数名を func とすると 　関数の定義の書き方： 　　　　　　def func(x,y) … プログラム(「コード」とも)… 　　　　　　　　　…どこかにreturn文が必要… end 関数の呼び出し： ans = func(3,5) 関数呼出の引数(3と5) は実引数。計算に用いられる実物。

23 関数の利点 一連の手続きに『名前』をつけ、入力と出力を明示することで、その手続きが何をしているかが明確になる
プログラムを関数に分けることで、そのプログラムの構造が明確になる 関数ごとにデバッグをすることで、誤りが発見しやすい。また変更も容易になる 同じような処理をする場合に、冗長性が減る 『再帰』は関数を使わないと書けない

24 アルゴリズムからRubyプログラムへ （完成）
関数は以下のようにdef を使って定義する： def max(n,x) y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; # if # for Rubyのプログラムでは、endがdefやforやifなどと対応するため対応関係がわかりにくい。そこで、インデント(段付け）をして対応が分かるように書く # def

25 実際に検証してみよう 先のプログラムは単に「アルゴリズム」をプログラムに直しただけ。 それがちゃんと期待通りに計算するかは、
(1) 具体的な（入力）データを与える 　(2) アルゴリズムが返した結果を表示させる ということが必要。

26 実際に検証してみよう(続き） この内容をmax.rbとして、実行させてみると… 具体的には以下のようなプログラムを作る：
def max(n,x) y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y # ここからが検証用のデータ print max(10, [0.3, 0.1, 0.7, 0.9, 1, 0.2, 0.5, 0.8, 0.4, 1.0]) # if # for # def この内容をmax.rbとして、実行させてみると…

27 動かない… ちゃんと書いたはずなのだが、以下のようなエラーメッセージが出て動かない…
max.rb:5:in `max': undefined method `>' for nil:NilClass (NoMethodError) from max.rb:4:in `each' from max.rb:4:in `max' from max.rb:12

28 めげない！ エラーメッセージに理由が書いてある。それを読んで、理由を理解して、直してみよう。
講義用のウェブページにある「Rubyのエラーメッセージとその対処 」を読んでみよう。 これはそのうちのどこにあたるか？

29 プログラムの修正 「(5) 未定義(undefined)なメソッド(method)／関数によるエラー 」に相当することが分かる
解釈：この場合は、5行目に使われている＞ という「未定義なわけがない」演算子がやり玉にあがっている。 ここは、つまり「for nil:NilClass」が問題。つまり「nil」には ＞ が使えない、と言っている。 対処法：このようなエラーが起きるのは、配列の要素の指定が間違っているか、要素の値の初期化(例えば0にする)ことを忘れている場合が多い

30 プログラムの修正(続き) わかっただろうか？配列の要素の指定に問題があったのである。 プログラムを見てみよう： def max(n,x)
y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y ｙに配列の先頭の要素を与えた「つもり」 配列の2番目の要素から最後の要素まで、要素を一つ一つ調べている「つもり」 # if Ｒｕｂｙの配列のインデックスは、いくつから始まり、いくつが最後の要素をさすものだったかな？ # for # def

31 プログラムの修正(完成） # maxアルゴリズムの検証 def max(n,x) y = x[0] for i in 1..(n-1)
if (x[i] > y) y = x[i] end return y # ここからが検証用のデータ print max(10, [0.3, 0.1, 0.7, , 0.2, 0.5, 0.8, 0.4, 1.0]) 実行させた結果は… # if # for # def

32 参考 プログラミング言語Cで書くと： float max(int n, float x[ ]) { int i; float y=x[0];
for (i=1; i < n; i++) { if (x[i] > y) { y=x[i]; } } return y; 実際には以下のプログラムに挿入 #include <stdio.h> #define Num 10 /* ここにいれる */ int main() { static float data[Num] = { 0.3, 0.1, 0.7, , 0.2, 0.5, 0.8, 0.4, 1.0}; printf(“%f\n”, max(Num,data)); }

33 4月15日の課題 2. 配列aのx番目の要素とy番目の要素を取り換えて得られる配列を返 す関数定義torikae(a,x,y) 例: a = [1,2,3,4,5] 、とすると torikae(a,1,3)は [1,4,3,2,5] を返す 回答 概略は次のようになる（わからない人はいますか？）

34 4月15日の課題(2) z = a[x] a[x] = a[y] a[y] = z 配列aのｘ番目の要素とｙ番目の
2.　配列aのx番目の要素とy番目の要素を取り換えて得られる配列を返す関数定義torikae(a,x,y) def torikae(a,x,y) end # def z = a[x] a[x] = a[y] a[y] = z 配列aのｘ番目の要素とｙ番目の 要素を取りかえるコードは？ ここに課題を満たすコード （プログラム）を書く # 最後に配列を返す--- return a 参考：　最初の３行は 　a[x], a[y] = a[y], a[x] とも書ける

35 4月15日の課題(3) ２つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数の定義seiret2 例: a = [1,2] とすると seiret2(a)は [1,2] を返し、 a = [20,10] とすると seiret2(a)は [10,20] を返す 回答 　概略は次のようになる（わからない人はいますか？）

36 4月15日の課題(3)続 if (a[0] > a[1]) a[1], a[0] = a[0], a[1]
２つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数の定義seiret2 例: a = [1,2] とすると seiret2(a)は [1,2] を返し、 a = [20,10] とすると seiret2(a)は [10,20] を返す def seiret2(a) end #def if (a[0] > a[1]) a[1], a[0] = a[0], a[1] end # if 参考：　２行目は a = torikae(a,0,1) 　とも書ける 配列aの１番目の要素が２番目の要素より 大きければ、これらを取りかえるコード！ return a # 最後に配列を返す

37 4月15日の課題(4) 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 例: a = [1,2,3] とすると seiret3(a)は [1,2,3] を返し、 a = [20,10,30] とすると seiret3(a)は [10,20,30] を返し、 a = [33,22,11] とすると seiret3(a)は [11,22,33] を返す 回答 　概略は次のようになる（わからない人はいますか？）

38 4月15日の課題(4)続 ここに課題を満たすコード （プログラム）を書く これはちょっと考えないといけない…
4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 def seiret3(a) end # def ここに課題を満たすコード （プログラム）を書く これはちょっと考えないといけない…

39 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： ３つの要素(仮にx,y,zとする)を小さいものから大きいものに並び替えるとすれば６通りの可能性がある( 3! = 6) (1) x ≧ y ≧ z (2) x ≧ z ≧ y (3) y ≧ x ≧ z (4) y ≧ z ≧ x (5) z ≧ x ≧ y (6) z ≧ y ≧ x

40 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： まずxとｙの大きさを比べる… は x ≧ y の場合の可能性 (1) x ≧ y ≧ z (2) x ≧ z ≧ y (3) y ≧ x ≧ z (4) y ≧ z ≧ x (5) z ≧ x ≧ y (6) z ≧ y ≧ x

41 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： まずxとｙの大きさを比べる… 次にx と zの大きさを比べる (1) x ≧ y ≧ z (2) x ≧ z ≧ y (5) z ≧ x ≧ y 最後にy と zの大きさを比べて(1)か(2)が決まる

42 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 if (x >= y) if ( x >= z) if (y >= z) return [z,y,x] # x>= y>= z else return [y,z,x] # x>= z >= y end #if (y>=z) end # if (x>=z) end # if (x>=y) # xとｙの大きさを比べる… # 次にx と zの大きさを比べる # 最後にy と zの大きさをる これにならって他の場合を書きこむ！

43 4月15日の課題(4)続 ４．三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 完成させよう！

44 練習問題（１） n個の実数x1, x2, …, xnが与えられて、その中の最小値を求める アルゴリズムを書く プログラムを書く
適当なデータを与えて、プログラムを実行してみる。そして最小値を返すことを確認する。

45 練習問題（２） n個の実数x1, x2, …, xnが与えられて、その中の２番目に大きな数を求める アルゴリズムを書く プログラムを書く
適当なデータを与えて、プログラムを実行してみる。そして2番目に大きな数を返すことを確認する。

46 出欠レポート ここまでの作業内容を出欠レポートとして書く 次は、宿題について

47 課題（1と２は提出を求める宿題） プログラムを書くために、Rubyを復習しよう 次の問題にチャレンジしてみよう
　(1)最古のアルゴリズム(ユークリッドの互除法）をプログラム化する 　(2) ファイルから実数を読み込み、その中の最大値を答える（つまり、数がファイルに書いてある） 　(3) 最大値と最小値からなる配列を返す (4) 最大値と最小値からなる配列を答えるだけではなく、それらが何番目の要素であるかも答える 宿題の提出期限は4月21日（木曜日）まで。あて先はウェブページ参照

48 プログラム課題提出の注意 （これこれの問題を解く）「プログラムを書け」、もしくは「アルゴリズムを書け」という課題が多く出される
この時に求められているのは「プログラム（やアルゴリズム）」だけではないことに注意 要求事項がちゃんと満たされていることも示す（検証する）必要がある そのために、プログラムの中身、その実行例（複数個の例題）、実行結果の吟味（ちゃんと目的を果たしているかどうか）を示す

49 ユークリッドの互除法 入力：正整数p, q 出力：pと q の最大公約数 手続き：
　　1. q > p ならば、 p と q の値を入れ替える 　　2. r ← （p の q による剰余） 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p ← q, q ← r として、１へ。 p = 72, q = 30 として、試してみよう

50 基本的な用語の確認 aとｂの公約数：aもbも正整数であることが前提 aの約数とbの約数で共通する数のこと
　例： 30 の約数は 1, 2, 3, 5, 6, 10, 15, 30 72の約数は 1, 2, 3, 4, 6, 8, 9, 12, …, 36, 72 aとｂの最大公約数(GCD)：aとｂに共通する公約数のうち最大のもの 30と72の最大公約数(これをGCD(30,72)と書く）は…