• 10/04 (卒研中間発表のメモ) #fnct
• 10/04 通信路のジャミングやリトライや通信遮断が、どの程度プログラム側が把握できるのか、実験が必要。 #fnct_卒研中間発表
• 10/04 成果として、 http://www.ei.fukui-nct.ac.jp/~t-saitoh/… が完成している。データストアの機能実装予定。農家の利用者側が見やすいWebインタフェースなモニタ環境作るぅ？ #fnct_卒研中間発表
• 10/04 @TohruSaitoh 安全マップネタに、他の卒研グループの人から、大量ダメ出し。例年の最終発表レベルが中間発表時点で完成していて、すばらしいんやけど… 私も鬼やけど、ほかの人も鬼やのぉ… #fnct_卒研中間発表
• 10/04 XBeeを用いたセンサーネットワークの構築：ビニールハウス制御システムなどを構築するために、組み込み機器用の無線ネットワークのXBeeを用いて、各所のセンサーを無線で収集し、それに応じた制御のシステムの構築を目標。 #fnct_卒研中間発表
• 10/04 緊急メールは現状で未実装。利用者側の一方的なメールアドレスの変更が大変かもね。緊急メール機能実装を期待。メール送信で写真付き記事投稿の機能実装を期待。(鬼と呼ばれそうだな…) #fnct_卒研中間発表
• 10/04 携帯で地図登録の際には、"現在位置取得"は可能？ 位置情報＆写真付きメールで地図登録ができると防災マップにも応用可能。緊急連絡メール機能の完成度は？ #fnct_卒研中間発表
• 10/04 地域安全マップの本格運用：Google Mapを用いた安全マップと緊急メールなどの今まで卒研でやってきた内容をGAE上で統合運用を目指す。 #fnct_卒研中間発表
• 10/04 外部DBのマルチSNS化は、SNSのグループなどを生かせなくなるかも。どういった落とし所が利便性が良いか？ #fnct_卒研中間発表
• 10/04 外部サーバDBに、事案情報・位置情報・グループ情報を記録し、Persistence API を使わなければ、外部サーバDB経由で、mixi,google,などのマルチSNS対応なシステムにできるんじゃねぇ？ #fnct_卒研中間発表
• 10/04 グループ管理の外部サーバに保存する情報は、Private流出の懸念から最小限が望ましい。んで、どこまで記録する？ このアプリ起動時に、どんなデータ参照許可を与える必要がある？ #fnct_卒研中間発表
• 10/04 地図の位置情報・事件事案情報は、PersistenceAPI保存？グループ管理の外部サーバのDBに保存？ #fnct_卒研中間発表
• 10/04 OpenSocialを用いたSNS上で動作する地域安全マップシステムの開発：SNSアプリのAPIであるOpenSocialを使って、利用者が地図上に安全情報を投稿できるようなシステムを目標、 #fnct_卒研中間発表
• 10/04 利用者の誘導ではカメラの条件が違うから、マッピングに失敗する可能性が高い。端末は固定の必要があるかも。 #fnct_卒研中間発表
• 10/04 マップ情報は、ファイルに吐き出すための関数などは実験済み？ #fnct_卒研中間発表
• 10/04 3Dデータを簡単に作れるようにするには？、カメラ内に動く物がどの程度あるとやばい？ #fnct_卒研中間発表
• 10/04 マーカレスARを用いた情報提示システム、PTAM拡張の複数マップ対応版PTAMMを使い、観光案内システムを作れないか… #fnct

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。

先週の2分木の概念を分かってもらうための基本に引き続き、 今週は2分木の様々な操作プログラムを説明する。

2分木と再帰

先週の授業の最後では、データ数カウントを再帰で説明したので、 違う視点の再帰ということで、ループ版の代わりの再帰版を説明し、 今週は課題の合計と全データ表示などを演習とした。

int find( struct Tree* p , int key ) {
if ( p == NULL )
return 0 ; // 見つからない
else if ( p->data == key )
return 1 ; // みつかった
else if ( p->data > key )
return find( p->left , key ) ;
else
return find( p->right , key ) ;
}

ちなみに、上記のようなfindは、処理の末端に再帰呼び出しが書かれているため、 一般的に末尾再帰呼び出しと呼ばれ、コンパイラによっては最適化によって ループ処理に置き換えられるかもしれない…といった説明もしておく。

