2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊

Slides:



Advertisements
Similar presentations
データ構造とプログラミング技 法 (第3回) ー木構造ー. 木構造 (1) 根( root )と呼ばれる節 R が、 1 つだけ含まれ る。 R … TmTm T1T1 木構造: 1 個以上の節の有限集合 T であり、 次の二つの条件を満足するもの (2) 根以外の節は、 m (≧ 0 )個の互いに素な部.
Advertisements

区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
4.3 マージソート.
基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
離散システム特論 整列(sorting)アルゴリズム 2.
アルゴリズムイントロダクション第2章 主にソートに関して
アルゴリズムとデータ構造 第8回 ソート(3).
プログラミング言語としてのR 情報知能学科 白井 英俊.
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 第2章 リスト構造 5月17日分
算法数理工学 第1回 定兼 邦彦.
実行時のメモリ構造(1) Jasminの基礎とフレーム内動作
情報知能学科「アルゴリズムとデータ構造」
プログラミング論 I 関数の再帰呼び出し
第10回 ソート(1):単純なソートアルゴリズム
アルゴリズムとデータ構造 2012年6月14日
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
情報処理Ⅱ 2005年12月9日(金).
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
アルゴリズムとデータ構造 2011年6月14日
二分探索木によるサーチ.
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造1 2006年6月16日
二分木のメソッド(続き).
プログラミング2 関数の再帰呼び出し
2011/06/21-24 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊
アルゴリズムとデータ構造勉強会 第6回 スレッド木
情報工学概論 (アルゴリズムとデータ構造)
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
第3回 アルゴリズムと計算量 2019/2/24.
データ構造とアルゴリズム (第3回) ー木構造ー.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
大岩 元 慶応大学環境情報学部 再帰 データ構造とプログラミング(8) 大岩 元 慶応大学環境情報学部
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
離散数学 07. 木 五島.
Cプログラミング演習 第10回 二分探索木.
関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題
プログラミング 4 整列アルゴリズム.
アルゴリズムとデータ構造 2010年7月26日
アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量
プログラミング 4 探索と計算量.
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造 2011年7月8日課題の復習
アルゴリズムとデータ構造1 2006年7月11日
プログラミング演習Ⅲ- Sorting Quick Sort and Merge Sort
15.cons と種々のデータ構造.
アルゴリズムとデータ構造 第2章 リスト構造 5月20日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
情報知能学科「アルゴリズムとデータ構造」
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
アルゴリズムからプログラムへ GRAPH-SEARCH
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2013年7月1日
情報工学概論 (アルゴリズムとデータ構造)
PROGRAMMING IN HASKELL
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
ヒープソート.
PROGRAMMING IN HASKELL
プログラミング2 関数の再帰呼び出し
プログラミング演習I 2003年6月11日(第9回) 木村巌.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊 5章 再帰呼出しと分割統治 杉原厚吉.(2001).「データ構造とアルゴリズム」. 東京:共立出版. 2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊

本章の目的 問題の性質を見極めて、「複雑な問題を、より単純な小問題に分割して解く」ことを学ぶ 効率は『計算量』だけではない。問題を解くための考えやすさ、分かりやすさも大事 複雑な問題を分割して解くことの代表的なものが再帰 ― 小問題が大問題の類似形の場合に有効 分割することで効率が悪くなることもある!

5.1 再帰呼び出し 再帰呼び出し(recursive call) ― 手続き(関数)の中で自分自身(その関数)を呼び出すこと 5.1 再帰呼び出し 再帰呼び出し(recursive call) ― 手続き(関数)の中で自分自身(その関数)を呼び出すこと 特長:ある種の手続きを簡潔に表現できる 特に、問題自身が再帰的な場合に有効 例: 二進木のなぞり :「二進木」は『左の部分木』、と『右の部分木』に分かれる。だから、木を中間順 (inorder)になぞるには、    (1)左の木をinorderでなぞる、(2)木の根を表示する、    (3)右の木をinorderでなぞる、 とすればよい。   これは、「左の木」も「右の木」も、木全体の類似形だから、再帰を使うのが有効

