ホーム » 2011 » 4月

月別アーカイブ: 4月 2011

2011年4月
日	月	火	水	木	金	土
	1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

今日は体育祭

2011年4月29日

4/29の祝日ですが、学校日程の都合もあり本来昨日予定の体育祭が雨で延期になって、今日が体育祭です。雨が降ったりして、競技が一部中止になったり…

再帰処理の速度分析

2011年4月27日

例年通りの進み方なんだけど、再帰処理の速度分析をするための説明を行う。最初に、fact(N) , 配列の2分割積算 , fib(N) のプログラムを示し、処理の流れのトレースを解説。この後に、ハノイの塔の再帰方程式と数学的帰納法による証明を説明する。

ハノイの塔のディスクの移動回数を、 $H(N)$ で表す。ハノイの塔のルールより、N枚のディスクの移動には、(1)最下層の1枚の上にある、(N-1)枚を隣に移動、(2)最下層の1枚を移動、(3)一旦隣に動かしておいた(N-1)枚を、目的の塔に移動というステップを経由する。このため、 $H(N)=1+2H(N-1)$ ただし $N>1$ また、最終的には、 $H(1)=1$ が成り立つ。

ハノイの塔は、少ない枚数での移動を解いてみると、 $H(N)=2^N-1$ が予想される。この式が常に成り立つことを証明するため、 $N=k$ 枚についてこの予想が成り立つものと仮定する。この時、 $k+1$ 枚については、

$H(k+1)=1+2H(k)$ が成り立つので、
$H(k+1)=1+2(2^k-1)=1+2^{k+1}-2=2^{k+1}-1$

となり、 $k+1$ でも仮定が成り立つことが示される。よって、数学的帰納法により仮定は全ての自然数について成り立つ。

この証明のような、式の中に自分自身が含まれるような方程式を、再帰方程式と呼ぶ。再帰処理の速度予測では、これと同じように再帰方程式をたてる事ができる。

プログラムと再帰方程式

int fact( int N ) {
if ( N == 1 )
return 1 ;
else
return N * fact( N - 1 ) ;
}

このプログラムの処理時間は、N=1においては、if,==,return の一定の処理が行われるので、

$T_{fact}(1)=T_a$

Nが2以上では、if,==,*,-1,returnの処理と、fact()の再帰が行われる。よって、

$T_{fact}(N)=T_b+T_{fact}(N-1)$

この再帰方程式を、代入を繰り返しながらとけば、

$T_{fact}(N)=T_b(N-1)+T_aN$

が導き出せる。よって、階乗の再帰プログラムの処理時間のオーダは、 $O(N)$ となる。

創造工学の導入実験でPerlと正規表現

2011年4月27日

4年の前期実験では、2週分を創造工学でのシステム作りの導入とするための、基礎実験を行っている。クラスを3グループに分け、私の担当は初回にPHPによる、 Webプログラミングの説明。これにより簡単な掲示板やアンケートを作ってもらった。

2回目の今日は、1日実験でPerlと正規表現の実験を行った。最初に、超単純英語によるBot作りをネタに、Perlの基本文法と、正規表現を体験してもらう。理解度が速い人向けに、後半はメールデータを題材にしながら、 Jcode.pmを用いた文字コード変換、headerのmime_decodeを説明し、このメールデータの中から、From,Toの部分を抽出するプログラムを作ってもらう。

perl-regex.pdf

#!/usr/bin/perl
# 超基本英語によるBot
while( <> ) {
   $line = $_ ;
   if ( $line =~ /like/ ) {
      if ( $line =~ /^(.*)\s+like(|s)\s+(.*)\.$/ ) {
         print "$1 は $3 が好きです。\n" ;
      }
   }
}

#!/usr/bin/perl
# メールデータの文字コード変換
use Jcode ;
my $head = 1 ;
while( <> ) {
   $line = $_ ;
   if ( $head ) {
      print Jcode->new( $line )->mime_decode->utf8 ;
      if ( $line =~ /^$/ ) {
         $head = 0 ;
      }
   } else {
      print Jcode->new( $line )->utf8 ;
   }
}

Perlを初めて使ってもらうので、暗黙変数$_とのマッチングや、「式 if ( 条件 ) ;」といった Perl らしい節操のない書き方は、説明を避けた。

数値の型とN進数

