再帰方程式+動的メモリ管理
マージソートの処理速度
再帰方程式の説明の最後として、ソート処理の速度見積りを示す。 クイックソートの説明だと、微妙な所が説明が判りにくいので、 例年通りマージソートの例にて、O( N log N ) を説明。
処理の内容より、 T(1) = Ta T(N) = Tb + 2*T(N/2) + N*Tc 再帰と同じ代入を繰り返すと、 T(1) = Ta T(2) = Tb + 2*T(1) + 2*Tc T(4) = Tb + 2*T(2) + 4*Tc : T(2^m) = Tb*(2^m-1) + 2^m * Ta + m * 2^m * Tc よって、O( N log N )
動的なメモリ
処理速度の見積りの次のプログラム評価指針としてのメモリの使用量の説明。 再帰呼出のプログラム例から、局所変数は 『最後に出現した変数から不要となる』特徴を持っていることを紹介し、 こういったデータの保存には Stack(Last In First Out)が使えることを示す。 例として、push,pop のコードを示し、fact(階乗)のコードを push,pop を 用いて記述する。
Stackのコードも示したため、対比的な事例ということで リングバッファのコードを示し待ち行列(First In First Out)の説明を行う。
動的なメモリの説明として、授業最後に malloc,free の例を示す。 動的に配列サイズを与えるプログラム例にて説明を行う。 詳しい説明は来週に行う必要あり。
体育祭、ご苦労さまでした。
体育祭では 4EI のクラスは、応援・デコレにて、大変ご苦労さまでした。 「4年間のクラスの集大成?」というと変かもしれませんが、 クラス全員で力を会わせ大変なイベントを乗り切ったという感想です。
応援
ダンスはなかなかの物でしたよ。 見ている所では、『団長、 かわいい! 』の声がよく聞こえてきました。
個人的には、白組(物質)のダンスの構成が旨いのに、凄く驚きました。 全体の配置・流れとも、ダンスをよく解っていると思いました。
デコレ
今日も朝早くからの準備だったみたいで、ご苦労さまでした。
録音した音が、スピーカを通しての音が予想外であったため、少し残念でした。
そういう実験って出来ないからなぁ….
FONT COLOR blue # 4EI の皆様は、この他の大量の写真につきましては、
のページを御覧下さい。(非公開)
再帰方程式
再帰を含む処理の処理速度の見積りの例として、 階乗の再帰の速度見積り、2分探索の再帰版の速度見積り、 ハノイの塔の処理速度の速度見積りを示す。
ハノイの塔の再帰方程式と数学的機能法
N枚の板の移動は、以下の手順で実行するため、移動回数を H(N) で表すと、 以下のような再帰方程式が示される。
- 底の1枚を残して、N-1枚を一旦別の柱に移し、
- 底の1枚を目的の柱に移動、
- 別の柱に移しておいた N-1枚を移動、
H(1) = 1 (N=1の時) H(N) = 1 + 2 * H(N-1) (N>1の時)
少ない枚数のハノイの塔を解くと、処理速度 H(N) では、以下の仮定が成り立つ。
H(N) = 2^N - 1
よって、数学的帰納法で証明すると、
・H(1) で、仮定が正しいのは明らか。 N = k の時、仮定が正しいならば、 N=k+1の時、 ・H(k+1) = 1 + 2 * H(k) # ルールより = 1 + 2 * (2^k - 1) # N=kの時の仮定を代入 = 1 + 2^(k+1) - 2 = 2^(k+1) - 1 であり、仮定は k+1 でも成り立つ。 よって数学的帰納法により、N≧1で成り立つ。
フィボナッチ数の再帰プログラムの処理速度の見積り
講義では、フィボナッチ数の処理速度の見積りは示さなかったが、 自主的な取り組みをしてみることと伝えておいた。 ここで、ヒントを示す。
フィボナッチ数の再帰処理より、成り立つ再帰方程式 T(1) = Ta T(2) = Ta T(N) = Tb + T(N-1) + T(N-2) 代入法による一般式の予測 T(1) = Ta , T(2) = Ta T(3) = Tb + Ta + Ta T(4) = Tb + (Tb + 2Ta) + Ta = 2Tb + 3Ta T(5) = Tb + (2Tb+3Ta) + (Tb+2Ta) = 4Tb + 5Ta 以下の一般式を仮定する。 T(N) = (Ta + Tb) * fib(N) - Tb 上記一般式は、N=1,2 で仮定が成り立つのは明らか。 N≦k で仮定が成り立つとすれば、N=k+1 の時、 T(k+1) = Tb + T(k) + T(k-1) = Tb + {(Ta + Tb) * fib(k) - Tb} + {(Ta + Tb) * fib(k-1) - Tb} = (Ta + Tb){ fib(k) + fib(k-1) } - Tb = (Ta + Tb) * fib(k+1) - Tb よって、k+1 でも仮定が成り立つことが確認できた。
この一般式より、フィボナッチ数の再帰呼出し処理の速度のオーダーは、 ) となる。 ビネの公式より、 )
# くそ、授業中に記憶だけで書いた(1+sqrt(5))/2 の値が違ってた….
体が筋肉痛…
昨日の田植えの手伝いの後遺症にて筋肉痛。 学生には「ダイエットになったでしょ!」と突っ込まれる。
# 先日の遠足では最終的に筋肉痛が出なかっただけに….
パルス回路の考察のヒント
例年パルス回路の実験を行うと、 『非安定マルチバイブレータ回路の負荷の影響の考察が解らない』 という質問多数。そこでヒント資料を公開する。
# といっても、答えを教えては意味がない…
整数型の範囲とN進数
符号付き/無しの整数(char,short,int,long等)の範囲の説明。 数値の範囲が問題となるプログラムの例として、以下の事例を紹介
/* 16bitコンピュータでのトラブル事例 */ /* int=16bitでは、座標間距離が200を越えるとオーバーフローの可能性 */ int distance( int x0 , int y0 , int x1 , int y1 ) { int r2 = (x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1) ; return sqrt( r2 ) ; } /* 2037年問題(時刻を1970年からの経過秒数で扱い 2037年に32bit溢れ) */ /* の説明のあと、2004年の銀行系トラブルの事例の説明。*/ int midtime( int time0 , int time1 ) { return (time0 + time1) / 2 ; /*int=32bitでは2004年以降トラブル発生*/ }
N 進数の説明により、基数変換方法と10進,2進,8進,16進の扱いを説明。 小数を含む基数変換の話しの途中で、時間切れ。
問題点の解説
提出されているシステム設計のテーマ案を元に、問題点などの解説。 来週からは具体的な実現方法のリサーチを行ってもらう。
個人的主観にてテーマ案の評価を行う。といっても、基準としては、以下の点とした。
- アイディア評価
- 自分のアイディアか?
- 過去のプロコンや演習で類似ネタが無いか?
- 広く使われている同類技術があるか?
- 新しい利用者を想定しているか?
- アイディア全体の完成度は?
- 説明の評価
- 判りやすい説明文章か?
- 図を交えた説明か?
- 目的が明記されているか?
- 処理の概要が明記されているか?
- 処理の利点や欠点が明記されているか?
- 実現可能性の評価
- 半年で実現可能なテーマか?
- システムの全体像が見えているか?
- 手法に言及しているか?
- 実現するための問題点に言及しているか?
- 実現したものがコンテストで評価されそうか?
グループが細かく別れすぎなので、同一ネタにまとめる必要あり。
「トリムパークかなづ」へ遠足
10人程の欠席者がいたものの、遠足では皆さんそれなりに楽しめていたようです。 丸岡駅までの移動にて利用した『事故後のJR』が、 『間に合わせのための加速運転が禁じ手』になっているためか、 全般的に5分遅れとなっているのが、時勢を感じさせます。
学生さんにも言われたが、筋肉痛が明後日に出るようなら、おじさんだそーな。 この日記をメモしている、5/3朝現在、筋肉痛は無いが虚脱感。 明日は、たぶん『おじさん』モードになってることだろう….はぁ…