void print( struct Tree*p ) {
if ( p != NULL ) {
print( p->left ) ;
printf( "%d" , p->data ) ;
print( p->right ) ;
}
}

上記のprintを演習とした際には、「全データを表示せよ」としか説明しなかったので、 学生さんの解いてくれたプログラムの表示順序をトレースし、 改めて上記のプログラムを示し、表示順序が「小さいもの順」となることを説明する。

データの追加処理

struct Tree* top = NULL ;
void entry( int key ) {
struct Tree** tail = &top ;
while( *tail != NULL ) {
if ( (*tail)->data == key )
break ;
else if ( (*tail)->data > key )
tail = &( (*tail)->left ) ;
else
tail = &( (*tail)->right ) ;
}
if ( *tail == NULL )
*tail = tcons( key , NULL , NULL ) ;
}

データの追加処理として、上記プログラムを示す。 この動作トレースにて、昇順済みのデータを与えた場合、 一方向にだけ伸びる効率の悪いO(N)木が生成される可能性を説明する。 さらに、この対応としてバランスを修正したAVL木について、紹介する。

2分木の利点欠点とハッシュ

最後にまとめとして、2分木の利点欠点をまとめる。 2分木は、検索がO(log N),追加もO(log N)であることを示す。 しかし欠点として、メモリの使用効率が悪いことなども説明。 この際に、配列の2分探索法は、データ追加では挿入場所を作るために、 データを(平均N/2回)ループでずらす処理が必要であり、O(N)で効率が 悪いことを説明する。そして、この改善のための方法として、 ハッシュがあることを説明する。

     +--+--+--+--+--+--+--+---+
index| 0| 1| 2| 3| 4| 5| 6|...|
value|53|28|76|13|30|62|90|...|
+--+--+--+--+--+--+--+---+
i番目のデータの
左の枝は、(i*2+1)番目
右の枝は、(i*2+2)番目

• 10/03 隔週(きまぐれ)サーバOS更新、なぅ。 #fnct

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。

OSの話の入り口として、プログラムの実行について説明する。 その前に、前回話のできなかった、unix,Linuxなどのサーバ系の説明も行った。 特にLinuxのオープンソースによる無料での利用と、携帯向けOSで利用されている ことなども紹介した。

プログラム言語

プログラム言語については、 最初に、機械語,アセンブリ言語の低級なプログラムから、 FORTRAN,COBOLといった最初の高級言語、 構造化プログラミングを取り入れながらC言語等が発達し、 最近ではオブジェクト指向などを取り入れた言語のC++,Javaなどの紹介をする。

このプログラムの実行の際には、あらかじめ高級言語のプログラムを機械語に直して 実行するコンパイラ方式と、必要に応じて機械語に直しながら実行する インタプリタ方式の説明を行う。 コンパイラでは実際にプログラムを動かす際に、元のソース・プログラムを 提供する必要がないことから、技術流出の心配が最小限にできることを紹介。 一方インタプリタ方式は、コンパイルの時間をかけずすぐに動作試験ができる特徴 などを紹介する。

コンピュータの主要構成とプログラム起動

コンピュータの主要な構成が、CPU,メモリ(主記憶),補助記憶(HDD),入出力装置で あることを紹介する。 特にメモリが不揮発性のROMと、揮発性のRAMの2通りがあり、 通常のメモリがRAMであることから、電源が切れてもOSが動く理由を説明する。 (1)必要最小限のROMに、BIOS(基本的な入出力装置の制御プログラム)と、 ブートローダ(OSを起動させるプログラム)が記録されている。 (2)電源が入ると、BIOSを使ってブートローダが、補助記憶装置内の OSを主記憶メモリに読み出し、OSが起動する。 (3)OSが起動すると、ユーザのアプリケーションの起動に合せ、 アプリケーション・プログラムをメモリに読み出し動作する。

この様なコンピュータの起動の説明に加え、サスペンドやレジュームなどの原理を 簡単に紹介しておく。

毎年恒例の防災訓練が開催されました。 学生さんも全員無事に避難となりました。

構造体の説明の2週目ということで、実際のプログラム作成に近いものを 説明するために、構造体の関数呼び出しについて説明する。

基本となるプログラムは、今まで文字配列と整数配列２つで書いていたものを、 構造体を使って書き換えたもの。

