ホーム » 2009 » 4月 » 23

日別アーカイブ: 2009年4月23日

2009年4月
« 3月   5月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰方程式の説明

処理速度の分析の第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 ) ;
:
}