アルゴリズムとデータ構造 1章の復習 第2章 リスト構造 ５月10日 アルゴリズムとデータ構造 1章の復習 第2章　リスト構造 ５月10日 情報知能学科 白井英俊 1

計算量：時間と空間 時間計算量、もしくは時間複雑度(time complexity) そのアルゴリズムを実行するのに、最悪の場合、どのくらい時間がかかるかを、入力の大きさの関数として表す 空間計算量、もしくは空間複雑度(space complecity) 　　　そのアルゴリズムを実行するのに、最悪の場合、どのくらい記憶領域が必要かを、入力の大きさの関数として表す 計算量（複雑度）＝時間計算量＋空間計算量 2

時間計算量の常識的な評価 教科書p.8 O(1) --- 理想的に速い O(log n) --- 非常に速い O(n) --- 速い O(n log（n)) --- 速いほう O(n2) --- かなり遅いが、許されないほどではない O(n3) --- かなり遅い。許される限界。 O(cn ) --- (cは1より大きい定数）。指数オーダ(exponential order)。とっても遅い。 3

計算量の演習1 教科書p.11 1.1 次の5種類の計算時間を、nを横軸にとって、一つのグラフに重ねて表せ。そして、そのグラフからオーダの大小関係が読み取れることを観察せよ。 f1(n) = 10000 n f2(n) = 10000 n log(n) f3(n) = １00 n**2 f4(n) = 10 n**3 f5(n) = 2**n 実際にグラフを書く前に、 これらのオーダがどうなるか 考えておいてください 4

計算量の演習1の解答 GnuPlotを用いる。ただし、ｘをnと「読み替える」 (1≦x≦30 のグラフ。x=30では f5 > f2 > f1 > f4 > f3のように見えるが…）

計算量の演習1の解答(続) f5を除いて3000まで表示させると、 f4 > f3 > f2 > f1 となる ことが分かる

計算量の演習1 の解答(まとめ) つまり、nが十分大きければ、 　　　　　　n < n*log(n) < n2 < n3 < 2n であることが分かる f1(n) = 10000 n　　　 オーダ：O(n) f2(n) = 10000 n log(n) O(n log(n)) f3(n) = １00 n**2 O(n2 ) f4(n) = 10 n**3 O(n3 ) f5(n) = 2**n O(2n ) 7

計算量の演習２ 教科書p.11 1.2 ステップ数が f(n)=100000n, g(n)=10n**3, h(n)=2**nの3つのアルゴリズムにn=100の大きさのデータを与えたとする。1ステップが10**(-9)秒で実行できるコンピュータで走らせたときの計算時間は次のどれに近いか？ 1ミリ秒、1秒、1分、1時間、1日、1ヶ月、1年、1世紀 8

計算量の演習２の解答 問題：ステップ数がf(n)=100000n, g(n)=10n**3, h(n)=2**nの3つのアルゴリズムにn=100の大きさのデータを与えたとする。 1ステップが10**(-9)秒で実行できるコンピュータで走らせたときの計算時間は？ 答え： f(100)=100000*100 = 107 g(100)=10*100**3 =107 1ステップが10-9秒なので、f もgも107*10-9 =1*10-2秒 (10ミリ秒) h(100)=2**(100) ≒ 1030 1ステップが10-9秒なので、h(100)*10-9 ≒ 1030*10-9 =1*1021秒 1年＝60*60*24*365≒ 3.2*107 秒, 1世紀=100年=3.2*109秒 210 =1024 ≒103　 だから2100=(210)10= (103)10

計算量の演習３ 教科書p.11 1.4 次の式のオーダを、最も忠実で簡単な式を用いて表せ。 (1) 6.5n3 + 8n2 + 5 (2) 5 n log(n) + 3 n2 (3) 2.5 n √n + 3.6 n log(n) (4) 5 n + 8 log(n) (5) 2n + 5 n 5 (6) 800 n log(n) + n 10

計算量の演習３の解答 問題： 次の式のオーダを、最も忠実で簡単な式を用いて表せ。 (1) 6.5n3 + 8n2 + 5 問題：　次の式のオーダを、最も忠実で簡単な式を用いて表せ。 (1) 6.5n3 + 8n2 + 5 (2) 5 n log(n) + 3 n2 (3) 2.5 n √n + 3.6 n log(n) (4) 5 n + 8 log(n) (5) 2n + 5 n 5 (6) 800 n log(n) + n 注意：2nのような「２」は定数倍ではない。nの関数に『掛け算』されている『数』が無視の対象 解法： (1)定数倍を無視 (２)最も大きくなるnの項だけを残す

計算量とオーダ ここまでで何か質問は？ アルゴリズムが与えられた時に、『計算量』を求めることは、5章に入ったら…

４月の講義のまとめ 「アルゴリズム」 「アルゴリズム」の計算量 時間複雑度、空間複雑度 オーダ　：　log(n), n, n*log(n),n**2, n**3, 2**n, n! 「アルゴリズム」をプログラムとして実現することにより、アルゴリズムの検証を行う　ー　プログラムを書くだけではなく、いろいろな例で実験する そのために、Rubyの復習が必要（代入、条件分岐、繰り返し、変数／定数、配列、クラス） アルゴリズムをプログラムとして実現する 再帰関数：プログラムを書く、プログラムを読む（動きを追う）

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

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

アルゴリズムの例（続) このような記法のアルゴリズムから プログラムを実現できるように！ 「プログラム」風(p.3) MAXはアルゴリズムの名前。カッコのなかは入力「引数」を書く。 「プログラム」風(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言語の対応」参照 このような記法のアルゴリズムから プログラムを実現できるように！

新しい概念：ポインタ(pointer) ポインタの元々の意味は「指さし」。 「変数」の役割は、 「オブジェクトを指す」 　（オブジェクトを「値」として持っているわけではない） 　　例えば、変数xに配列[1,2,3] を代入したとする。 　　その結果、「変数」の値として配列[1,2,3]が入るのではなく、配列そのものは別の場所に作られ、その場所への『手がかり』が「変数の値」になる。 　　　このような手がかり(記憶番地、アドレス)をポインタという。 　　　Rubyの変数の『値』は、みなポインタ 参考: プログラミング言語Cでは、int *x のように書いて、変数xは、整数オブジェクトへのポインタ(アドレス)を値とする、というように宣言する 17

ポインタの詳細 記憶場所b 記憶場所a 変数名 x アドレス（記憶番地）：コンピュータの記憶場所 　ここでは少し拡張して「データの格納場所の手がかり」（場所の情報）と考える 例：　配列を変数に代入 記憶場所b 記憶場所a 変数名 配列：かなりの場所を必要とする複雑なデータ x アドレス 18

ポインタによる説明 5 [ , 3 ] 1, 2 x = [1, 2, 3] x y = x x[1] = 5 y コンピュータの内部： x = [1, 2, 3] x xの記憶場所 y = x 5 x[1] = 5 y yの記憶場所 p y => [1,5,3] x.shift [ , 3 ] 1, 2 配列： p y => [5, 3] 注意：本当は「配列」は、かなり複雑な形をしているのだけど、簡略化しています

クラスとインスタンス Rubyのオブジェクトには 数、文字列、配列、…などがあった これは、プログラミング言語としてはかなり豊か 　数、文字列、配列、…などがあった これは、プログラミング言語としてはかなり豊か これらを使いこなせば、いろいろなことができる。でも… 問題に適したデータ構造を考えないといけないことがある。 そのために、クラス定義とインスタンス生成の方法は知っておかないといけない （本講義では　これから多用します） 20

Rubyにおけるクラス定義 オブジェクト指向 プログラムが扱うデータ（オブジェクト）と、それをどのように扱うかという手続き（関数）とを「組」として表す クラスーオブジェクトの「種類」 クラス定義 1) どのようなパーツ（部品）があるかを宣言：インスタンス変数 　 2) 手続き（関数)の宣言：インスタンスメソッド

