例年だと解説していないんだけど、大学編入試験あたりで出題されている場合もあるし、 探索方法にこだわらなければ、難しい内容でもないので、グラフについて説明。

(0)--(1)--(3)--(4)--(5)--(7)
|              |    |
(2)------------(6)---+

上図のような、ノード間の接続状況を覚える場合、各ノードの接続を0/1で覚える 隣接行列がよく使われる。この例では、無向グラフだけれど、 ノードi番からｊ番につながっているものをa[i][j]=1で覚えれば、 有向グラフでも扱える。 実際のプログラミングでは、ノードを駅、路線を隣接行列で覚えるが、 隣接行列に、駅間の運賃を保存する場合も考えられる。(重み付きグラフ)

この隣接行列で、始点を与えた時のすべての経路を求めるプログラムは、 以下のようになる。

#include <stdio.h>
#define N 8
int a[N][N] = { // 隣接行列(無向グラフ)
{0,1,0,0,0,0,0,0} ,
{1,0,1,1,0,0,0,0} ,
{0,1,0,0,0,0,1,0} ,
{0,1,0,0,1,0,0,0} ,
{0,0,0,1,0,1,0,0} ,
{0,0,0,0,1,0,1,1} ,
{0,0,1,0,0,1,0,1} ,
{0,0,0,0,0,1,1,0}
} ;
// 訪問フラグ
int flag[N] = {0,0,0,0,0,0,0,0} ;
void visit( int i ) {
flag[i] = 1 ;
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

このプログラムでは、訪問可能な先が、未訪問であれば訪問する…という処理を、 再帰によって行っている。

メモリ節約のために2進数で…

このプログラムでは、隣接行列や訪問フラグには、0/1の論理値しか保存していないのに、 int型(32bit-CPUで4byte)を消費してもったいない。 論理値0/1の配列を、2進数のbit列で扱えば、メモリを節約できる。
# 節約目的というより、2進数の取り扱いは、情報処理試験や
# 大学の編入試験での出題もあるから…

各種試験を考えると、下の赤線部あたりが理解できる/書けるというのがキモ。

#define N 8
int a[N] = {
0x02 , // {0,1,0,0,0,0,0,0} → 0000,0010
0x0D , // {1,0,1,1,0,0,0,0} → 0000,1101
0x42 , // {0,1,0,0,0,0,1,0} → 0100,0010
0x12 , // {0,1,0,0,1,0,0,0} → 0001,0010
0x28 , // {0,0,0,1,0,1,0,0} → 0010,1000
0xD0 , // {0,0,0,0,1,0,1,1} → 1101,0000
0xA4 , // {0,0,1,0,0,1,0,1} → 1010,0100
0x60 , // {0,0,0,0,0,1,1,0} → 0110,0000
} ;
int flag = 0 ;
void visit( int i ) {
flag |= (1<<i) ;
for( int j = 0 ; j < N ; j++ ) {
if ( (a[i] & (1<<j)) && (flag & (1<<j))==0 ) {
printf( "%d->%d " , i , j ) ;
visit( j ) ;
}
}
}
int main() {
visit( 0 ) ;
return 0 ;
}

ちょうど、C++のテンプレートなどを使ったプログラミングを確認していたので、 STLを使って書いてみた。 配列宣言とか初期化以外の部分は、最初のプログラムと同じように書けるのが C++のテンプレート機能のおかげ。 bitsetは、論理値の配列を内部的にはbit演算で行ってくれるクラス。 vectorは、指定型で配列サイズが動的なもの。

#include <iostream>
#include <bitset>
#include <vector>
#define N 8
using namespace std;
vector< bitset<N> > a ;
bitset<N>           flag( 0x00 ) ;
void visit( int i ) { // 最初のプログラムとまるっきり同じ
flag[i] = 1 ;       // 内部的にはbitsetのおかげで2進数演算
for( int j = 0 ; j < N ; j++ ) {
if ( a[i][j] == 1 && flag[j] == 0 ) {
cout << i << "->" << j << " " ;
visit( j ) ;
}
}
}
int main() {
a.push_back( bitset<N>( 0x02 ) ) ;
a.push_back( bitset<N>( 0x0D ) ) ;
a.push_back( bitset<N>( 0x42 ) ) ;
a.push_back( bitset<N>( 0x12 ) ) ;
a.push_back( bitset<N>( 0x28 ) ) ;
a.push_back( bitset<N>( 0xD0 ) ) ;
a.push_back( bitset<N>( 0xA4 ) ) ;
a.push_back( bitset<N>( 0x60 ) ) ;
visit(0) ;
return 0 ;
}

プログラム末尾の配列a[]の初期化が、ちょっと美しくない。 C++では、配列は、無引数のデフォルトコンストラクタで初期化される。 しかし、引数付きで初期化したい時もあるんで、調べてみたら、 "placement new"なんて機能があるみたい。

vector< bitset<N> > a( 8 ) ;
int table[N] = {
0x02 , 0x0D , 0x42 , 0x12 , 0x28 , 0xD0 , 0xA4 , 0x60 ,
} ;
int main() {
for( int i = 0 ; i < N ; i++ )
new( &a[i] ) bitset<N>( table[i] ) ;
:
}

たしかに便利なコンストラクタの強制呼び出しなんだけど、 このコードだと、要素についてデフォルトコンストラクタと、 placement new のコンストラクタの2回が呼び出される。 placement new の実行前に、デストラクタって呼び出されるの？ なんか気持ち悪い…
# 試してみたけど、placement new の前にデストラクタが呼ばれることはないようだ…

画像処理の制御ネタで、PTAMを使って…と思っているのだが、 実際にコードを見てみると、C++のテンプレートやらauto_ptrやらを、 たっぷり使っている。 まだまだC++でも理解不足があるので、 改めてSTLやらコンテナやらを読み直し。 以下のページは、説明がなかなかよくまとまっている。

• C++編（標準ライブラリ）

情報構造論のテストで、このあたりの基本データ構造をCで書いて出題するのもアリだよな…

周囲でのインフルエンザの拡大の中、 今日は今シーズン最初の4Eにてクラス閉鎖が発生となった。

そして、今日担任クラスでも1名のインフルエンザが発生した。 電子情報の現状は、以下の通り。

3年 インフルエンザA?×2名
4年 インフルエンザB(寮生)×1名
5年 インフルエンザA×1名
　　インフルエンザB×2名
　　類似症状および欠席×4名

データベースの内部構造の説明として、排他処理やB木について解説を行う。

トランザクションとは、首尾一貫したデータに対する一連のデータベースの操作の集合で、 データの一貫性が保証されなければならない。 (A)原子性、(C)一貫性、(I)隔離性、(D)耐久性が重要であり、 一貫性を完全に反映させたCOMMIT状態から、トランザクションを受けつけ、 一貫性が保証されない時はROLLBACK文により処理が無かったものとして、 改めてトランザクションを行ったりする。

排他処理

トランザクションは並行して行われたりするが、一貫性を保つために順序が重要。 同時実行制御では、(a)ロッキング方式、(b)時刻印方式(更新の不都合の検知にタイムスタンプを使う)などがある。 ロッキング方式では、ロックの粒度（カラム/レコード/テーブル/DB全体)も重要。 粒度が大きいと、排他処理で待ちが増える。 ロックの種類には、共有ロック(Readロック:一般的に読み出しで他のアクセスを許す)や、 専有ロック(Writeロック:書き込み時で他のアクセスを許さない)がある。 ロックで排他状態になれば、待たされる…

