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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

プログラムの修正(完成） # 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

参考 プログラミング言語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.9. 1.1, 0.2, 0.5, 0.8, 0.4, 1.0}; printf(“%f\n”, max(Num,data)); }

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

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

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

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

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

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