ホーム » 2012 » 4月

月別アーカイブ: 4月 2012

2012年4月
« 3月   5月 »
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2012年4月29日(第266回)

ゲスト 体育長 4年電子情報工学科 木下さん、OB 五十嵐さん

  • 体育祭について
  • 就職試験について
  • ゴールデンウィークの過ごし方

photo120429.jpg

OBの五十嵐さんが大学お土産をスタジオに持ってきてくれました!

今日は体育祭

晴天の中、昨日の順延を受け、本日が体育祭です。

1204271208_640x480.jpg

ハノイの塔とマージソートの分析

再帰呼び出しを含む処理の、速度分析の説明として、ハノイの塔とマージソートを 説明する。

ハノイの塔

ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、


ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、



となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

マージソートの処理速度分析

最も高速なソートアルゴリズムとして、クイックソートがあげられる。 しかし、説明が分かり難いので、同じ処理速度のオーダとなる、 マージソートの分析で説明する。

マージソートのアルゴリズムは、

  • データが1件の時は、そのまま。
  • それ以上の件数では、
    • データを中央で2分割して、それぞれをマージソートを行う。
    • 出来上がった2つのデータ列を、先頭から2つを比較し小さい方から移し替える。

この方式であれば、再帰方程式として、以下の式が示される。


N=1,2,4,8,…と、代入を繰り返すと、処理時間は、 であることがわかる。

複素数のクラスと隠蔽化

前回までで、オブジェクト指向でのクラスの説明が終わったので、 class宣言の外にメソッド実体を書く方法(クラス限定子"::")や、 inline宣言などを説明し、実際の例として複素数クラスを用いて演習にとりかかってもらう。

// 直交座標系
class Complex {
private:
double  re , im ;
public:
inline Complex( double r , double j )
: re( r ) , im( j ) {}
inline void print() {
printf( "%lf + j%lf" , re , im ) ;
}
inline void add( Complex& z ) {
re += z.re ;
im += z.im ;
}
} ;
void main() {
Complex a( 1 , 2 ) ;
Complex b( 2 , 3 ) ;
a.add( b ) ;
a.print() ;
}
// 極座標系
class Complex {
private:
double  ab , th ;
public:
inline Complex( double r , double j )
: ab( sqrt( r*r + j*j  ) ) , th( atan2( j , r ) ) {}
inline void print() {
printf( "%lf ∠ %lf" , ab , th ) ;
}
inline void add( Complex& z ) {
// 演習のネタ
}
} ;

直交座標系のクラスと、極座標系のクラスにて、 複素数の加減乗除のメソッドを実装し、 これにより隠蔽化が可能で、クラス内を変更(リファクタリング) しても利用者に影響が少なくできることを体感してもらう。

fvwmとかgwmって、いつの時代やねん…

電子情報のメインサーバも oldstable のままなので、 移行作業を始めるための準備。 使うだろうと入れてあるけど、実質使っていない gnome やら kde やら を削除したあと、aptitude をかけた時に競合パッケージを減らすために、 利用頻度が低いパッケージを目視で削除中。

ただ、fvwm-data やら gwm-data といった、過去の遺物のパッケージ名が 未だにインストールされてた。(さすがにバイナリは競合の中消えてしまっている)

もう少し、要らないパッケージを消して、夕方あたりから本格的な更新作業を 行うかな….

uptime 200を超えると再起動おそ…

ようやく、主要パッケージだけにできたので、更新作業を夕方から行った。 確認すると、uptime 250日。再起動をかければ、まちがいなく fsck が起動するから、 再起動中に他の方からのクレームが来ないか心配しながらの再起動。

途中、grubでなくLILOのブート画面に、クラクラしながらも、ルート,/home の fsck にイライラしながらの再起動が完了。 後は、監視系の munin , nagios3 を入れて、足場を固める。 gnome,KDEの再インストールとも思うが、ニーズが出るまではやめておこう。

2012年4月22日(第265回)

  • クラブ紹介 陸上部
  • 新レギュラー自己紹介 1年物質工学科 山野さん、松島さん