中間順による二進木のなぞり:inorder関数  この前は「インスタンスメソッド」として実現。今度は二進木のインスタンスを引数とする「関数」として実現することを考える  再帰の場合、『どのような場合に再帰しない(停止する)か』という検査を最初に実行(参考:数学的帰納法) def inorder(tree) if (tree != nil) # tree==nilなら再帰しない inorder(tree.left) # 左の部分木を中間順で print tree.data # 頂点のデータを表示 inorder(tree.right) # 右の部分木を中間順で end # if end # def インスタンスメソッドとの比較: (1)「木」を表す引数が必要  インスタンスメソッドでは   不要(@selfと同じだから) (2) インスタンスの部品(イン スタンス変数)の参照方法   @data, @left, @right

インスタンスメソッドと「関数」 インスタンスメソッド class Vertex def initialize(data, left, right) @data = data @left = left @right = right end # initialize attr_attribute :data, :left, :right def inorder   @left.inorder if @left != nil  print @data @right.inorder if @right != nil  end # def of inorder end # class インスタンスメソッドの呼出し: xをVertexのインスタンスとすると x.inorder xのクラスに付随するメソッドinorder が呼び出される それに対し 関数としてのinorderの 実現では、Vertexのインス タンスを引数して呼出す: inorder(x)

中間順による木のなぞり(関数版) inorder(1) 実行結果 1 inorder(2) 2 3 4 5 6 7 8 9 10               1           2          3       4      5    6    7     8   9  10 に対して: inorder(1) ② ③ inorder(2) ① print(1) ② inorder(3) ① ③ ② ③ inorder(6) inorder(4) ① print(2) print(3) inorder(5) inorder(7) inorder(10) inorder(8) print(4) print(5) inorder(9) 8 4 9 2 10 5 1 6 3 7

先行順による木のなぞり 先行順(頂点、左の部分木、右の部分木) def preorder(tree) 同様に、関数として実現することを考える if (tree != nil) # tree==nilなら再帰しない print tree.data # 頂点のデータを表示 preorder(tree.left) # 左の部分木をpreorderで preorder(tree.right) # 右の部分木をpreorderで end # if end # def

先行順による木のなぞり 2 3 4 5 6 7 8 9 10 実行 1 に対して: 1 2 4 8 9 5 10 3 6 7 ① ③ ① ② 実行           1           2        3       4      5   6   7   8   9  10 に対して: ③ ① ② ① ③ ② ① ② ③ ② 1 2 4 8 9 5 10 3 6 7

後行順による木のなぞり 後行順(左の部分木、右の部分木、頂点) def postorder(tree) これも、関数として実現することを考える 後行順(左の部分木、右の部分木、頂点) def postorder(tree) if (tree != nil) # tree==nilなら再帰しない postorder(tree.left) # 左の部分木をpostorderで postorder(tree.right) # 右の部分木をpostorderで print tree.data # 頂点のデータを表示 end # if end # def

後行順による木のなぞり 2 3 4 5 6 7 8 9 10 実行 1 に対して: 8 9 4 10 5 2 6 7 3 1 ③ ① ② ③ 実行           1           2        3       4      5   6   7   8   9  10 に対して: ① ② ③ ② ③ ① ② ① ① ② 8 9 4 10 5 2 6 7 3 1

応用:数式の構文木 例: (a+b)*(c-d*e) は次の二進木で表現される(葉には変数が、葉以外の頂点は演算子が書かれる) これを数式の「構文木」 と呼ぶ。数式の構造 (どこの塊同士がどのような 演算によって結合されてい るか)が明示されている * + ー a b c * d e