struct Student {
char name[ 20 ] ;
int  kokugo ;
int  sansu ;
} ;
void main() {
struct Student ei[ 50 ] ;
int  size ;
for( size = 0 ;
scanf( "%s%d%d" ,
ei[ size ].name ,
&( ei[ size ].kokugo ) ,
&( ei[ size ].sansu ) ) == 3 ;
size++ )
{   printf( "%s %d %d¥n" ,
ei[ size ].name ,
ei[ size ].kokugo ,
ei[ size ].sansu ) ;
}
}

このプログラムで、ei[] 以外の配列にも入出力が必要であれば、 入力専用関数や出力専用関数があったほうが便利。

int inputStudent( struct Student* p )
{   return scanf( "%s%d%d" ,
(*p).name ,
&( (*p).kokugo ) ,
&( (*p).sansu ) ) == 3 ;
}
void printStudent( struct Student* p )
{   printf( "%s %d %d¥n" ,
(*p).name , (*p).kokugo , (*p).sansu ) ;
// 同じ処理をアロー演算子だと以下のように書ける。
// printf( "%s%d%d¥n" , p->name , p->kokugo , p->sansu ) ;
}
void main() {
struct Student ei[ 50 ] ;
for( size = 0 ;
inputStudent( &( ei[ size ] ) ) ;
size++ )
{
printStudent( &( ei[ size ] ) ) ;
}
}

この様な構造体のデータを取り扱う関数を準備し、 メイン処理では、その関数を呼び出すようにすれば、 メイン処理では、データ構造の中身や、その関数の中身を知らなくても、 入力・出力処理が行われることが予想しやすい。 このため、メイン処理を記述する人と、データ構造の処理を記述する人で、 作業の分担がしやすく、かつ、データ構造の変更があった時に、 メイン処理の変更を殆ど無い状態にできる。

また、最初の説明では、既存のポインタ渡しの延長で説明を行ったが、 "(*p).member"というのは、面倒でありアロー演算子が使えることを説明する。

この後は、授業の範囲外ということで、同じプログラムをオブジェクト指向で 書いてみた例を示し、データ隠蔽・手続き隠蔽といった用語を説明する。

データベースの授業の１回目として、ガイダンスを行う。 授業で取り扱う内容などのシラバスについて説明い授業開始。

最近のWebシステムでの3段スキーマ・アーキテクチャなどを交えながら、 データベースの使われ方などの説明の後、データベースを使わなかったら どういった処理が大変で、データベースが如何に便利かを説明する。

詳細は、例年同じなので、前年度へのリンクを示す。

後期に入ったということで、中間試験までと期末試験までの予定を 簡単に説明した後で、2分木の説明を行う。

2分木

比較として、最初に配列での高速なデータ検索として、 2分探索法について説明し、データ検索が O(log(N))で表せること、 データの追加の処理などは、配列で実装すれば、O(N)となり、 あまり高速ではないことを説明する。

一方、リスト構造は、シーケンシャルアクセスしかできないから、 中央値を取り出すのには、O(N)の時間を要するため、 2分探索法が出来ないことを説明する。

そこで、2分木のデータ例を図示し、目的のデータを探すのに 要する比較回数を検討してもらう。これにより、 2分木のピラミッド構造の段数が、データ検索の際のループ回数である ことを説明し、段数 m と、データ件数 2^m = N より、 O(log(N))などの説明を行う。

structd Tree {
int  data ;
struct Tree *left ;
struct Tree *right ;
} ;
struct Tree* tcons( int x , struct Tree*l , struct Tree*r )
{
struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->data = x ;
n->left = l ;
n->right = r ;
}
return n ;
}
struct Tree* top = // 静的にデータを生成
tcons( 50 ,
tcons( 75 , NULL , NULL ) ,
tcons( 25 , NULL , NULL ) ) ;

例題

2分木データ挿入処理のプログラムは複雑になりそうだし、 いきなりポインタのポインタでは、混乱をすると思われるので、 簡単に検索、データ件数カウントなどの例題を示す。

int  find( struct Tree* p , int key )
{
while( p != NULL ) {
if ( p->data == key )
return 1 ;
else if ( p->data > key )
p = p->left ;
else
p = p->right ;
}
return 0 ;  // 見つからない
}
int count( struct Tree* p )
{   if ( p == NULL )
return 0 ;
else
return 1 + count( p->left ) + count( p->right ) ;
}