2011年4月26日

先日の変数の寿命とスコープの話の次ということで、数値の型とN進数について説明。

数値の型によって、初心者がやりそうな間違いを説明しながら、 C言語の型変換が、「精度が異なる場合は、精度のいい方に型変換」とか「型キャスト」を説明。

int a[4] = { 10 , 11 , 12 , 20 } ;
int sum = 0 , count = 0 , i ;
for( i = 0 ; i < 4 ; i++ ) {
sum += a[i] ;
count++ ;
}
printf( "%f" , sum / count ) ;
// 実行結果は、%fとintの型の不一致で、異常値の表示。
// (double) sum / (double) count と書くべき。
double x ;
for( x = 0 ; x < 3.141592 ; x += 1/18 * 3.141592 ) {
printf( "%f %f\n" , x , sin( x ) ) ;
}
// 1/18*3.14 は、1/18が整数除算で0になるため
// 無限ループ

N進数

N [bit]で扱える数値が $2^N$ であらわせ、概数を求める場合、 $2^{32}={2^2}\times{2^{10}}\times{2^{10}}\times{2^{10}}\simeq{4}\times{10^9}$ 計算できることや、 $2^{N}=10^{M}$ より、 $M=N\times\log_{10}2=N\times{0.301}$ で大体の桁数が計算できることを説明。

$abcd)_N=aN^3+bN^2+cN^1+d=N(aN^2+bN^1+c)+d$ を説明し、元の数をNで割った余りを下の桁から書き並べると、N進数に直せることを説明。この後、8進数、16進数、10進数変換の理解度を確認。 C言語での0123の8進数表記や、0x123の16進数表記、printfでの"%o","%x"なども説明。

次に、小数点以下のN進数の説明を行う。 $0.abcd)_N=\frac{a}{N}+\frac{b}{N^2}+\frac{c}{N^3}+\frac{d}{N^4}=\frac{1}{N}(a+\frac{b}{N}+\frac{c}{N^2}+\frac{d}{N^3})$ より、小数点以下にNをかけると、整数部にN進数の小数点上位1桁が得られることを説明する。これより、0.1)₁₀といった値を2進数にすると、無限循環小数になることを示す。この結果、C言語で、0.1を10回積算しても、正確に1.0といった値にならない可能性があることを紹介する。

2011年4月24日(第213回)

2011年4月24日

学生会長　４年物質工学科　西山さんへのインタビュー
体育祭の競技の詳細について
マニアックタイムズ第２回　２年電子情報工学科　山田さん
動画投稿サイトについて

Windowsマシン消滅

2011年4月21日

朝から授業用の資料を印刷しようと、ちょろちょろ仕事を初めていたが、トイレに行ってもどってきたら、マウスもキーボードも動かない。キーボード切替器が入っているので、切り替えるがLinux側では問題なくマウスもキーボードも動く。どうもUSBが怪しいのでFront USBにつないだり、他のUSB機器をつなげたり。どうやってもマウスキーボードが動かない。どうも、PCのマザーボード上のUSB回路がやられたとしか思えない。備品番号をみると、購入時期もちょうど５年前だし寿命かな…

仕方が無いけど、デスクトップメインマシンが無くなったので、代用品を探す…そういえば、卒研用にiMacを買ったけど、今年は利用者がいなさそうだし、教官室に移動とした。ということで、教官室は、iMac,Linux×2,MacBook構成となって、Windowsマシンなし。さすがに、色々と無理も出てくるので、Parallels Desktop 6 for Mac を発注する。

でもWindowsで使っていた、NAS には重要な書類がぞろぞろ。でも、Mac側でTeraStation を使うと、smb:// では文字化け、afp:// では漢字は表示できても読めないファイルがちょろちょろ…ということで、不便極まりない。でも年度末に買った Drobo S があるので、 HFS+にフォーマットし直し、中身をごっそり移動させることにした。 TeraStation も初期型の 500GB だし、これも寿命かな…

手続き抽象・データ抽象

2011年4月21日

前回のコンストラクタなどの説明も終わったので、今回は具体的な課題に取り組んでもらう。

最初に先週予告していたように、実部・虚部による複素数のクラスを宣言し、加算と表示メソッドを作る。この後、オブジェクト指向の良さとして、データ内部や手続き内部が隠蔽化されていれば、後でクラス設計者が内部を、複素数の絶対値と偏角に変更しても、プログラムの利用者側のプログラムを一切変更せずに済むということを示す。