数式の構文木の演習 * ー + c a b d e 先の木を 1) 中間順(inorder) 2) 先行順(preorder)   3) 後行順(postorder)  でそれぞれなぞると… 参考:ポーランド記法、逆ポーランド記法 * ー + c a b d e

数式の構文木の演習(解) 日本語的! (a+b)*(c-d*e) の構文木を以下の方法でなぞると: 1) 中間順(inorder)  2) 先行順(preorder): 数式のポーランド記法 * + a b – c * d e  3) 後行順(postorder): 逆ポーランド記法   a b + c d e * – * 日本語的!

2進木以外の「木のなぞり」 「先行順」と「後行順」による木のなぞりは、2進木でなくとも使える(中間順も無理すればできなくはない)

一般の木の表現 一般の木構造を次のようなデータ構造(ノードと呼ぶ)で表す class Node    一般の木の表現 一般の木構造を次のようなデータ構造(ノードと呼ぶ)で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end @parent @firstChild self @nextBrother 注意:枝の向きが明らかな場合は矢印を省略する

木の表現(続) クラスNodeを図示すると、次のようになる 頂点 親頂点 兄弟頂点 子頂点 label (ラベル) parent (親) 一個一個が以下の構造をもつ 親頂点 label (ラベル) parent (親) firstChild(第一子) nextBrother(次の兄弟) @parent @firstChild self @nextBrother 兄弟頂点 子頂点

NodeクラスとVertexクラスの比較 class Node      # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother)    @parent = parent     # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def  initialize end 頂点のラベル(値) class Vertex   # 2進木用の頂点を表現するクラス    def initialize(data, left ,right)   @left = left  # 左の部分木   @right = right # 右の部分木   @data = data # 頂点の値   end # def initialize end # class 子の頂点

一般の木のなぞり ある頂点 n からみると 子の頂点すべてを取り出すことは、すぐにはできない class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end ある頂点 n からみると  子の頂点すべてを取り出すことは、すぐにはできない  比較:二進木では子の頂点は左と右だけで、それぞれ@leftと@rightで取り出せた 最初の子しか見えない だから、「木をなぞる」には、「子頂点をすべて取り出す」ためのしかけが必要 それには、「次の兄弟」を使う!

一般の木において子頂点をすべて表示する:「木のなぞり」の準備 右の木を例にとって考える。 v0を対象とすると、その「子」は どのようにしたら取り出せるだろ うか? 例題の木 v0 v1 v3 v2 答え: v0.firstChild = v1 v6 v5 v4 v0.firstChild.nextBrother v1 @parent @firstChild self v0.firstChild.nextBrother.nextBrother v1 Nodeクラス ある頂点の「兄弟」頂点をすべて取り出す インスタンスメソッドがほしい! @nextBrother 子頂点=最初の子(s)+sの「兄弟」頂点

兄弟頂点を訪問するメソッド class Node # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother)    @parent = parent     # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def  initialize   attr_accessor :parent, :firstChild, :nextBrother, :label def brothers return if (@nextBrother == nil) # 次の兄弟がいない場合 print @nextBrother.label @nextBrother.brothers      # 次次と兄弟を訪問 end

参考:先祖の頂点を要素とする配列を求める 右の木を例にとって考える。v5を対象とすると、その「親」はどのようにしたら取り出せるだろうか? また「先祖」(親、親の親、親の親の親…)は? 例題の木 v0 v1 v3 v2 v6 答え: v5.parent = v1 v5 v4 v5.parent.parent = v0 @parent Nodeクラス ある頂点の「先祖」頂点とは、 (1) (親がいれば)親 、に加えて (2) 親の「先祖」頂点 self @nextBrother @firstChild

先祖の頂点の配列を求める(続) class Node # 一般の木の頂点を表現するクラス def initialize(label, parent, firstChild, nextBrother)    @parent = parent     # 親ノード @firstChild = firstChild # 第一子 @nextBrother = nextBrother # 次の兄弟 @label = label end # def  initialize   attr_accessor :parent, :firstChild, :nextBrother, :label def ancestors return [ ] if (@parent == nil) # 親がいない場合 # そうでなければ 親+親の先祖 を返す return [@parent]+@parent.ancestors  end

