2012年4月29日(第266回)
ゲスト 体育長 4年電子情報工学科 木下さん、OB 五十嵐さん
- 体育祭について
- 就職試験について
- ゴールデンウィークの過ごし方
OBの五十嵐さんが大学お土産をスタジオに持ってきてくれました！
今日は体育祭
晴天の中、昨日の順延を受け、本日が体育祭です。
ハノイの塔とマージソートの分析
再帰呼び出しを含む処理の、速度分析の説明として、ハノイの塔とマージソートを 説明する。
ハノイの塔
ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、
ということが予想される。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、
ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、
枚では、
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
マージソートの処理速度分析
最も高速なソートアルゴリズムとして、クイックソートがあげられる。 しかし、説明が分かり難いので、同じ処理速度のオーダとなる、 マージソートの分析で説明する。
マージソートのアルゴリズムは、
- データが１件の時は、そのまま。
- それ以上の件数では、
- データを中央で２分割して、それぞれをマージソートを行う。
- 出来上がった２つのデータ列を、先頭から２つを比較し小さい方から移し替える。
この方式であれば、再帰方程式として、以下の式が示される。
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年物質工学科 山野さん、松島さん
体育祭の応援練習
まだ練習も始まった所、本人達自身から『なんかラジオ体操っぽくね？』の声。
うん、私もそう思う。
# でも、本番では例年かっこよく決めてくれる….
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 ２分探索法 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の補数表現の説明追加が必要かな。