今回は、プロジェクタにエディタをそのまま投影しながら、直接プログラムを書き、目の前でコンパイル＆実行しながら説明を行った。時間の後半は、このクラスに乗算以外にもいろいろな複素数演算を加え、呼び出し側のプログラムが変更不要といったことを実践できるようなプログラムを作ることを目標として、課題に取り組んでもらう。

オーダ記法

2011年4月20日

先週の最大選択法の処理時間の分析を、解説する。具体的な説明は、先週の資料に記載したのでそちらを参照。この後、2分探索法のブログラムを示し、オーダ記法の説明を行う。

2分探索法の分析

int data[ N ] ;     // dataはあらかじめ昇順にソート
int key = 探す値 ;
int L = 0 , R = N ; // [0,N)
while( R-L > 1 ) {
   int M = (L + R) / 2 ; // [L,M) , M , [M+1,R)
   if ( data[ M ] == key )
      break ;
   else if ( data[ M ] > key )
      R = M ;     // [L,M)
   else
      L = M+1 ;   // [M+1,R)
}

このプログラムでは、ループ1回につき、対象データ件数が約半分になる。よって、m回ループをすれば、対象データ件数は、 ${\frac{N}{2^m}}$ となり、データが見つからない最悪ケースでは、対象データ件数が1件になるまで繰り返す。よって、 ${m}=\log_2{N}$ となり、処理時間は、以下のように示される。

${T(N)}=T_a+T_b\times\log_2{N}$

オーダ記法

処理速度の見積もりでは、単純ループはNに比例、最大選択法では、 ${N^2}$ に比例、 2分探索法では、 ${\log{N}}$ に比例ということが、アルゴリズムの処理時間の分析では重要となる。そこで、「Nについてのどのような式に比例するのか？」を、オーダ記法で表す。単純ループでは、 ${O(N)}$ 、最大選択法では、 ${O(N^2)}$ 、 2分探索法では、 ${O(\log{N})}$ といったように表記する。

変数の寿命と有効範囲、関数と引数

2011年4月19日

最初に、先週の未消化分ということで、switch – case 文を説明。 caseラベルにジャンプする概念と、break 文の必要性を解説。

大域変数・動的局所変数・静的局所変数

変数には、寿命と有効範囲という概念が重要であり、局所変数であれば、宣言されたブロックの中でのみ有効。大域変数は、どこからでも使える変数で便利だけど、危険な使い方。局所変数は、一般的に動的変数であり、ブロックに入った時に作られ、ブロックを抜けると消滅する。しかし、static キーワードを付けた局所変数は、静的変数となり、プログラム起動時に作られ、プログラム終了まで生き残る。

int x = 123 ;            // 静的大域変数
void foo() {
int x = 234 ;        // 動的局所変数
x++ ;
printf( "%d" , x ) ;
}
void bar() {
static int x = 345 ; // 静的局所変数
x++ ;
printf( "%d" , x ) ;
}
void baz() {
x++ ;
printf( "%d" , x ) ;
}
void main() {
foo() ;   // 235
bar() ;   // 346
baz() ;   // 124
foo() ;   // 235
bar() ;   // 347
baz() ;   // 125
}

関数と引数

関数と引数の説明として、実引数のコピーが仮引数に渡されて、局所変数の仮引数は関数処理と同時に消滅するという解説を行う。これにより、関数での副作用が呼び出し側に伝わらないようにすることを説明。一方で、関数の副作用を伝えたい場合は、値渡しではなく、ポインタ渡しをすることを説明。

// 値渡し(副作用が無い)
void foo( int x ) {
x++ ;
printf( "%d" , x ) ;
}
void main() {
int x = 123 ;
foo( x ) ;  // main::x とfoo::xは別の入れ物
foo( x ) ;
}
// ポインタ渡し(ポインタ経由で副作用)
void foo( int* p ) {
(*p)++ ;
printf( "%d" , *p ) ;
}
void main() {
int x = 123 ;
foo( &x ) ;
foo( &x ) ;
}

