電子情報工学科

2分木データ構造の応用として、意思決定木と2項演算子による式の表現を説明する。

意思決定木

質問を繰り返した後に、その結果を示すような意思決定木を、 2分木で表現する事例を紹介する。進路決定の時期の4年生というのもあって、 勉強好き？もっと勉強したい？といったようなネタで、例を示す。

プログラム例として、以下のようなものを示す。

char input[ 10 ] ;
struct DTree* p = 何らかの木の生成 ;
// 質問を繰り返す。
while( p->yes != NULL || p->no != NULL ) {
printf( "%s¥n" , p->mes ) ;
scanf( "%s" , input ) ; // 質問への回答を入力
if ( strcmp( input , "yes" ) == 0 )
p = p->yes ;
else
p = p->no ;
}
// 枝の末端であれば、結論を表示する。
printf( "あなたは... %s¥n" , p->mes ) ;

2分木を用いた式の表現

式を表現する手法として、演算子の優先順位を()で表現しないのであれば、 式を逆ポーランド記法に変換しておけば、スタックなどを用いてその処理は容易。 しかしながら、木を用いれば演算式を表現することもできる。 これに合わせて、演算子には単項演算子、2項演算子、3項演算子(?:演算子)が あることを説明する。また、"1+2+3"は"(1+2)+3" , "a=b=c=0" は "a=(b=(c=0))" として扱われ、左結合演算子や右結合演算子の2種類がある。 "1+2"中置記法、"+,1,2"前置記法、"1,2,+"後置記法といった、表現法を説明する。