プログラミング演習 一般の木において(Nodeクラスを使用) treeTemplate.rb 参照のこと (1)先行順に木の頂点を訪れるインスタンスメソッド preorder (2) 後行順に木の頂点を訪れるインスタンスメソッド postorder を作る

再帰的な構造、効率の悪い問題 Hanoiの塔:再帰的な構造をしていて、計算量が大きな問題の典型例 詳しくは別紙の資料参照  詳しくは別紙の資料参照  (右図はWikipediaより拝借)  問題:n枚の円盤を3本あるうちの一つの柱から別な柱に移す手順を求める  入力:円盤の枚数、柱の名称(a,b,c) 出力:円盤を移す手順

プログラム Hanoi def hanoi(n,a,b,c) # n枚の円盤をaからcへ移す if (n==1) # 円盤が一枚ならば print ’move the disk from ’,a,’ to ’,c,”\n” else hanoi(n-1,a,c,b) # n-1枚の円盤をaからbに移す hanoi(n-1,b,a,c) # n-1枚の円盤をbからcに移す   end # if end # def

ハノイの塔の計算量 円盤をn枚移すのにかかる計算量を f(n) とすると、このアルゴリズムは f(n) = 2*f(n-1)+α という計算量が必要である。(円盤を1枚移す手間を定数「 α 」としている) したがって、f(n) は O(2n) これはアルゴリズムのせいではなく、問題自体が難しい(指数オーダーの計算量を必要とする)から =>アルゴリズムが簡潔に書けるからといって、そのアルゴリズムの効率がよいということにはならない g(n)=f(n)+αとすると、g(n)は2の等比数列

(予習)5.2 分割統治法 再帰呼び出しによる効率のよいアルゴリズムの例: マージソート(merge sort) (予習)5.2 分割統治法 再帰呼び出しによる効率のよいアルゴリズムの例: マージソート(merge sort) 入力: n = 2k (kは正整数)個の数の集合S(配列とする) 出力: Sの要素を昇順に並べたもの(配列とする) 手続き: |S|=2ならば、[min(S),max(S)]を返す   さもなくば、Sをn/2個ずつに分け、それぞれをマージソート(mergeSort)する。この二つの結果を、昇順に並べ(merge)、それを返す。 Sの最小要素 Sの最大要素

マージソートの実現(0) アルゴリズムから、mergeSortの全体像は: def mergeSort(s) n = s.size if (n == 2) # |S|=2の場合の手続きを書く---(1) else # それ以外の場合の手続きを書く---(2) end # if end # def

マージソートの実現(1) |S|=2のときに[min(S),max(S)]を返す def mergeSort(s) n = s.size これは簡単。条件文の使い方さえ分かっていれば… def mergeSort(s) n = s.size return s if n==1 # 一般性を考慮 if (n == 2) # s[0]とs[1]を比較して、 #  [小さい方の要素、大きい方の要素]  を返す else # 次で考える end # if end # def

マージソートの実現のために (1) |S|=2のときに[min(S),max(S)]を返す アルゴリズムを実現するには、以下の作業をするための「アルゴリズム」が必要: (1) |S|=2のときに[min(S),max(S)]を返す (2) Sをn/2個ずつに分け、それぞれをマージソート(mergeSort)し、二つのマージソートが返した結果を合わせて、昇順に並べる(mergeする)

マージソートの実現(2) def mergeSort(s) n = s.size return s if n==1 # 一般性を考慮 if (s.size == 2)        # できているはず…    else       mid = (n-1)/2 # 真中の要素の番号 x = mergeSort(s[0 .. mid]) y = mergeSort(s[(mid+1) .. (n-1)]) return merge(x,y) # xとyを合わせて昇順に end # if end # def 注:Rubyでは、配列xのインデックスi番目の要素から インデックスj番目の要素までを  x[i..j]  により配列として取り出せる

