アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量

Presentation on theme: "アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量"— Presentation transcript:

1 アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量
アルゴリズムとデータ構造 はじめに 第1章　アルゴリズムと計算量 情報知能学科 白井英俊

2 教科書の確認 杉原厚吉 (2001) 『データ構造とアルゴリズム』. 東京：共立出版. 講義の時は必ず持ってくること
（4月中はあまり参照しないかもしれないが） 定期試験の時に持ち込み可 （書き込み自由）

3 アルゴリズムとは 与えられたデータから目的の情報を見つけ出したり、作り出したりするための手続き 誰のための手続き？ → 人間も計算機も
誰のための手続き？　→　人間も計算機も 本講義でとりあげる「アルゴリズム」は、計算機で実行できるよう（つまり、プログラムが欠けるよう）、明確に書かれることが要求される

4 データ構造とは アルゴリズムを実行するための『データ』や、アルゴリズムの対象となる『情報』を、計算機（プログラム）で表す（表現する）方法
よく用いられるデータ構造の例： 　　配列、リスト、スタック、キュー、グラフ、木、ハッシュ

5 アルゴリズム＋データ構造＝プログラム 本講義は「プログラミング」の講義ではない。
　つまり、特定のプログラミング言語に習熟することが目的ではない 使用するプログラミング言語に依存せず、ある目的を達成するためのプログラムを作るための「基本的な知識と技術の習得」が目的 プログラムを作ることは要求する。それは、「アルゴリズム」や「データ構造」が正しく実現されているか、という検証のため

6 たとえて言えば… 入力 例えて言えば、 　アルゴリズムは料理のレシピ 出力

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

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

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

10 アルゴリズムの例（続) 「プログラム」風(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によって 値を「返す」ということ

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

12 アルゴリズムからRubyプログラムへ 2ページと3ページのどちらの記述でもよいがそれに基づいてRubyプログラムを書く

13 データ構造の出番 「入力：正整数 n と n 個の実数x1, x2, …, xn」 の中の n 個の実数x1, x2, …, xn
をRubyのプログラムでどのように表現するか？ 複数個の実数を「まとめて」表すための標準的な方法は「配列」というデータ構造を使うこと ところで、Rubyの配列って？ 「標準的」とは、よく用いられる、という意味 このように、いくつかのオブジェクトをまとめて記憶する データ構造を「入れ物」と呼ぶことがあります

14 Rubyの配列 配列とは：変数は一個のオブジェクト（物）しか記憶できないが、配列は複数のオブジェクトを記憶する
書き方：オブジェクトをカンマで区切って並べ、全体を大括弧でくくる。 　例： [ 1, 2, 3, “a”, “ab”, “abc” ] Rubyでは、配列はArray（アレイ）と呼ばれるオブジェクト

15 Rubyの配列（続) 配列[インデックス] 配列自体が一つのオブジェクトなので、これを変数の値とすることができる。
例：　x = [ 1, 2, 3, “a”, “ab”, “abc” ] 配列の要素の値を調べる（取り出す)には… 配列[インデックス] 「インデックス」とは、配列における要素の位置を表す数のこと。 先頭の要素のインデックスが０、次が１、…となる。

16 Rubyの配列（続) x = [ 1, 2, 3,“a”,“ab”,“abc” ] とすると、xの値となっている配列に対し、
　　インデックスが３の要素は… “abc”のインデックスは… 試してみよう。 　x[3] 　 この他にも　x[0], x[5], x[6], x[-1] など [ 1, 2, 3,“a”,“ab”,“abc” ][3]

17 Rubyの配列（続) size (もしくは length) というメソッドを使う 配列の大きさ：配列の要素の数はどうやって分かる？
メソッドとは、オブジェクトに対する操作のこと。関数ともいう。オブジェクトによっていろいろなメソッドが用意されている。 試してみよう。 　x.size [ 1, 2, 3,“a”,“ab”,“abc” ].length

18 配列を使ったプログラム 問題１．変数aには配列が値として入っている。 たとえば、 a= [ 1, 2, 3,“a”,“ab”,“abc” ]

19 アルゴリズムから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; y = x[1] 実はこれだと問題があるが、今はこれで進める

20 アルゴリズムから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

21 アルゴリズムから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と「条件式が不成立の時の処理」は、なくても可

22 アルゴリズムからRubyプログラムへ(2番目の処理のまとめ）
2番目の処理をまとめると以下のように書ける： for i in 2..n if (x[i] > y) y = x[i] 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;

23 アルゴリズムからRubyプログラムへ(３番目の処理）
3番目の return y はyの値を返すもの。 でも、どこに返すのか？ ここでの選択 　(1) 画面に表示する(printを使う） 　(2) アルゴリズムＭＡＸの結果として返す ここでは(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;

24 アルゴリズムから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とする

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

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

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

28 アルゴリズムから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

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

30 実際に検証してみよう(続き） この内容を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.2, 0.5, 0.8, 0.4, 1.0]) # if # for # def この内容をmax.rbとして、実行させてみると…

31 動かない… ちゃんと書いたはずなのだが、以下のようなエラーメッセージが出て動かない…
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

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

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

34 プログラムの修正(続き) わかっただろうか？配列の要素の指定に問題があったのである。 プログラムを見てみよう： 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

35 プログラムの修正(完成） # 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.9, 1.1, 0.2, 0.5, 0.8, 0.4, 1.0]) 実行させた結果は… # if # for # def

36 参考 プログラミング言語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)); }

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

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

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

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

41 ユークリッドの互除法 入力：正整数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 として、試してみよう

42 基本的な用語の確認 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)と書く）は…