struct Expr {
int  value ;
char op ; // 演算子は1文字だけを考慮
struct Expr* left ;
struct Expr* right ;
} ;
// 整数値の木の生成関数
struct Expr* Integer( int x ) {
struct Expr* ans=(struct Expr*)malloc(sizeof(struct Expr)) ;
if ( ans != NULL ) {
ans->value = x ;
ans->left = ans->right = NULL ;
}
return ans ;
}
// 演算子の木の生成関数
struct Expr* Operator(char op,struct Expr*l,struct Expr*r) {
struct Expr* ans=(struct Expr*)malloc(sizeof(struct Expr)) ;
if ( ans != NULL ) {
ans->op = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}
void main() {
struct Expr* e   // 2分木の式 1+2*3
= Operator( '+' , Integer( 1 ) ,
Operator('*' , Integer( 2 ) , Integer( 3 ) ) ) ;
// 式の値を評価したい
printf( "%d" , eval( e ) ) ;
}
int eval( struct Expr* p ) {
if ( p->left == NULL && p->right == NULL ) {
return p->value ;  // 枝の末端なら定数値
} else {
switch( p->op ) {  // 再帰呼び出しで右辺左辺を計算
case '+' : return eval(p->left)+eval(p->right) ;
case '*' : return eval(p->left)*eval(p->right) ;
}
}
}

専攻科の実験の第３クール目の担当ということで、 オムニホイール車体の制御をArduino Nano で制御をテーマとした。 ただ、同じプログラムばかりでは面白くないだろうと、 昨年度創造工学演習のものづくり用に購入していた、超音波センサーPINGを 使って、身近なものを追いかける車体を作ってもらおうと考えた。

んで、Arduinoの使い方は、簡単に理解してもらえて、PINGを試すが、動かない。 最小配線にして、低電圧源にして動かすけど、ダメ。 3個買ってあったので、交換試験をするけど3個とも動かない。 5000円ほどしたんだけどなぁ…×3で15,000円。 昨年の創造工学の実験中にすでに壊れていたとしか思えない…
# ちょっと涙目…

構造体の演習も終わり、シメのネタということで、共用体と列挙型の説明を行う。 後半は次のグラフィックスの講義の導入として、ディスプレィの構造について説明する。

共用体と列挙型

共用体の説明として、１つの変数に異なる型のデータを覚える場合の、 メモリのムダ対策として以下の例を示す。

配列[0]=整数の123;
配列[1]=実数の0.234;
配列[2]=文字の"ABCD";

を覚えたいならば、

struct A {
int  num ;
double real ;
char  str[ 8 ] ;
} ;
struct A data[1000] ;
data[0].num = 123 ;
data[1].real = 0.234 ;
strcpy( data[2].str , "ABCD" ) ;

しかしながら、メモリの2/3はムダになる。 共用体を使えば、要素の記憶場所が同じ場所を使うようになる。

union A {
int  num ;
double real ;
char  str[ 8 ] ;
} ;
union A data[ 1000 ] ;

列挙型は、プログラム記述時に、定数に名前をつけるときに使う。 例えば、１週間の曜日に応じた処理をプログラムで書く場合は、

#define SUN 0
#define MON 1
#define TUE 2
:
#define SAT 6
int week ;
for( week = SUN ; week <= SAT ; week++ ) {
if ( week == WED ) {
水曜日の処理 ;
}
}

と書くけど、define文の羅列を記述するのは面倒なので、列挙型を使う。

enum WEEK { SUN , MON , TUE , ... , SAT } ;
enum WEEK  week ;
for( week = SUN ; week <= SAT ; week++ )
if ( week == WED ) {
:
}

追記：上記のプログラムは、"week++"が警告を吐くかもしれない。列挙型の具体的な数値が、連続と言う保障はないから…。警告が不気味なら、weekの宣言は "int week ;"にしておくべき。

グラフィックス・ディスプレィの構造

ディスプレイの構造として、CRT,液晶,プラズマなどの構造を説明する。

CRT(Cathode Ray Tube:陰極管,ブラウン管)は、 高電圧による電子放出された電子が(電子銃)、 偏向ヨークで電子の軌道を曲げ、蛍光板にぶつかって光る という構造にて説明する。(画像はWikipediaより引用)

上記の構造で、画面上の任意の場所を指定した色で発色することができるが、１画面を構成するために、昔はベクタースキャン方式で一筆書きのような絵を表示していた。 TVなどはラスタースキャン方式で、表示位置を左上から１行ごとに点で光らせ、１画面を構成する。

さすがにくだらないネタも細かく記載されているWikipedia、個人的にはベクタースキャン方式のStarWars のゲーム機の記載が懐かしく思う。

液晶モニタは、バックライト、偏向板、透明電極、液晶、カラーフィルタから構成される。 液晶は、電圧により光の偏向方向を制御できる液体。 自然光は、様々な波の方向を持った光の集まりだけど、偏向板を通り抜けると１方向だけの波になる。偏向板と液晶でバックライトの光の量を調整し、カラーフィルタで色をつける。

２つの方式の利点欠点として、CRTは薄型にすることが困難で大型化すれば重量も問題となる、液晶は画像の時間的な追従性が悪く、色の再現性も低いといった点を説明する。 時間追従性の性能の違いとして、『ゲーマーはシューティングの僅かな遅れも問題とするので、 ゲーマー御用達は CRT 』といった説明をすると、こういう時だけ寝ることもなく興味を持って聞いている。毎年ながらだけど…

計算機システムのネットワークの説明ということで、今日は物理層のお話。

パラレルインタフェースとシリアルインタフェースの説明を行い、 速度や配線の容易さという観点で利点や欠点を説明する。 配線でのノイズやインダクタンス・容量成分で波形が鈍ることから、 配線への電気的な配慮からもシリアルが普及し高速でもシリアルが普通になっていることを紹介。 USBやRS-232Cなどを事例で名前を上げる。

LAN

Ethernetの事例として、10BASE/5,/2,/T等の配線方法やターミネータの必要性を話しながら、 10BASE/Tの普及を説明し、HUBの内部構造を簡単に説明する。

WAN

Wide Area Network として、AM/振幅変調、FM/周波数変調、PM/位相変調などを説明したあと、電話線＋モデムによる通信(64Kbps)、デジタル化したISDN(128Kbps)、基地局に近ければ高周波帯域を使った通信のADSLなどを紹介する。 さらに、光ファイバやCATVなどの方式でのWANなどを紹介。

残り講義もあと１つ程になってきたので、2回分の資料を作っていったけど、やっぱり１回分の話の範囲しか進めなかった。来週CSMA/CDと、IPアドレス+ルーティング、TCP再送、DNSとhttp+メールまで、進めるかなぁ…

Yahooの特集記事にて、転身に効きそうな「パソコン・IT」の資格ランキングが、 掲載されている。 どちらかというと、上位に記載されているのは、技術系以外の仕事をしている人が、 IT系もできるという意味で持っていると有利な資格のランキングになっているな…

• 1位：マイクロソフトオフィススペシャリスト(MOS)
• 2位：情報処理技術者試験/ITパスポート試験
• 3位：Excel表計算処理技能認定試験
• 5位：情報処理技術者試験/基本情報技術者試験
• 6位：シスアド技術者能力認定試験
• 7位：情報処理技術者試験/システムアーキテクト試験
• 8位：C言語プログラミング能力認定試験

自宅サーバのMRTGにて、メール流量の時間変化を観察しているが、 実質SPAMメールの流量変化観察と同じ。 んで、週変化グラフを見ていると、夜のゴールデンタイムになると 流量が減っている傾向が見える。 これから考えると、日本国内のBOTに感染しているパソコンが、 アイドリング状態になるのを狙ってSPAMをばら撒いているように思えてくる。 職場のパソコンがBOT感染で、アクティブ状態でSPAMをばら撒くという仮説も考えられるけど、 9-5以外の夜中にもSPAM流量があるしなぁ…

高専プロコンや歯みがきロボコンと、自分の関連するイベントもひとまず終了。 ただ、高専プロコンで課題自由部門の本戦参加ができなかったり、 歯みがきロボコンでもzeroからライントレースを作ったりという、 実践で頼りがいのある学生さんが少ない。

難しいことをああだこうだと指導するよりも、 興味を持って実際にプログラムを書く事が先決だろうと考える。 ゲームを作ってみるのも1つだけど、数値をうまく操る技術がないと、 キャラクターの動きも単調でつまらないはず。 ということで、プログラミングパズルにチャレンジしてもらうのがいいのではないかと考える。問題も極めてシンプルに….

プログラミングパズル

1. x*yの計算をするプログラムを作成せよ。
   ただし、乗算演算子＊や除算演算子／は使わない事。 1000*1000の実行にかかる時間を、他の人のプログラムと比べてみること。
2. 上記のプログラムを、for,while,do-while,goto文を使わずに記述せよ。
3. 99の階乗(99!)を全ての桁を計算せよ。
   ただし、言語付属のBIGNUM系パッケージは使わない事。

99の階乗は、Common Lispであれば、勝手にBIGNUMを使ってくれるので、
→ (defun fact(n)
(if (= n 0) 1 (* n (fact (- n 1)))))
→ (fact 99)
933262154439441526816992388562667004907
159682643816214685929638952175999932299
156089414639761565182862536979208272237
582511852109168640000000000000000000000
でも、BIGNUM相当を自分ですらすら書けて、普通のプログラマー。

構造体の説明の後半として、メモリの使用量と関係深いワード境界とビットフィールドの説明を行う。 最初に、主記憶の不足とプログラムの関係として、仮想メモリとメモリ不足時にハードディスクアクセスが多発し、スピード低下について述べる。

ワード境界

struct A {
   char name[ 3 ] ; // イニシャルと点数の構造体？
   int  point ;
} a[ 4 ] ;
境界無視 境界配置
|NNNP|   |NNNx|    N:name
|PPPN|   |PPPP|    P:point
|NNPP|   |NNNx|
|PPNN|   |PPPP|
|NPPP|   |NNNx|
|PNNN|   |PPPP|
|PPPP|   |NNNx|
|PPPP|

CPUに比べて、主記憶の速度は遅いため、メモリアクセスは必要最小限にしたい。 しかしながらワード境界を無視すると、a[0].point の取得には、2回のメモリアクセスが 発生するため、処理速度が低下する場合がある。 このため、name 3文字の後ろに1byteの空きを設けて、ワード境界をまたがらない様に 構造体の要素を配置するのが一般的。

この話の前に、char=8bit=1byte=0..255(-128..0..127),32bitCPUなら、 int=32bit=4byte=-2^31..0..2^31-1といった復習を簡単に行った。

メモリインタリーブとよばれる方式を使うと、 ワード境界があっても最小限のメモリ参照で済むが、ハードウェアが複雑化する。 情報処理技術者試験を受けるのであれば、インターリーブも理解しておくこと。

ビットフィールド

struct YMD {
   int  year ;
   int  month ;
   int  day ;
} ;

といった構造体では、12byte のメモリを使用するけど、メモリ使用を減らすには、 year=0..2047,month=0..15,day=0..31と考えれば、20bitで十分。 メモリの使用量を減らすために、year , month , day を１つのint型で覚えるには？

ymd = year *10000 + month*100 + day ;
printf( "月=%d" , (ymd % 10000) / 100 ) ;

という方法もあるけど、2進数として年月日を覚えるのであれば、

// YYYYYYYYYYY000000000
// or         MMMM00000
// or             DDDDD
ymd = (year << 9) | (month << 5) | day ;
printf( "年=%d" , ymd >> 9 ) ;
printf( "月=%d" , (ymd >> 5) & 0x0F ) ;
printf( "日=%d" , ymd & 0x1F ) ;

とすれば、int 型で、年月日を必要最小限のbit数で保存できる。 しかしながら、2進数演算は分かりにくいので、以下のようなビットフィールドを使えば簡単。

struct YMD {
   unsigned int  year  : 11 ;
   unsigned int  month :  4 ;
   unsigned int  day   :  5 ;
} ;