マージ(merge)とは? ・「再帰法」は、今作ろうとしている手続き(mergeSort)が小さな問題に対しては「ちゃんと正しい値を返してくれる」と考えて作る方法。だから、以下は「ソートされた数の配列が返されると仮定してよい」:   mergeSort(s[0..mid])  # 配列sの前半 mergeSort(s[(mid+1)..(n-1)]) # 配列sの後半 とすると、考えなければならない問題は、返した結果を合わせて、昇順に並べる方法

マージ(merge) つまり mergeSort(s[0..mid]) mergeSort(s[(mid+1)..(n-1)]) は、それぞれソートされた配列を返す。 例: [1,3,5,9,11,15,18,20]   [2,4,6,8,10,12,14,16] マージ(merge)は、この二つを入力として、 [1,2,3,4,5,6,8,9,10,11,12,14,15,16,18,20] というような昇順の配列を返す関数

マージ(merge)関数を作る def merge(x,y) result = [ ] # マージした結果の記録用 xlen = x.size ‐1; ylen = y.size ‐1 # xとyの最後の要素のインデックス xc = 0; yc = 0 # xとyそれぞれ「見る」要素の番号 while (xc <= xlen && yc <= ylen ) # 未検査要素あり # x[xc]とy[yc]を比較しresultに入れるなど # 適切なプログラムを書く end # while # xかyに未検査のものがある場合の処理を書く end # def

マージソートの完成 mergeとmergeSortをちゃんと書くことができれば、次のような結果が得られるだろう:   (mergeSortTemplate.rb参照)ーーー課題  mergeSort([20, 10, 5, 15, 3, 7, 13, 18, 2, 6, 4, 1, 19]) の出力結果: [1, 2, 3, 4, 5, 6, 7, 10, 13, 15, 18, 19, 20]

分割統治法 入力データの大きさをnとすると、そのデータを大きさ n/b の問題 a 個に分割し、それぞれを再帰的に解いた結果を利用して、元の問題の解を作るという方法(教科書、p.51)で、かつ  計算時間 f(n) が n=1の時、 f(n) = c (cは定数) n ≧2の時、 f(n)=a*f(n/b) + cn (a,b,cは定数)  となるもの(マージソートでは a=b=2)

ハノイの塔とマージソートの比較 ハノイの塔は再帰法を使っていても、その計算量は O(2n) マージソートでは、O(n*log n) この違いは何か? 答え:  元の問題に対し、一定の比で小さな問題にして解く(マージソート)か、一定の差で小さな問題にして解く(ハノイの塔)か。(p.53-54)

再帰呼出しを使わない方がよい例 フィボナッチ数列(Fibonacci sequence) 定義: 非負整数nに対するフィボナッチ数F(n)とは     n=0 または n=1のとき、1    それ以外: F(n) = F(n-1)+F(n-2)  この形から、「ハノイの塔」タイプであることが明らか

フィボナッチ数F(n)を求める 先の定義を単純にプログラムすると以下のとおり: def fibo1(n) if (n==0 || n==1) return 1 else return fibo1(n-1)+fibo1(n-2) end # if end #def

フィボナッチ数F(n)の別な求め方 実は再帰を使わず、F(1),F(2),F(3),… の順にF(n)まで計算すれば、ずっと効率がよい     …計算量のオーダーはO(n) def fibo2(n) return 1 if (n==0 || n==1) x = 1; y = 1 for i in 2..n z = x+y ; x = y; y = z end # for return z end # def 昨年の教科書を使っている人に:アルゴリズム FIBO2(p.54)の1行目を訂正

実は。。。 教科書p.56にあるように、フィボナッチ数F(n)はO(log n)で求めることができる。