情報処理に関する資格試験

JABEE において、情報処理の知識習得を条件とするために、 専攻科生にいずれかの資格の取得か、情報処理の総合試験(技術士試験問題相当)合格 を修了要件としている。 しかし、資格試験の見直しが必要なので、試験内容を追いかけている。 うーむ、細かく『級』が設けられている試験では内容が簡単すぎるものや、 ワープロ操作技能しか要求していない試験も含まれる。

2分木を使った式の表現の説明。

2分木を使わない場合

式といっても、演算子の優先順位や結合方向などの問題がある事を説明した後、 逆ポーランド記法などがあることを説明し、 逆ポーランド記法のなら、値を計算する事はスタックを使えば簡単であることを説明。

2分木を使った式の表現

今までの知識だけで2分木を使って式を表現すると、 木の枝のポインタは『値』の場合と『木』の場合があるので、どうするか？ といった話題から、木を表現するデータ構造の宣言を考えさせる。

struct Exp {
int  type ;         /* 節が数値か演算子か？ */
char op ;           /* 数値の場合 */
int  value ;        /* 値の場合 */
struct Exp* left ;  /* 左右の枝 */
struct Exp* right ;
} ;

このデータ構造の場合の『無駄』をどう対処すべきかを答えてもらう。 授業で提案された方式は、以下の３つであった。
# 案1,案3を組み合わせて、共用体を使ったデータ構造の宣言例を示す。
# あわせてtypeのbit数を減らすために、ビットフィールドを使う場合もあることを紹介

1. op と value は同時に使わないから、 value に演算子コードを保存すれば op は不要！
2. 数値の場合には、op に数値を表すコードを割り当てれば、type は不要！
3. 数値の場合は left , right も NULL なので、type は不要！

最後に、上記データ構造での、式の値を求める eval を説明する。

10/31〜11/2の期間に実施していた 認証評価 の実地審査が無事終了しました。 面談に御協力頂いた学生の皆さん、OBの皆さんご苦労さまでした。

昨日は私の担当の実験も視察コースの１つで、質問などを受けました。 選択実験でテーマ数が多く、シラバスに実験テーマが記載漏れとなっていて、 どうして？と質問されて、多少戸惑いましたが….

審査最後の「審査の各項目の確認結果」では、どの項目も問題がなく無事終了でした。 審査結果は、１月の学校への連絡と返答ののち、３月に『正式な審査結果』が 届くそうです。

２分木の構造にて、

• 名前と生年月日
• 名前と電話番号

のデータにて、入力し２分木を生成し、データ順で表示。 これに加え、以下の処理をできるようにする。

• 同じ名前のデータを探す。
• データを探す時の最悪の検索回数を求める。
• 指定したデータを削除する。

担当実験じゃないけど、昨年に引続き記録だけ。 昨年のコースの周回速度は、15秒。 車体正面の無駄な飾りが….
# でも、最初の完成グループの割に、飾りで遊ぶ余裕があるのか….
プログラム応用の授業で、ビットフィールドの処理の説明が良かったみたい。

勝山の地場産業振興センターにて

構造体の応用として、ワードアライメントの話とビットフィールドの話をする。

構造体のワードアライメント

struct A {
int  x ;
char n[ 5 ] ;
} ;
struct A array[ 100 ] ;
printf( "%d" , sizeof( array ) ) ;

この例が、900byte でなく 1200byte の場合もあるよ…ということで、 最近のコンピュータが、ワード単位でメモリをアクセスすることや、 ワード境界をまたがったメモリアクセスは、速度低下の可能性があることを説明。 メモリをパックして節約もできるという説明の時に『大量のメモリ使用がスワッピングを引き起こし速度低下の可能性がある』ことも説明する。

関連授業：計算機構成論、OS論

構造体のビットフィールド

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

の構造体が、12byte メモリを消費することを説明し、メモリ節約のために int 型で表現したら、どうなるかを説明する。

/* int型で年月日を保存 */
/* 0000,0000,0000,YYYY,YYYY,YYYM,MMMD,DDDD */
int bday = (2005 ≪ 9) + (10 ≪ 5) + 28 ; /* 2005年10月28日 */
/* int型の年月日より抽出 */
int y = bday ≫ 9 ;           /* bitマスクをbit幅から作る  */
int m = (bday ≫ 5) & 0xF ;   /* (bday ≫ 5) & ((1U≪4)-1) */
int d = bday & 0x1F ;         /* bday & ((1U≪5)-1)        */
/* int型の年月日の月を2月に変更 ;
bday = (bday & 0xFFE1F) | (2 ≪ 5) ;
/* bday & ~(((1U≪4)-1) ≪ 5) | (2 ≪ 5) */

でも、説明していても、『年は何bitで表現できる？』の回答ができない学生もいる….

この面倒臭い式を説明した後、ビットフィールドの説明で閉める。

struct YMD {
unsigned int  year  : 11 ;
unsigned int  month :  4 ;
unsigned int  day   :  5 ;
} ;
struct YMD bday ;
/* 構造体への代入 */
bday.year = 2005 ; bday.month = 10 ; bday.day = 28 ;
/* 構造体の一部を修正 */
bday.month = 2 ;

先週までのコンピュータの歴史で、最後の『プログラム言語の歴史』は 詳しく話さず、今回の言語プロセッサの話題に切替える。

コンピュータの中でのプログラムの実行のネタとして、 機械語,アセンブラ、 RAM,ROM とは、 コンピュータの電源ONからブートローダ・BIOS・OS起動などの 説明をおこなう。 そのあと、コンパイラ方式，インタプリタ方式の説明を行う。 速度面での利点欠点、プログラム配布面での利点欠点を解説する。 特殊な事例として、バイトコードインタプリタやらエミュレータなども説明する。 このネタの中で、Java がネットワークの安全性やCPU非依存性で有利な点を 紹介する。

中央前列の２名さまは、すごく興味深げに話しを聞いてくれて、気持が良い。 やる気がでるね。その反動で、話の速度が上がりがちかも….