体育祭の応援練習

まだ練習も始まった所、本人達自身から『なんかラジオ体操っぽくね?』の声。
うん、私もそう思う。
# でも、本番では例年かっこよく決めてくれる….

1204201636_739x512.jpg

oldstableをstableに

学科サーバやらアンケートシステムやらで、 Debianベースで色々なサーバを運用しているけど、 どれも5年近くの稼働。

きちんと更新はかけているけど、lenny から squeeze に 上げるのが面倒で、squeeze 登場の時に oldstable/lenny だけに sources.list を書いて運用していた。 しかし、さすがに oldstable のメンテナンス期間も過ぎ、 最近は、"aptitude safe-upgrade"かけても更新が無い。 限界。

ということで、メイン稼働でない oldstable なサーバで、 stable 切り替えを行う。ただ、大きな変更だけあって、 パッケージ間競合で、うまく自動更新スクリプトが止まらない。

何台か作業したけど、以下の手順だと競合が少ないかな。

aptitude install aptitude
aptitude install gcc g++
aptitude install apache2 php5
aptitude install xserver-xorg
aptitude install gnome
# kdeと競合が多いけど、ばっさりkdeを一時的にremove...

ああ、サーバなのに使ってもいない gnome , KDE なんか、 こんなに律儀にインストールしてるんだろう…>オレ。

PHPが一般ユーザで動かなくなる

更新をかけたら、一般ユーザでのPHPが動かなくなる。 でも、自分のホームでは、動く。さっぱり訳の分からない状況で、 userdir が原因と疑い、検索をかけたらようやく解明。 PHP 5.3 あたりから、安易にユーザがPHPコードを使えないように、 設定ファイルが、変更されてる。

自宅サーバでは、問題なく動いていたし、設定ファイルを比較しまくったのだが、 違いが見つからず、解明まで時間ががかった。 自宅では、mod-enabled/userdir.conf は触らずに、 conf.d/php5.conf で設定していたものだから、気付くまでに手間取ってしまった。

(( /etc/apache2/conf.d/php5.conf ))
<IfModule mod_php5.c>
<IfModule mod_userdir.c>
<Directory /home/*/public_html>
php_admin_flag engine on
</Directory>
</IfModule>
</IfModule>

オーダ記法と再帰関数

先週は、単純サーチ、最大選択法などの説明だったので、 2分探索方の説明を行い、

単純サーチ T(N) = Ta + Tb×N
最大選択法 T(N) = Ta + Tb×N + Tc×N^2
2分探索法 T(N) = Ta + Tb×log N

これらのTa,Tb,Tcは、計算機の性能に依存し、アルゴリズムの優劣判断には使えないので、 これらを記載しないオーダ記法を用い、 O(N) , O(N^2) , O(log N) のように記載する。

再帰関数

for 分による繰り返しの分析ができても、再帰処理を含む場合は、面倒になる。

以下のような再帰関数を示し、動作トレースのあと、一番簡単な fib について、 処理時間を示す。

int fact( int x ) {
if ( x == 0 )
return 1 ;
else
return x * fact( x - 1 ) ;
}
int fib( int x ) {
if ( x < 2 )
return 1 ;
else
return fib( x - 2 ) + fib( x - 1 ) ;
}

変数のスコープと寿命、数値の範囲

制御構文の説明の後として変数の説明、数値の範囲を説明。

int x=123; // 大域変数
void foo( int x ) { // 局所変数の仮引数。
x++ ;
printf( "%d" , x ) ;
}
void main() {
int a= 234;
foo( a ) ; // 235 値渡しでコピーされる。
foo( a ) ; // 235
}

関数の書き方の説明をしたけど、値渡し、ポインタ渡しの説明が不完全。 来週は、値渡し、ポインタ渡しを説明。

数値の範囲

char , short int , int , long int 、unsigned , signed といった型を説明。 数値の範囲は、他の授業で丁度やっていたので、すんなり説明が終わる。 ただし、2の補数表現の説明追加が必要かな。