説明において、間違い・勘違いを防ぐためのテクニックとして、 switch-caseでは、最後の行にも breakを書くとか、次のcaseになだれ込みでも、/*no break*/ コメントを入れるとかのテクニックを紹介。大域変数では、一時的な変数と間違われないように、使用目的が分かるような長い名前をつけるとか、大域変数は単語先頭を大文字、#define 定数は名前をすべて大文字とするといったような、誤解されないテクニックも紹介する。

新サーバのRAID化

2011年4月18日

先日から、自宅に持ち帰って設定をしていたサーバが、ようやく動いてくれるようになった。新型の Software RAID 対応の組み込みRAIDコントローラだったけど、 Debianが対応が不十分なのか、Read-only の認識しかしてくれない。やむなく、RAIDコントローラを使用せずに Software RAID を構成させた。

HDDにRAIDの下地となるパーティションの作成
　> SCSI1(0,0,0)(sda)-500GB ATA WDC XXXXXXXXX
　>  1.基本 128 MB B K raid  # md0(boot) -- 注:bootフラグを付ける
　>  2.基本 500 GB   K raid  # md1(LVM)
　> SCSI1(0,0,0)(sdb)-500GB ATA WDC XXXXXXXXX
　>  1.基本 128 MB B K raid  # md0(boot)
　>  2.基本 500 GB   K raid  # md1(LVM)

ブート起動用に128MBの領域を確保し、残りは /,/home,swap 用に使うけど、 /etc/sda,/etc/sdb でRAIDを構成させるために、領域種別にはraidを指定する。

ソフトウェアRAIDの設定
　MDデバイスの作成
　　種別=RAID1 , デバイス数=2 , スペアデバイス=0
/dev/sda1 /dev/sdb1 = RAID1 デバイス 0 # md0(boot)
/dev/sda2 /dev/sdb2 = RAID1 デバイス 1 # md1(LVM)

２つのHDDの４領域を、/dev/md0,/dev/md1 に組み合わせる。

boot領域の設定
　> RAID1 デバイス 0. - 128MB ソフトウェアRAIDデバイス
　>  1. ---- 128 MB   ext4   /boot
　> RAID1 デバイス 1. - 128MB ソフトウェアRAIDデバイス
　>  1. ---- 500 GB K lvm    # vg00(lv00:swap,lv01:root,lv02:home)

/dev/md0は、/boot に割り当てる。 /dev/md1は、lvm に構成させるために、領域種別には lvm を指定する。

LVMの設定
　論理ボリュームマネージャの設定
　　ボリュームグループの作成
　　　ボリュームグループ名 = vg00
　　　ボリュームグループデバイス = /dev/md1
　　論理ボリュームの作成 ( vg00 上)
　　　論理ボリューム名 lv00 =  12GB (swap用)
　　　論理ボリューム名 lv01 = 128GB (root用)
　　　論理ボリューム名 lv02 = 380GB (home用)
　> LVM VG vg00, LV lv00 -  12 GB Linux device-mapper(linear)
　>  1.  12 GB K スワップ スワップ
　> LVM VG vg00, LV lv01 - 128 GB Linux device-mapper(linear)
　>  1. 128 GB K ext4 /
　> LVM VG vg00, LV lv02 - 360 GB Linux device-mapper(linear)
　>  1. 360 GB K ext4 /home

lvm を論理ボリューム vg00 に全て割り当て、その中を swap用、root用、/home用に区分けして、それぞれ割り当てる。

最初は、インストール後に再起動をかけたけど、bootしてくれない。試行錯誤を繰り返すが原因がつかめなかったが、RAID設定が外れている状態でも、異様な遅さがあったので、RAID処理が行われている雰囲気があった。んで、最終的に、BIOS の設定で、Software RAID の設定があったので、単独のHDDと認識するように設定を変更したら無事bootしてくれるようになった。

電子情報工学科

月別アーカイブ: 4月 2011

リンク集

検索・リンク

今日は体育祭

再帰処理の速度分析

プログラムと再帰方程式

創造工学の導入実験でPerlと正規表現

数値の型とN進数

N進数

2011年4月24日(第213回)

Windowsマシン消滅

手続き抽象・データ抽象

オーダ記法

2分探索法の分析

オーダ記法

変数の寿命と有効範囲、関数と引数

大域変数・動的局所変数・静的局所変数

関数と引数

新サーバのRAID化

投稿ナビゲーション

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー

メタ情報