ロックでは、資源解放を待つ状態になるが、資源が複雑に絡み合い、お互いがUnlock待ちになると、デッドロック状態が発生する。これを防ぐために、(a)ロックの一括獲得、(b)使用データの順序付け、(c)トランザクションの優先順位などを設けたりするけど、完璧なデッドロック解消は不可能。

DB内部構造：B木

2分木などの方式では、データの登録順序によっては木の左右のバランスが悪くなって、 検索効率の低下が発生する。2分木であれば、AVL木の手法でバランスを取るけど、 面倒な処理となる。

B木では、１つの節は位数Nのデータと、N+1件の節へのポインタを持つ。 １つの節の中のデータ件数は、N/2以上、N以下になるようにする。 データをB木に追加する時、データ個数がN+1個になった時、 中央値のデータを、上位ノードに繰り上げて２つの節に分ける。 このようにすることで、木のバランスを保つようにする。 (参考：昨年度資料)

Wikipediaより引用

Wikipediaより引用

Webのニュースを見ていたら、鹿児島の内之浦のロケット発射場で、 再びロケットが打ち上がることになったらしい。

昨年はハヤブサの成功で、JAXAも鼻高々の状態だけど、 前回の担任で工場見学にて訪問した際は、 ロケット発射は種子島ばかりで…との説明だっだなぁ…

