論理と計算（２）

Size: px

Start display at page:

Download "論理と計算（２）"

なごみふじした
4 years ago
Views:

1 情報科学概論 Ⅰ アルゴリズムと計算量亀山幸義亀山担当分の話題アルゴリズムと計算量 Fibonacci 数列の計算を例にとりアルゴリズムと計算量とは何か具体的に学ぶ良いアルゴリズムの設計例として整列 ( ソーティング ) のアルゴリズムを学ぶ 2 Fibonacci 数 () Fibonacci 数 (2) = if n =, 2 Fib(n-2) + Fib(n-) if n > 2 = if n =, 2 Fib(n-2) + Fib(n-) if n > 2 Fib() = Fib(2) = Fib(5) = 5, Fib(6) = 8, Fib(7) = 3, Fib(3) = Fib() + Fib(2) = + = 2 Fib(0) = 55, Fib(20) = 6765, Fib(4) = Fib(2) + Fib(3) = + 2 = 3 Fib(30) = Fibonacci 数を求める () Fibonacci 数を求める (2) n =, 2 = Fib(n-2) + Fib(n-) n > 2 class Fib { public static int fib (int n) { if (n < 3) return ; else return (fib(n-2) + fib(n-)); Javaプログラム public static void main (String args[]) { int n = Integer.valueOf(args[0].intValue()); int r = fib(n); System.out.println( fib of + args[0] + is + r); 5 n =, 2 = Fib(n-2) + Fib(n-) n > 2 n class Fib { public static int fib (int n) { if (n < 3) return ; else return (fib(n-2) + fib(n-)); public static void main (String args[]) { int n = Integer.valueOf(args[0].intValue()); int r = fib(n); System.out.println( fib of + args[0] + is + r); Fib(n) 止まらない 6

2 Fibonacci 数を求める ( 素朴法 ) Fibonacci 数を求める ( メモ化 ) n =, 2 = Fib(n-2) + Fib(n-) n > 2 n =, 2 = Fib(n-2) + Fib(n-) n > 2 関数 Fib ( 入力 n : int) n =, 2 ならばを返す n>2 ならば r = Fib(n-2) r2 = Fib(n-) r+r2 を返す疑似コード ( 疑似プログラム ) による記述 7 関数 Fib ( 入力 n : int) n =, 2 ならば Fib(n)= をメモしてを返す n>2 ならば Fib(n-2) の値からメモから取り出し r とする Fib(n-) の値からメモから取り出し r とする Fib(n)=r+r2 をメモして r+r2 を返す 8 Fibonacci 数を求める ( メモ化 2) Fibonacci 数を求める ( メモ化 3) n =, 2 = Fib(n-2) + Fib(n-) n > 2 関数 Fib ( 入力 n : int) n =, 2 ならば Fib(n)= をメモしてを返す n>2 ならば Fib(n-2) の値からメモから取り出し r とする Fib(n-) の値からメモから取り出し r とする Fib(n)=r+r2 をメモして r+r2 を返す Fib() = Fib(2) = Fib(3) = + = 2 Fib(4) = + 2 = 3 Fib(5) = = 5 n Fib(n) Java の int 型として実装した場合 9 n =, 2 = Fib(n-2) + Fib(n-) n > 2 Int 型がオーバーフロー下 3 けたのみを計算実際には最近 2 つの値のみメモ化すればよい n Fib(n) メモ化法による改善計算速度は向上素朴法では Fib(30) までメモ化法では Fib(8000) でも計算可能ただし int のオーバーフローを無視メモリは多く使うメモ化のための記憶領域が必要感覚的な比較ではなくきちんと比較をしたい速度が 0msec であるなどはあまり意味がない ( その時に使用した計算機の速度に依存してしまい客観的普遍的な比較にならない ) アルゴリズムアルゴリズム問題に対する解き方与えられた基本命令をどう組み合わせて解を求めるかを記述したものアルゴリズムとプログラムの違いプログラムは特定のプログラム言語で記述その言語の処理系を用いて実行可能アルゴリズムはより抽象的一般的な疑似プログラムとして記述する ( 特定のプログラム言語や特定の実装方式に関する記述を取り除いた記述とする ) そのままでは実行可能でないことが多い 2 2

3 アルゴリズムの計算量計算量アルゴリズムをはかる尺度計算の複雑さとも言う computational complexity 2 つの計算量時間計算量 time complexity 計算のスピード実行速度空間計算量 space complexity メモリ ( アルゴリズムを実行する過程で瞬間的に使用する最大メモリ量 ) どちらも小さい ( 少ない ) 方が良い 3 具体的な時間計算量 Fib(n) に対する素朴法足し算の回数 Fib(n) 関数呼び出しの回数 >Fib(n) その他の計算 Fib(n) に対するメモ化法足し算の回数 n-2 関数呼び出しの回数 n- その他の計算たしかに後者の方が速い 4 Fib(n) に対するより高速な方法 () 準備 : x から x^n を ( 掛け算だけで ) 計算する例 :x^3 を計算したいとき x -> x^2 -> (x^2)^2 = x^4 -> (x^4)^2 = x^8 x * x^4 * x^8 = x^3 掛け算 5 回で x^3 が求まった n の 2 進数表現の桁数を r とするとき 2r- 回以下の掛け算で x^n が求まる 2 r - < 2 log_2 n - 5 Fib(n) に対するより高速な方法 (2) メモ化法 : x = Fib(n-) x = y = Fib(n) y = Fib(n) y = x+y = Fib(n-)+Fib(n) = Fib(n+) 0 0 x y n- = x y = Fib(n) Fib(n+) 6 Fib(n) に対するより高速な方法 (3) Fib(n) に対するより高速な方法 (4) A = 0 A -> A^2 -> A^4 ->. -> A^024 0 n- = Fib(n) Fib(n+) 7 2*2 行列 A の n- 乗を計算すれば回の足し算で Fib(n) が求まる 2 つの 2*2 行列の積 8 回の掛け算 4 回の足し算 n 乗の計算は 2log_2 n- 回以下の乗算よって Fib(n) は 6log_2(n-) -8 回以下の掛け算 8log_2(n-)-3 回以下の足し算 8 3

4 問題より高速な方法は本当に高速か? 正数の乗算整数の加算合計素朴法 0 Fib(n) Fib(n) メモ化法 0 n-2 n-2 より高速な方法 < 6 log n < 8 log n <24 log n オーダ記法定数倍などを無視し n が非常に大きくなったときの関数の振る舞いだけを表す表記方法正確な定義はデータ構造とアルゴリズムの授業を参照すること素朴法 O(α^n) α=( 5 + )/2 メモ化法 O(n) より高速 O(log n) 9 2 オーダの違いはとんでもない差を生じる 00n と 2^n の差 n = n = ほぼ 0^6 n = ほぼ 0^9 計算機が 2 倍のスピードになっても指数関数的アルゴリズムでは計算できる n が増えるだけアルゴリズムの良し悪しの差はハードウェアの改良だけではとても埋められない良いアルゴリズムを考えるのは今も将来も極めて重要 22 前半のまとめアルゴリズムとは何か計算量とは何かアルゴリズムの良し悪しは入力データが非常に大きくなったときの計算時間に非常に大きく響く参考 : O(n^k) となるアルゴリズムが存在する問題たちの集合をクラス P と呼ぶ P は多項式を意味する a x^n + b x^(n-) + 23 後半 : 整列アルゴリズム整列 ( ソート ) 昇順に整列

5 素朴な整列アルゴリズム () 最小値を探す先頭と最小値をいれかえる素朴な整列アルゴリズム (2) 最小値 ( のつ ) を探す先頭と最小値をいれかえる素朴な整列アルゴリズム (3) 素朴な整列アルゴリズム (4) 時間計算量 ( データの個数を n とする ) 2 つのデータの比較 (n-) + (n-2) + + = n(n-)/2 データ列における 2 つのデータの交換 n+(n-) + + = n(n+)/2 その他 ( ループの制御等 ) は無視時間計算量は O(n^2) 用途によってはこれでも十分利用価値があるが n が非常に大きなときは遅すぎる例 : 筑波大学のすべての科目を科目番号順に整列 29 マージソート ( 併合ソート ) のアルゴリズム () 基本アイディア : Divide and Conquer ( 分割統治法 ) 多数のデータ数に対して何らかの解と求める場合データを 2 つ ( 以上 ) に分割してそれぞれの解を求めその結果を用いて全体に対する解を求める方法マージソート ( 併合ソート ) のアルゴリズム (2) 分割するそれぞれを別々にソートする

6 マージソート ( 併合ソート ) のアルゴリズム (3) マージ操作 () つのソート済みの列をマージ ( 併合 ) する > なのでを書き込むマージ操作 (2) マージ操作 (3) < 3 なので 2 を書き込む同様にして小さいものから順に書き込んでいくマージ操作 (4) 最後に残ったデータをコピーする再帰 (recursion) マージソート ( を含む分割統治法 ) は再帰を使う再帰的な関数定義 Fib(n) = if n < 3 then else Fib(n-2)+Fib(n-) 関数の定義の中で定義されつつある関数自身を回以上呼ぶ関数再帰を上手に使うことによりアルゴリズムやプログラムを簡潔明瞭に表現することができる cf. 計算論 ( 計算可能性関数の理論 )

7 マージソートの計算量 () 時間計算量 ( データの個数を n とし n=2^m と仮定 ) 2 つのデータの比較のみをカウントする N 個のデータのマージソートにおける 2 つのデータの比較回数を T(n) とすると次の式が成立する T(n) <= T(n/2) + T(n/2) + マージ操作における計算量 2n- n- よって授業時点のスラ T(n) <= 2 T(n/2) + 2n イドの誤り修正 38 マージソートの計算量 (2) 時間計算量 ( データの個数を n とし n=2^m と仮定 ) T(n) <= 2 T(n/2) + 2n T() = 0 これらより (n=2^m とおくと ) T(2^m) <= 2 m 2^m + T(n) <= 2 n log n + よって T(n) は O(n log n) であるマージソートの時間計算量は O(n log n) 39 関数の増大度の差 N N log N N^2 2^N ^2 0^ ^4 0^ ^6 0^ ^8 0^300 整列アルゴリズムのあれこれ古来多くの整列アルゴリズムが考案されてきた素朴な方法 ( インサーションソートなど ) O(n^2) マージソート O(n log n) その他クイックソートヒープソートなどデータに対して比較演算のみが許される場合は O(n log n ) が最善であることが証明されているデータが 0 から 00 までの整数値のように有限個の範囲であれば O(n) のソートが可能バケツソート 40 4 後半のまとめ全体のまとめ整列問題を取り上げ素朴なアルゴリズム分割統治法に基づく効率の良いアルゴリズムについて考えたポイントアルゴリズムを設計するとはどういうことかそのアルゴリズムの性能 ( 計算量 ) を見積もるのはどうすればよいか O(n^2) と O(n log n) は大差がある 42 問題をモデル化しそれに対する良いアルゴリズムを考えるのはコンピュータサイエンスにおける最重要問題のつ良いアルゴリズム重要な尺度は時間計算量や空間計算量 : データのサイズを表す n が非常に大きいときの計算量を ( おおざっぱに ) 示す現実問題の解決にあたって ( 理想的なアルゴリズムがいつでもそのまま使えるわけではないが ) 大きなヒントとなる 43 7

8 レポート ( 締切 7 月 25 日 ) 以下の内容 ( つ以上 ) の解答をレポートボックス ( 支援室で設置 ) に提出せよ ( 名前学籍番号明記 ).Fib(n) を O(log n) で計算するアルゴリズムで Fib(024) の下 3 ケタを求めなさい 2. マージソートの時間計算量について T(n) <= 2 T(n/2) + n から T(n) が O(n log n) であることを導きなさい 3. 以下のデータに対するマージソートの過程を図示しなさい 0, 2, 8, 9, 2,, 4, 7, 6, 3 4. 本日の授業内容を A4 サイズでページ程度のサイズでまとめなさい 44 レポート問題. 解答.Fib(n) を O(log n) で計算するアルゴリズムで Fib(024) の下 3 ケタを求めなさい解スライド 7 ページの行列 A の 024 乗を計算 A A^2 A^4 A^024=[ / ] ただし行列の要素は下 3 ケタのみ計算 = Fib(025) Fib(026) これより Fib(024) の下 3 けた = レポート問題 2. 解答 2. T(n) <= 2 T(n/2) + n から T(n) がO(n log n) であることを導きなさい (n=2^m と仮定してよい ) 解 T(2^m) <= 2 T(2^(m-)) + 2^m - <= 4 T(2^(m-2)) + 2 2^m (+2) <= 8 T(2^(m-3)) + 3 2^m (+2+4) <= 2^m T() + m 2^m (2^m-) = 2^m (m+t()-) + よって十分大きなmに対して T(2^m) <= 2^m 2m であるので T(n)<= 2 n log_2 n 46 よって T(n) は O(n log n) であるレポート問題 3 の解答 3. 以下のデータに対するマージソートの過程を図示しなさい 0, 2, 8, 9, 2,, 4, 7, 6, 3 解 ( 奇数個の列を半分するとき前半が後半より長くすると仮定逆パターンで解答しても構わない ) 以下では整列済みの列を( ) で表す [0, 2, 8, 9, 2,, 4, 7, 6, 3] [[0, 2,8, 9, 2], [, 4, 7, 6, 3]] [[[0, 2, 8], [9, 2]], [[,4,7], [6,3]]] [[[[0,2],[8]], [[9], [2]]], [[[,4],[7]], [[6],[3]]]] [[[[[0],[2]],(8)], [(9), (2)]], [[[[],[4]],(7)], [(6),(3)]]] 47 レポート問題 3 の解答 ( 続き ) [[[[(0),(2)],(8)], (2,9)], [[[(),(4)],(7)], (3,6)]] [[[(2,0),(8)], (2,9)], [[(,4),(7)], (3,6)]] [[(2,8,0),(2,9)], [(,4,7),(3,6)]] [(2,2,8,9,0), (,3,4,6,7)] (,2,2,3,4,6,7,8,9,0) 解答は上記の趣旨がかかれていればよくこの通りでなくてよい 48 8

論理と計算（２）

論理と計算（２）情報科学概論 Ⅰ アルゴリズムと計算亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 計算とは? コンピュータが計算できることは? 1 2 関数 = 計算? NO 部分関数と計算入力 1 入力 2 関数出力入力 1 入力 2 部分関数出力停止しない入力 1 入力 2 コンピュータ止まらないことがある出力 3 入力 1 入力 2 コンピュータ出力停止しない