アルゴリズムとデータ構造

アルゴリズムとデータ構造
はじめに
第1章 アルゴリズムと計算量
情報知能学科
白井英俊
教科書の確認
杉原厚吉 (2001) 『データ構造
とアルゴリズム』. 東京:共立出
版.
講義の時は必ず持ってくること
(4月中はあまり参照しないかもしれないが)
定期試験の時に持ち込み可
(書き込み自由)
2
アルゴリズムとは
• 与えられたデータから目的の情報を見つけ出
したり、作り出したりするための手続き
• 誰のための手続き? → 人間も計算機も
• 本講義でとりあげる「アルゴリズム」は、計算機
で実行できるよう(つまり、プログラムが欠ける
よう)、明確に書かれることが要求される
3
データ構造とは
• アルゴリズムを実行するための『データ』や、ア
ルゴリズムの対象となる『情報』を、計算機(プ
ログラム)で表す(表現する)方法
• よく用いられるデータ構造の例:
配列、リスト、スタック、キュー、グラフ、木、
ハッシュ
4
アルゴリズム+データ構造=プログラム
• 本講義は「プログラミング」の講義ではない。
つまり、特定のプログラミング言語に習熟する
ことが目的ではない
• 使用するプログラミング言語に依存せず、ある
目的を達成するためのプログラムを作るため
の「基本的な知識と技術の習得」が目的
• プログラムを作ることは要求する。それは、
「アルゴリズム」や「データ構造」が正しく実現
されているか、という検証のため
5
たとえて言えば…
入力
例えて言えば、
アルゴリズムは料理のレシピ
出力
6
例えて言えば...
• アルゴリズムは料理のレシピ
入力 ... 料理の材料 (小麦粉、キャベツなど)
出力 ... 料理 (お好み焼き、カレーライスなど)
料理を作るには材料をどんな手順でどのように調
理するか、が必要 ... アルゴリズム
• データ構造は、料理のための道具
• レシピが読めても、料理を作れないのでは意味がな
い!⇒ ちゃんと動くプログラムを書けなければ意味
がない。。。さらに効率性も大事。。。
7
アルゴリズムの例
入力
• 問題(教科書p.1): n個の実数x1, x2, …, xnが
与えられて、その中の最大値を求める
出力
• 素朴版(p.1)
x1, x2, …, xnを順にみていく。その途中でいつ
も、「それまでに見た数の最大値」を覚えてお
く。最後まで見終わったとき、「それまでに見
た数の最大値」が求めるべき最大値
8
アルゴリズムの例(続)
• より明確な記述(p.2)
入力: 正の整数nとn個の実数値x1, x2, …, xn
出力: x1, x2, …, xnの中の最大値
手続き:
「変数y に x1の値を代入する」
1. y ← x1 (yは「それまでの最大値」を記録)
2. i = 2,3,…,nに対して順に次を行う:
xi > y ならば y ← xi
3. yを出力する
9
アルゴリズムの例(続)
MAXはアルゴリズムの名前。続けて、入
力である「引数」を書く。だからnが必要
• 「プログラム」風(p.3)
Algorithm MAX(n, x1, x2, …, xn):
入力(Input): 正整数 n と n 個の実数x1, x2, …, xn
出力(Output): x1, x2, …, xnの中の最大値
記法の注意:ここではプログラムの
手続き(Procedure):
命令の後に「;」を書く
1. y ← x1 ;
ここでの記法についてはウェブページの
「教科書のアルゴリズムの記述とRUBY言
2. for i ← 2 until n do
語の対応」参照
if xi > y then y ← xi ;
アルゴリズムにおいて「出力する」とは、
printするという意味でなく、returnによって
3. return y;
値を「返す」ということ
10
アルゴリズムの検証
•このアルゴリズムがちゃんと動くかは
(1)頭で考え、手を動かす
(2)アルゴリズムを反映したプログラムを作り、
適切な入力を与えて動かし、結果を調べる
ことで検証する、つまり、正しいかどうかを確認
する
11
アルゴリズムからRubyプログラムへ
• 2ページと3ページのどちらの記述でもよいが
それに基づいてRubyプログラムを書く
• それにはRuby言語の書き方を知らないとい
けない…(君たちはちゃんと覚えていると信じ
たい!)
12
データ構造の出番
•「入力:正整数 n と n 個の実数x1, x2, …, xn」
の中の n 個の実数x1, x2, …, xn
をRubyのプログラムでどのように表現するか?
「標準的」とは、よく用いられる、という意味
複数個の実数を「まとめて」表すための標準的
な方法は「配列」というデータ構造を使うこと
このように、いくつかのオブジェクトをまとめて記憶する
データ構造を「入れ物」と呼ぶことがあります
ところで、Rubyの配列って?
13
Rubyの配列
Rubyでは『オブジェクト』
という概念が重要。数も
文字列もオブジェクト
• 配列とは:変数は一個のオブジェクト(物)しか
記憶できないが、配列は複数のオブジェクト
を記憶する
• 書き方:オブジェクトをカンマで区切って並べ、
全体を大括弧でくくる。
例: [ 1, 2, 3, “a”, “ab”, “abc” ]
• Rubyでは、配列はArray(アレイ)と呼ばれる
オブジェクト
14
Rubyの配列(続)
• 配列自体が一つのオブジェクトなので、これ
を変数の値とすることができる。
例: x = [ 1, 2, 3, “a”, “ab”, “abc” ]
• 配列の要素の値を調べる(取り出す)には…
配列[インデックス]
「インデックス」とは、配列における要素の位置を表す数のこと。
先頭の要素のインデックスが0、次が1、…となる。
15
Rubyの配列(続)
x = [ 1, 2, 3,“a”,“ab”,“abc” ]
とすると、xの値となっている配列に対し、
インデックスが3の要素は…
“abc”のインデックスは…
試してみよう。
x[3] この他にも x[0], x[5], x[6], x[-1] など
[ 1, 2, 3,“a”,“ab”,“abc” ][3]
16
Rubyの配列(続)
• 配列の大きさ:配列の要素の数はどうやって
分かる?
size (もしくは length)
というメソッドを使う
メソッドとは、オブジェクトに対する操作の
こと。関数ともいう。オブジェクトによって
いろいろなメソッドが用意されている。
試してみよう。
x.size
[ 1, 2, 3,“a”,“ab”,“abc” ].length
17
配列を使ったプログラム
• 問題1.変数aには配列が値として入っている。
たとえば、 a= [ 1, 2, 3,“a”,“ab”,“abc” ]
ここで、a[1]とa[2]の値を取り換えるコード(プ
ログラムの断片)は?
• 問題2.変数aには配列が値として入っている。
aの偶数番目の要素と奇数番目の要素をす
べて取り換えるコードは?
たとえば、 a= [ 1, 2, 3,“a”]ならa= [ 2,1, “a”,3]となる
18
アルゴリズムからRubyプログラムへ
(続き:代入と配列の使用)
• 入力は、変数nとxとする。
ただし、nの値は正整数、 Algorithm MAX(n, x1, x2, …, xn):
入力(Input): 正整数 n と n 個の実
xの値は実数を要素と
数x1, x2, …, xn
出力(Output): x1, x2, …, xnの中
する配列
の最大値
• 手続きの最初をRubyで 手続き(Procedure):
1. y ← x1 ;
2. for i ← 2 until n do
書くのは簡単…
if xi > y then y ← xi ;
3. return y;
y = x[1]
実はこれだと問題があるが、今はこれで進める
19
アルゴリズムからRubyプログラムへ
(続き:繰り返し)
• 2番目の手続きは「繰り
返し」
Rubyには、『繰り返し』の
メソッドはいろいろある:
while, for, downto, times,
… (適切なものを選べる
ようにしよう!)
ここではforを使うのが適切
書き方: for i in 2..n
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;
実はこれだと問題があるが、今はこ
れで進める
繰り返される処理
end
20
アルゴリズムからRubyプログラムへ
(続き:条件分岐)
•「繰り返される処理」は
Algorithm MAX(n, x1, x2, …, xn):
正整数 n と n 個の実
ここでは「条件分岐」である。入力(Input):
数x1, x2, …, xn
出力(Output): x1, x2, …, xnの中
Rubyの条件文の書き
の最大値
方:
手続き(Procedure):
if (条件式)
「条件式が成り立つ時の処理」
else
「条件式が不成立の時の処理」
end
1. y ← x1 ;
2. for i ← 2 until n do
if xi > y then y ← xi ;
3. return y;
elseと「条件式が不成立の時の処理」は、なくても可
21
アルゴリズムからRubyプログラムへ
(2番目の処理のまとめ)
• 2番目の処理をまとめ
ると以下のように書け
る:
for i in 2..n
if (x[i] > y)
y = x[i]
end
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;
22
アルゴリズムからRubyプログラムへ
(3番目の処理)
•3番目の return y はyの値を返すも
の。
•でも、どこに返すのか?
•ここでの選択
(1) 画面に表示する(printを使う)
(2) アルゴリズムMAXの結果とし
て返す
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;
ここでは(2)を考える。
でも、「アルゴリズムMAXの結果とし
て返す」とはどういうこと?
23
アルゴリズムからRubyプログラムへ
(関数/メソッド)
•「アルゴリズムMAXの結 Algorithm MAX(n, x1, x2, …, xn):
入力(Input): 正整数 n と n 個の実
果として返す」とは、
数x1, x2, …, xn
x1, x2, …, xnの中
Ruby の関数(メソッド)を 出力(Output):
の最大値
つくり、それにmaxと名を 手続き(Procedure):
1. y ← x1 ;
つけ、maxの関数の処理
2. for i ← 2 until n do
if xi > y then y ← xi ;
として1から3までの処理
3. return y;
をやらせるように書く、
ということ
Rubyでは関数名を大文字にできないのでmaxとする
24
アルゴリズムを関数として表現
関数: 入力を取り、それに基づいて一連の手続き
(計算)を行い、その結果を出力する(返す)、という
プログラムの単位
25
関数について
関数定義の引数(xとy)
は仮引数という。『定義』
のための仮のもの
• 関数名を func とすると
関数の定義の書き方:
def func(x,y)
… プログラム(「コード」とも)…
…どこかにreturn文が必要…
end
関数呼出の引数(3と5)
は実引数。計算に用い
関数の呼び出し:
られる実物。
ans = func(3,5)
26
関数の利点
• 一連の手続きに『名前』をつけ、入力と出力を
明示することで、その手続きが何をしているか
が明確になる
• プログラムを関数に分けることで、そのプログ
ラムの構造が明確になる
• 関数ごとにデバッグをすることで、誤りが発見
しやすい。また変更も容易になる
• 同じような処理をする場合に、冗長性が減る
• 『再帰』は関数を使わないと書けない
27
アルゴリズムからRubyプログラムへ
(完成)
• 関数は以下のようにdef を使っ
て定義する:
def max(n,x)
y = x[1]
for i in 2..n
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
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のプログラムでは、endがdefやforやifなど
と対応するため対応関係がわかりにくい。そこで、
インデント(段付け)をして対応が分かるように書く
28
実際に検証してみよう
• 先のプログラムは単に「アルゴリズム」をプロ
グラムに直しただけ。
• それがちゃんと期待通りに計算するかは、
(1) 具体的な(入力)データを与える
(2) アルゴリズムが返した結果を表示させる
ということが必要。
29
実際に検証してみよう(続き)
具体的には以下のようなプログラムを作る:
# maxアルゴリズムの検証
def max(n,x)
y = x[1]
for i in 2..n
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
# ここからが検証用のデータ
print max(10, [0.3, 0.1, 0.7, 0.9. 1.1, 0.2, 0.5, 0.8, 0.4, 1.0])
この内容をmax.rbとして、実行させてみると…
30
動かない…
• ちゃんと書いたはずなのだが、以下のような
エラーメッセージが出て動かない…
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
31
めげない!
• エラーメッセージに理由が書いてある。それを
読んで、理由を理解して、直してみよう。
• 講義用のウェブページにある「Rubyのエラー
メッセージとその対処 」を読んでみよう。
• これはそのうちのどこにあたるか?
32
プログラムの修正
• 「(5) 未定義(undefined)なメソッド(method)/関数
によるエラー 」に相当することが分かる
• 解釈:この場合は、5行目に使われている> という
「未定義なわけがない」演算子がやり玉にあがって
いる。 ここは、つまり「for nil:NilClass」が問題。つま
り「nil」には > が使えない、と言っている。
• 対処法:このようなエラーが起きるのは、配列の要
素の指定が間違っているか、要素の値の初期化(例
えば0にする)ことを忘れている場合が多い
33
プログラムの修正(続き)
• わかっただろうか?配列の要素の指定に問題があったので
ある。
• プログラムを見てみよう:
def max(n,x)
yに配列の先頭の要素を与えた「つもり」
y = x[1]
for i in 2..n
配列の2番目の要素から最後の要素ま
if (x[i] > y)
で、要素を一つ一つ調べている「つもり」
y = x[i]
end # if
Rubyの配列のインデックスは、いくつから始まり、いく
end # for
つが最後の要素をさすものだったかな?
return y
end # def
34
プログラムの修正(完成)
# maxアルゴリズムの検証
def max(n,x)
y = x[0]
for i in 1..(n-1)
if (x[i] > y)
y = x[i]
end # if
end # for
return y
end # def
# ここからが検証用のデータ
print max(10, [0.3, 0.1, 0.7, 0.9, 1.1, 0.2, 0.5, 0.8, 0.4, 1.0])
実行させた結果は…
35
参考
• プログラミング言語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));
}
36
練習問題(1)
• n個の実数x1, x2, …, xnが与えられて、その中
の最小値を求める
(1)アルゴリズムを書く
(2) プログラムを書く
(3) 適当なデータを与えて、プログラムを実行して
みる。そして最小値を返すことを確認する。
37
練習問題(2)
• n個の実数x1, x2, …, xnが与えられて、その中
の2番目に大きな数を求める
(1)アルゴリズムを書く
(2) プログラムを書く
(3) 適当なデータを与えて、プログラムを実行して
みる。そして最小値を返すことを確認する。
38
課題(1と2は提出を求める宿題)
• プログラムを書くために、Rubyを復習しよう
• 次の問題にチャレンジしてみよう
(1)最古のアルゴリズム(ユークリッドの互除法)をプ
ログラム化する
(2) ファイルから実数を読み込み、その中の最大値
を答える(つまり、数がファイルに書いてある)
(3) 最大値と最小値からなる配列を返す
(4) 最大値と最小値からなる配列を答えるだけでは
なく、それらが何番目の要素であるかも答える
宿題の提出期限は4月12日(月曜日)。あて先はウェブページ参
39
照
プログラム課題提出の注意
• (これこれの問題を解く)「プログラムを書け」、もしく
は「アルゴリズムを書け」という課題が多く出される
• この時に求められているのは「プログラム(やアルゴ
リズム)」だけではないことに注意
• 要求事項がちゃんと満たされていることも示す(検
証する)必要がある
• そのために、プログラムの中身、その実行例(複数
個の例題)、実行結果の吟味(ちゃんと目的を果たし
ているかどうか)を示す
40
ユークリッドの互除法
入力:正整数p, q
出力:pと q の最大公約数
手続き:
1. q > p ならば、 p と q の値を入れ替える
2. r ← (p の q による剰余)
3. r = 0 ならば、q が最大公約数(終了)
さもなくば、 p ← q, q ← r として、1へ。
p = 72, q = 30 として、試してみよう
41
基本的な用語の確認
整数xが整数aの約数 ⇔ aがxで割り切れる
• aとbの公約数: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とbの最大公約数(GCD):aとbに共通する公
約数のうち最大のもの
30と72の最大公約数(これをGCD(30,72)と書く)
は…
42