1/13に、「就職活動の心得」ということで、 福井県就職者支援センターの方を招いて、本科4年・専攻科1年対象に講演会が行われた。

まずは就職の説明から始まり、新卒は「育成し次世代を担う人材」を採用、 中途採用は「退職者の人材の補填」が採用の目的で違うこと、 だからこそ新卒採用は「意欲・熱意・向上心」を持っていることが評価の対象となる。 就職では、最初から適職な職場が見つかることはほとんどない。 だからこそ複数の会社に応募して内定をもらうことは、ある意味「会社と自分の縁」だし、 そこからの仕事の中で「自分で適職となるようにする」という考えが大切。

会社での選考試験では、面接や試験結果での比較して大きく違う訳ではない。 だからこそ面接での第一印象はすごく大切。 第一印象は(1)身だしなみと(2)礼儀(マナー)が大切。 面接重視といっても「みかけによらず」という人もいるかもしれないが、 こういう人は少数派。 厳選した採用の場合、みかけによらず…を採用といったriskyなことは少ないはず。

ということで後半は、各クラスから代表１名に出てきてもらい、 挨拶や会釈・礼といった時の体の角度にいたる説明や、座った際の姿勢といった 面接での第一印象を良くするための方法をレクチャしてもらう。

PTAMを使って、マーカ・レスでロボット制御の卒研を期待して、 MacBookAirを購入。PTAMを動くようにしてみたけど、制御にまで 話を続けるために、もう少し基礎勉強。 解説サイトがあるので、以下にまとめる。

• PTAMの解析-1
• PTAMの解析-4 動画の公開

先週に引き続き、動的メモリ領域の管理法の説明を行う。 最初に先週の領域サイズが固定ならば、freelist で管理可能という話と、 「最後に確保したメモリが最初に不要となる…」というのであれば、 スタックで管理が可能という話をしておく。

自由な領域サイズでのmalloc+freeでは、一般的に 次の領域へのポインタと、そのブロックのサイズを使って管理を行う。 このブロックをfreelist でリスト構造にして保存している。

mallocの処理

mallocでは、freelistの中から、要求サイズより十分大きいブロックを探すか、 要求サイズと同じサイズのメモリブロックを検索する。

要求サイズと同じブロックが見つかった場合は、そのブロックを迂回するようにポインタをつなぎかえる。(上図の青) 要求サイズより大きなブロックが見つかった場合は、その領域の後半を切り分けてユーザにメモリを貸し出す。この場合は、ブロックサイズの修正だけ。(上図の赤)

freeの処理

freeでは、返却された領域をfreelistに接続すればいいが、 このままではメモリ領域が細切れになるだけで、 最終的に大きなメモリを確保できなくなってしまう。 このため、返却されたメモリブロックは、freelist内に隣接する領域が無いか検索され、 隣接するメモリブロックと併合する。

一般的に次のメモリブロックへのポインタは、昇順方向になるように接続する。 また、mallocやfreeの処理での freelist 内の検索が行われるため、ヒープホールが 大量発生しているような状況では、処理効率の悪さが問題となる。 この辺の処理を簡単にするために、freelist をメモリブロックの大きさ毎に複数使う方法もある。

補足説明として、実際にユーザが要求したメモリとは別に、nextポインタとブロックサイズを 記憶する必要があるため、小さいメモリ領域をmallocで使うとメモリ使用効率が悪いことを 説明する。また、メモリブロックのサイズは、ワード境界のことを考慮して、4の倍数(32bitコンピュータならば)に切り上げられることを説明する。

ワードアライメントやheap管理データの領域が無駄といった話だけだと、 メモリ倹約至上主義で時代遅れと言われかねない。 補足説明として、メモリ増設もマザーボードから変えなきゃムリって場合はハードウェアの価格に影響が出ることと、 メモリ浪費で仮想メモリが使われだすとスラッシングで処理速度の低下の弊害を説明する。