先日のプロコンで、課題部門の作品(WT)に興味をもってくれた スペースタイムエンジニアリングさんの紹介で、DTN(遅延耐性ネットワーク) のワークショップに参加。災害時のネットワークを意識した 様々な発表があった。 以下、実験中で公式発表でないものもあるので、キーワードだけ抜粋。

オフローディング：災害時のネットワークでは、混雑して使えない時は、 (a)時間的(空いてる時に送る)、 (b)空間的(つながる場所に移動して送る)、 (c)通信経路的(WiFi,3G,LTEなど通信路を切換えて送る)

蓄積運搬型のデータ伝送：FireChatなどのすれ違い時にデータを蓄積 運搬するデータ伝送では、端末密度の違いに応じて送り方を変えないと、 無駄なネットワーク通信が発生する。 高密度の場所では、広範囲の交信履歴のある効用値の高いものに送る。 低密度の場所では、区別せずに送る。 GPS情報で有効なすれ違いができた場所を記憶するとどうかな？

蓄積運搬型で、過密度の場所ですれ違いする場合には、マルチキャストや ブロードキャストで配信できないか？

南紀白浜で、被災時のネットワークがどうなるか、人や車の動きを考慮 したネットワーク状況をシミュレーション。観光地であれば、 旅行者2万人、住人1万人程度の想定が必要。 被災時には、メッシュネットワーク構築が重要。ルータにユーザ通信用、 WiFiメッシュネット構築用の2系統を付けて、平常時はFree WiFiスポット で災害時にWiFiスポット間通信でメッシュネットを構築させたい…

災害時にメッシュネットを効率よく構築したい。自律ロボットが、 ZigBeeのAPをばらまいてメッシュネットを構築させたい。 電波強度が限界に近づくと2つ目のZigBeeのAPを落としていく。 直進しながら距離を稼ぐメッシュネット構築。 または、自律ロボットがAPとなり、隣接APと電波強度がギリギリに なるまで、拡散移動し、面積的な広範囲のメッシュネット構築。

すれ違い通信時に端末の軌跡情報を元に、通行不能場所を推定できないか？

すれ違い通信でBLEでは、送れる情報が少ない。WiFiを併用して通信量を増やしたい。 BLEでWiFiのSSID等の情報を送って、その後はWiFiをDirect通信に 切り替えて、大量通信を行う。WiFiのDirect通信切換えにかかる時間が問題。

StarBEDの活用事例として、災害時ICT検証のプラットフォームNERVF。 若狭湾周辺の災害時ICT挙動シミュレーションに取組中。

災害時に人の存在情報のセンシングができないか？ スマートフォンの加速度＆音情報で混雑検出ができないか？ 群衆を撮影したツイート画像から、混雑情報を検出できないか？ 背景差分法で、同一背景でなくても、特徴量検出で対応箇所をマッピング してから、背景差分を行えば若干の撮影位置の違いがあっても、 背景差分法ができる。 風景写真でオプティカルフローを求めると地表面が求まるので、 地表高を考慮すれば、誤情報をrejectできるはず。

2分探索木のテスト問題にて、以前にも同様の出題をしたけど、 再び….

先日導入を悩んでいたChromebookが届いた。余計な機能も無いし、 サックサク。キー入力も設定の中に検索,Controlキーの変更もあり 使い勝手の悪さの第一ハードルはなくなった。

しかしちょいと慣れだすと、無意識にカーソル移動にCtrl-Nとかの emacsキーバインドで操作して、その度にウィンドウが開いて、軽くイライラ。

でも、これなら、学生さんがレポートとかでGoogle Docsにはなるけど、 慣れちゃえばこれでパソコン仕事は十分とも思えてくる。 ネットワークが繋がらないところでどの程度使えるのかがカギかな。

プログラミング環境が無いし、どの程度で演習に使えるかと思ったけど、 Ctrl+Alt+Tで"chrome-OS"のshellに抜けることができる。 機能の中にはssh接続もあるし、これでサーバに接続すればなんでもアリじゃん…。 と思ったのだが、ssh経由でサーバにつないでemacs使ってプログラム編集をしようとしたら、 相変わらずCtrl-Nでウィンドウ開くわ、カーソル操作でもエスケープシーケンスの問題なのか反応がおかしくなる。

個人的には、じゃあ vi でいいじゃん…と思うけど、学生さんにはなぁ…