クラス定義の例 部品名 名簿の一つの項目を「クラス」として定義する 名簿の項目(Item)には、(少なくとも)次のパーツ（部品)をもつと考えられる 1)名前　 2)住所 3)生年月日 4)性別 5)年齢 name address birth_date sex age これを図示すると… クラス名 Item name address birth_date sex age 具体的な値がはいる（ポインタ) 部品名

クラス定義の例(続) 右に図示した名簿の項目(Item)に対応した「クラス」: Item class Item 　　def initialize(n,a,b,s) @name = n @address = a @birth_date = b @sex = s @age = Time.now.year - b end Item name address birth_date sex age 大文字から始める Initialize は重要なインスタンスメソッド。「インスタンス」作成の時に説明 @つきの変数が「インスタンス変数」 これが「パーツ（部品）名」になる

クラス定義の例(続) ただ、このままだと、部品にアクセス(取り出し、参照)しにくいので… class Item def initialize(n,a,b,s) @name = n @address = a @birth_date = b @sex = s @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age Item name address birth_date sex age attr_accessor につづけて インスタンス変数名の前にコロン( : )

インスタンス生成 鯛焼きを食べるには、「材料を用意して、鯛焼きを作る」必要がある。 それをするのが、「インスタンス生成」 　　インスタンス生成 鯛焼きに例えて言えば、 クラス定義は、鯛焼きを焼く金型(鉄板) これだけでは、鯛焼きは食べられない… 鯛焼きを食べるには、「材料を用意して、鯛焼きを作る」必要がある。 それをするのが、「インスタンス生成」 「Taro Yamada」の名簿項目を作る: 　　Item.new(“Taro Yamada”, “Toyota”, 1990, “male”) 注：ここでは、生年月日ではなく「生まれた年（西暦）」としよう

