再帰方程式の説明
処理速度の分析の第2段階として、再帰を含む処理の処理速度について説明を行う。
再帰による階乗の処理速度
再帰で階乗の処理を記述し、その動きを説明したあと、処理速度を分析してみる。
((階乗の再帰)) int fact( int x ) { if ( x <= 0 ) return 1 ; else return x * fact( x - 1 ) ; } ((処理速度の再帰方程式)) T(0) = Ta T(N) = Tb + T(N-1) | N≧1 ((再帰方程式を代入法で予測)) T(0) = Ta T(1) = Tb + T(0) = Ta + Tb T(2) = Tb + T(1) = Ta + 2*Tb : T(N) = Ta + N * Tb よって、再帰による階乗の処理は、O(N)
再帰による2分探索の処理速度
次に2分探索法を再帰によって記述してみる。 この処理にかかる時間は、データ件数Nに対して….
((2分探索の再帰による記述)) int find( int data[] , int L , int R , key ) { if ( L+1 == R ) { if ( data[ L ] == key ) return L ; else return -1 ; } else { int M = (L + R) / 2 ; if ( data[ M ] == key ) return M ; else if ( data[ M ] > key ) return find( data , L , M , key ) ; else return find( data , M , R , key ) ; } } int array[8] = { 12 , 23 , 34 , 45 , 56 , 67 , 78 , 89 } ; void main() { printf( "%d番目に見つかった" , find( array , 0 , 8 , 78 ) ) ; } ((処理速度の分析)) この関数は、対象となるデータ件数によって時間が変化し、 対象となるデータ件数(R-L) の関数Tであるとして... T(1) = Ta T(N) = Tb + T( N / 2 ) で表すことができる。 代入法で予測してみると、 T(1) = Ta T(2) = Tb + T(1) = Ta + Tb T(4) = Tb + T(2) = Ta + 2 * Tb : T(2^m) = Ta + m * Tb ただし m = log2( N ) だから、 T(N) = Ta + Tb * log(N) よって、O(log(N))
ハノイの塔や再帰によるフィボナッチ数列の処理速度
Moodle講習会に参加
大学連携で県立大学を中心として整備をすすめている f-leccs.jp の 活動の一環として、LMS(Learning Management System) Moodle の講習会(県立大学開催、仁愛大学篭谷氏講師)に参加。 連携校の登録された先生であれば、講義の日程管理・配布資料・小テスト・評価管理 をWebインタフェースで自由に登録管理ができる。
参加する学生さんとしても、小テストでは携帯Web機能のモジュールも追加されているので、 多少の制限はあるけど、携帯で回答するなどもできるようになっている。 ただ、資料の準備には慣れも必要だし、一度頑張ってコンテンツを作っちゃえば、 使い回しもできるようになるんだし、最初のひと頑張りが大切かな。
予習ができなきゃね…
私自身は、ずいぶん前から、講義のあとの要点をまとめたメモを講義録として、 日記に記載してきている。 しかし、あくまでも講義の後。 大学は予習した上で授業に臨むのが前提だから、 講義録ではすでに遅れているんだよなぁ… さて、頑張って『授業の前』に Moodle 上でコンテンツを作らねば…
VOD化
f-leccs.jp で狙っているの講義へのネット技術の活用の1つには、 講義のVOD(Video On Demand)化もあげられている。 映像系の担当の方との雑談では、なかなか全員の人に認知してもらえるまでが大変そう…
VOD化といっても、常にビデオの専門家に来てもらうのはコストもかかる。 それに講義の話って、重要そうなネタを表現を色々と変えながら何度も話すことを 繰り返したりするから、映像的には動画がでかい+内容もかなり冗長ということで、 ケチくさい考え方の染み付いたサーバ屋の視点では、 『なんだかもったいないよぉ…』って気分。
それ以上に、ビデオに撮られること自体が恥ずかしい…って障壁の方が大きかったりして….
C言語からC++でオブジェクト指向
先週のC言語によるオブジェクト指向の導入に引き続き、 C++を実際に使ってみるようにと、ベースのプログラムを、 メソッド呼び出し表記に変えたり、コンストラクタを使うように修正したりしながら 説明を行う。
class Person { private: // private宣言で、クラス以外で使えない。 char name[ 10 ] ; int age ; public: // public宣言で、クラス以外でも使える。 void set( char s[] , int a ) { // C言語なら、対象オブジェクトを明記したけど、不要となる。 strcpy( name , s ) ; age = a ; } void print() { printf( "%s %d" , name , age ) ; } } ; void main() { Person saitoh ; saitoh.set( "T-Saitoh" , 44 ) ; saitoh.print() ; } ((上記の説明の後)) class Person { : Person( char s[] , int a ) { // データ初期化⇒コンストラクタ strcpy( name , s ) ; age = a ; } } ; void main() { Person saitoh( "T-Saitoh" , 44 ) ; : }