使い勝手の実験ということで、会議の議事録をChromebookで頑張ってみた。 入力速度や漢字入力の操作性では、問題は無かったけど、 ChromeブラウザでのEvernote Web版(Beta)を使ったのがマズかったかな。 範囲指定して、文字装飾かけると、文字が消えてしまう…(x_x;; Ctrl-Zで復活させると装飾がかかって復活してくれるけど…. 古いWeb版にしても、装飾かけると文字が消えるのは、相変わらずか…ダメじゃん。

今朝、演習室に入ったら、「ぐぉ〜ん」という音が部屋中に響いている。 今までの経験で、HDDとかの異音はもう少し音が高音域だし、 サーバからの悲鳴のメールは飛んでいないので、改めて音の方向に行くと、 EthernetのGiga-SW-HUBが音を出している。

16ポートの排熱FAN付きなので、排熱FANのベアリングが壊れたとしか 思えない。修理も考えるけど、8ポートのGiga-HUBが5000円程のご時世だし、 8ポートの購入することにした。

ほぼ同型の現行後継機種のHUBもあるけど、大型だけあって、 排熱FANがついている様子なので、FANナシ8ポート2個で、 設置形態も適当にやりくりすれば、利便性もあがるだろう…

トラブルが起こる時は、続くもんだ…
自室の"Drobo S"(異なるサイズのHDDで特殊なRAID化できるHDD-NAS)の1個が故障。 HDDが故障のメールを吐いて、空き領域を使って残り4個で冗長化するための再構築処理が始まった。 発注したHDDが届いたら、故障HDDを取り除いて差し替えるだけなので、復旧は極めて簡単(の予定)。

先週が演習課題で、未完成な人も多いので、前半講義、後半演習とする。

ビューテーブル

データベースでプログラムを作る場合、3層スキーマ構成で考えることが多い。 概念スキーマ、内部スキーマ、外部スキーマ。 ビューテーブルは、外部スキーマに相当する。

使い方としては、元々複数のテーブルで扱われているデータを、 あたかも合成したテーブルがあるかのように扱えるもの。

((成績データベースを例に...))
[成2]　こういうシンプルな表だと分かりやすい
名前 |科目|担当|点数
Aさん|ＤＢ|斉藤| 65
Bさん|電磁|高久| 73
Cさん|ＤＢ|斉藤| 45
　
　　　でも修正不整合などを防ぐには...
[成]
名前 |科ID|点数
Aさん|1000| 65
Bさん|1020| 73
Cさん|1000| 45
　
[担]
科ID|科目|担当
1000|ＤＢ|斉藤
1020|電磁|高久
create view 成2 (名前,科目,担当,点数)
as select 成.名前, 担.科目, 担.担当, 成.点数
from 成, 担
where 成.科ID = 担.科ID ;

データベース組込み言語

データベースの処理のプログラムを実際に記述する場合、C言語などで扱う場合は、 特殊なSQL埋め込み用の機能を用いて記述する場合が多い。 select文などを埋め込むと、各要素を処理するためのループ命令が作られ、 カーソルという概念で1件づつの処理を繰り返してくれる。

SQLの埋め込みなどの機能でプログラム言語と整合性の高いものは、 COBOLが一番有名。しかし、COBOL自体は歴史の長い言語であり、 最近の金融系では、COBOLプログラマが定年でプログラムを改良できる技術者不足などが原因の トラブルが多いことも雑談として説明しておく。

情報構造論は、先日のB木の説明をした所なので、 データベースの一般的な話をする予定だったが…

Webサービスとデータベースと負荷分散

でも、一般的なWebシステムでの負荷分散の話を知ってて 欲しかったので、 (1)大量のユーザの相手を負荷分散で処理するWebサーバ、 (2)そのWebサーバの裏でデータベースの処理をする スレーブ・データベース・サーバ、 (3)そのスレーブサーバの中核となるマスターデータベースサーバ の3段構成となっていることなどを説明する。

また、こういったWebシステムでは、早急なサービス提供開始が 必要となるから、安価なLAMP(Linux+Apache+MySQL+PHP)の コンピュータシステムで実現することが多いことを説明する。

LAMPシステムでサービスを開始すると、サービス提供の最初であったり、 システムが話題になったりと、インターネットでの情報によって、 サービス利用者は増減する。しかし、利用者が増えてサービス性能が 低下するのを防ぐ場合には、コンピュータの増設が必要となる。

仮想コンピュータ

しかし、物理的なコンピュータの増設は、管理の手間や導入費用、 さらに利用者が減った際に、遊休のコンピュータができるなど、 問題も多い。そこで、最近のコンピュータは1台の中に、 複数のCPUを持っていることから、仮想サーバ機能で、 必要な時に必要な量のコンピュータを一時的に借りるなどの 方法が取られる。

この際に、出来上がったソフトウェアを借りる(SaaS)、 プログラムを動かす基盤を借りる(PaaS)、 仮想コンピュータのCPU,MEM,HDD,NETを借りる(IaaS)などの 方式がある。

様々なプログラム言語

このWebサービスを動かすにあたり、 サーバ側であれば、PHPやPerlといったプログラム言語が使われたり、 Java等が使われる。そのデータ処理で、SQLなどの言語も使われる。

一方でクライアント側では、昔であれば静的なHTMLページを 記述したけど、ページ遷移は全画面同時に起こるため、 操作性が悪い。このため、以前であれば Java が使われた。 しかし、Java はブラウザの中の特定枠の中で動かされ、 ブラウザと連携するのは困難であった。そのため、JavaScriptなどが 開発され、画面の必要な部分だけ通信しながら処理を行う AJAX技術が発達してきた。それに合わせ、HTML5や画面レイアウト の記述であるCSSなどの考え方も重要となってきた。 そうすると、CSS,JavaScript,HTMLなどを自分で組合せて記述するのは 大変なので、jQueryなどのライブラリが普及してきた….

今日は、2分木を用いた式の表現とB木について説明を行う。 前回、２項演算子の話で、逆ポーランド記法などの説明をしたので、 そのプログラム例から話を行う。

逆ポーランド記法のスタック処理

逆ポーランド記法による式は、スタックを用いると簡単にその値を求める処理が記述できる。

// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '
// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '\0' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}
' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}

2分木による式の表現

これが本来説明したい2分木による式の表現。 データ構造を簡単にしたいので、 左右の枝がNULLなら、opr部に整数値、非NULLなら、opr部に演算子の文字コードとする。 この方式であれば、要素名は異なるものの、２分木のデータ宣言とまるっきり同じ。

// まずはデータ構造の宣言と、そのデータを生成する補助関数。
struct Expr {
int opr ;
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の場合
struct Expr* Integer( int x ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = x ;
ans->left = NULL ;
ans->right = NULL ;
}
return ans ;
}
// 演算子の場合
struct Expr* Operator( int op ,
struct Expr* l ,
struct Expr* r ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}

データ構造を作る処理が記述できたところで、その式の表示と、その式の計算。

// 2分木による式を表示する関数。
// 演算子の優先順位を無視して、全てにカッコをつける
void print_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
printf( "%d" , e->opr ) ;
} else {
printf( "(" ) ;
print_expr( e->left ) ;
printf( "%c" , e->opr ) ;
print_expr( e->right ) ;
printf( ")" ) ;
}
}
// 式の値を計算する関数
int eval_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->opr ;
} else {
switch( e->opr ) {
case '+' :
return eval_expr( e->left )
+ eval_expr( e->right ) ;
case '*' :
return eval_expr( e->left )
* eval_expr( e->right ) ;
}
}
}
// 実際に計算させてみる。
void main() {
struct Expr* e
= Operator( '*' ,
Integer( 1 ) ,
Operator( '+' ,
Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval_expr( e ) ) ;
}

B木

2分木で式の表現を説明したが、枝の数は左右２本と限定する必要はあるのだろうか？ 2本をN本に拡張したものが、B木と呼ばれる。

// 位数2のBTree
struct BTree {
int size ; // B木のノード内のデータ数
int d[ 4 ] ; // 実際のデータ
struct BTree* p[ 5 ] ; // d[i] < ● < d[i+1] のデータは、
// p[i+1]の枝に保存
} ;

B木では、枝に関する条件に加え、位数Nの場合では、ノード内のデータ件数を必ず、 N <= (データ件数) <=2N を満たすようにする。

データの追加で、ノード内のデータ件数が2Nを越える場合には、 加えるデータを含め、データ順に並べた時の中央値を上位ノードに移動させ、 ノードを、左右に分割を行う。

|
　　[ 12 | 21 | 23 | 29 ]  ← 18を加えるなら、12,18,21,23,29 で、
　　　　　　　　　　　　　　　　　21を上位に上げる。
[ 8 |(21)| 39 | × ]
|    |
|    +---------------+
|                    |
[ 12 | 18 | × | × ]  [ 23 | 29 | × | × ]

先週の2分木の演習に引き続き、後半を演習とした。

前半では、プログラミングへの興味を持って欲しいし、 先週のプロコンの状況を紹介した。

課題部門での作品の背景として、FireChat というソフトがあり、 香港の学生デモでも活躍していたことを話す。 また、情報統制でインターネットでどういうことが発生するかということで、 FireWallによる制限や、DNS 統制などの雑談も行った。

演算子の話

2分木の応用で、式の取扱いを来週解説する予定なので、 演算子の一般的な知識を説明。

なにげない「1+2*3」という式も、演算子には優先順位があり、 「1+(2*3)」を意味している。この優先順位を()で表さないためにはどうすればいいのか？

C言語で使われている演算子も細かく分類すると、 単項演算子、2項演算子、3項演算子(条?真値:偽値)がある。 単項演算子も単純な「-(マイナス)、!(NOT)」という前置型の他に、 「++x , x–」といった前置・後置で処理が異なるものもある。 2項演算子も、「1+2+3」は「(1+2)+3」のように処理される左結合演算子と、 「x=y=0」が「x=(y=0)」として処理される右結合演算子があることを説明。

演算子の表記法にも、「1+2*3」を、「1,2,3,*,+」のように、 演算子の前に式を置く、後置記法(逆ポーランド記法)という方式もある。 逆ポーランド記法は、日本語の文法に近いということもあげられるが、 スタックを使い、『数値はスタックに詰む、演算子がでたらスタック上位の 2つの値を取り出し、計算結果を改めてスタックに詰む。』という処理を 繰り返せば、複雑な計算式も正しく値を求めることができる….といった説明を 行う。

ちなみに、「+,1,*,2,3」のような演算子を前に置くものは、前置記法(ポーランド記法)、「1+2*3」のような書き方は、中置記法と呼ぶ。