インスタンス生成(続) Item.new (“Taro Yamada”, “Toyota”,1990, “male”) これにより、initializeメ ソッドが呼び出される class Item def initialize(n, a, b, s) @name = n @address = a @birth_date = b @sex = s @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age その引数の n, a, b, sがそれぞれ　Item.new　の実引数と結び付けられ、 次に 　の文が実行 されて、次に示すようなItemクラスのインスタンスができあがる:

インスタンス生成（完成) Item.new(“Taro Yamada”, “Toyota”,1990, “male”) name address birth_date sex age “Taro Yamada” “Toyota” 1990 “male” ２０ 注：Time.now.year が2010を返すとすれば

演習1：クラスとインスタンス 注：補助資料を参照してください： 演習1.１．Itemクラス定義を用いて、以下の例を参考に、自分に当てはめて名簿項目(Itemインスタンス)を生成せよ（注意：女性の場合、性別は”female”） mydata = Item.new(“Taro Yamada”, “Toyota”, 1990, “male”) 演習1.２．上を実行後 mydata.age の値を表示させよ。 演習1.3. さらに　mydata.age = ３0 を実行させた後の　mydata.birth_date と mydata.age の値を表示させよ。

クラス定義（追加）：インスタンスメソッド そのインスタンスだけに適用される関数(メソッド)の定義： class Item 　　def initialize(n,a,b,s) @name = n ; @address = a @birth_date = b ; @sex = s @age = Time.now.year - b end attr_accessor :name, :address, :birth_date, :sex, :age def show(sep = “, ”) return “Name: “+@name+sep+” Sex: “+@sex+sep+”Age: “+@age 注：(sep=“,”)　は、メソッド(関数)の引数が省略できること、また省略された場合に”,”が値となることを表すRubyの記法

演習2：クラスとインスタンス 注：補助資料を参照してください： 演習２(発展)： 　(1) 複素数を表すクラスを定義せよ。そのクラスの名前を Complex とし、パーツは二つ、 real (reと略す、実部)　と imaginary (im と略す、虚部)。 (2) 補助資料の例にならって、複素数同士の引き算と割り算をするメソッドを付け加えよ。 (3) インスタンスを2つ以上つくり、計算がちゃんと行われることを確かめよ。

複素数について 2つの複素数を (a+bi), (c+di)とすると(a,b,c,dは実数, iは虚数) 足し算： (a+bi) + (c+di) = (a+c) + (b+d)i 引き算： (a+bi) - (c+di) = (a-c) + (b-d)i 掛け算： (a+bi) * (c+di) = (a*c - b*d)+(b*c + a*d)i 割り算： (a+bi) / (c+di) = (a*c + b*d)+(b*c - a*d)i c2 + d2 c2 + d2 参考： (a+bi) (a+bi) (c - di) (a*c + b*d) (b*c -a*d)i (c+di) (c+di) (c - di) c2 + d2 c2 + d2 (c –di)は(c+di)の共役複素数 * +

… （予習)リストの必要性とポインタ 名簿のような｢表｣を記憶することを考える 　　普通の方法：　1行分記憶するのに必要な記憶の大きさをkバイトとして、コンピュータ上に固定した記憶場所を確保して使う 1行k バイト k 2k …

リストの必要性とポインタ（続） 表方式の特徴：検索が容易 n件目のデータは、n*k～(n+1)*k-1の範囲に入っている 表方式の欠点：データの削除や挿入の手間が大きい 　　例：1番目のデータを削除したら、その後のデータをすべて一行ずつ前に移動しなければならない

リストの必要性とポインタ（続） リスト（線形リスト）：表方式の欠点を解消 リスト(線形リスト）の基本単位：セル(Cell) データの挿入、削除の手間が軽減 　ただし、記憶場所が多く必要、データの検索(アクセス）の手間がかかる、という欠点あり リスト(線形リスト）の基本単位：セル(Cell) data データ部 next ポインタ データ部：　データの記憶用 ポインタ部：別なセルのアドレス

セル(Cell) 線形リスト構造を表現する基本単位セル 　例えて言えば、連結器つきの車両 　つながったセルの図