先週は2分木の概念の理解と検索処理の話をしたので、 今日は実際に木の全要素に対する処理などを再帰を交えて説明を行った。

2分木の前に、簡単な再帰に慣れてもらうために、 単純リストでのループを使った処理を再帰で記述する練習。 以下のようなcount()を示した後、単純リストの全データ表示と、全データ合計を書いてもらう。 この際に、再起でプログラムを書くコツとして、「処理できない問題は小さく分けて考える」 という定番の説明をおこなう。

// ひとまず再帰に慣れるために線形リストで...
int count( struct List* p )
{
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ;
}

この後、実際に2分木のデータ処理として、リストに対する全データ表示を記述してもらう。 あらかじめ単純リストの説明の後だったので、意外とすんなり理解してくれた様子。 この説明のあと、全データ件数count(struct Tree*)や、全データ合計sum( struct Tree* )や、 ループで記述可能であるけれどあえて、find( struct Tree* p , int key ) なども考えてもらう。

// 2分木で全データを昇順に表示
void print( struct Tree* p )
{
if ( p != NULL ) {
print( p->left ) ;
printf( "%d" , p->data ) ;
print( p->right ) ;
}
}

この話の関連として、print() は、深さ優先探索であり、記述は手間だけど別な探索では、 幅優先探索といった用語を紹介する。 また、2分木のcount(),sum(),print()などは、通常再帰でなければ記述できない処理であり、 find()はループでも記述可能で、この違いは末尾再帰呼び出しになっているかの 違いであることを紹介する。

ガイダンスに続き、データベースの基礎的な総括を行う。

データベースでは、エンドユーザは、WebやGUIアプリなどを経由してデータにアクセスするが、 そのWeb,GUIアプリは、応用プログラマが作成し、実際のデータベースには、SQLを経由して アクセスが行われる。実際のデータベースは、データベース管理者が定義・生成・２次記憶割り付け・再編成などの細かなチューニングを行う。

データベースシステムの実例

データベースシステムの実例ということで、Oracle などの製品名に加え、 Webとの一貫したシステム構築では、LAMP(Linux+Apache+MySQL+PHP)構成といった 用語なども紹介する。

応用プログラマにしてみれば、SQLを経由することで、データをプログラムから分離ができ、 実際の内部の構造を知ることなく独立性が得られる。また、データの一貫性を保つことは、 データベースを利用しないと大変であるが、データベースでは(a)正当性確認,(b)同時実行制御,(c)障害回復などを行ってくれるので、一貫性のあるデータ管理が容易となる。

プライバシーの保護などの話の一環として、最近のシステムでデータベースを利用する場合、 大きな問題となるSQLインジェクションといった手法の存在なども紹介する。

データベースに対する視点

データベースに対する視点として、エンドユーザからの要求を応用プログラマが処理する場合、 データベースの一部分だけであったり、複数のデータベースを大きな単独の表で扱えると便利であったりする。こういう応用プログラマの視点を外部スキーマと呼ぶ。 しかし実際には、複数の表からなるデータベースでは更新なども容易な(正規化された) 表であるほうが良い。このような視点は、概念スキーマと呼ばれる。 さらにデータベースの内部では、このデータを高速に処理するためのインデックスが付加されたり、実際のファイル上に記録されるデータ形式がとられる。これらは内部スキーマと呼ばれる。この利用者の視点に応じたスキーマ構成を、３層スキーマ・アーキテクチャと呼ぶ。

データモデル

データベースでは、階層的なデータ構造は木構造で表現できる。 (ファイルに記録する際では、XMLなどの表現をとったりする。) しかし、階層の深い物の取り扱いは不便となる。現実のデータでは、これらが複雑に絡み合う ことが多く、ネットワークモデルなどと呼ばれる。 これらのモデルは汎用性が高いものの、検索や取り扱いが複雑となるため、 関係モデル(Relational model)が広く使われている。

情報処理技術者試験受験者から質問

情報処理技術者試験を受ける学生さんが、質問にくる。 「第３正規形って何？」例年の質問ネタである。 でもなかなかうまい説明ができない。 こんなんが、データベース教えていていいのかな…

ということで、解りやすく説明しているページを探してみた。

• 第2正規形は、部分関数従属性を取り除く。 「キーから非キー」への関数従属性を整理する。 A→Bを取り除く。
• 第3正規形は、第2正規形から推移関数従属性を取り除くこと。 「非キーから非キー」への関数従属性を整理する。 A→B→Cを取り除く。(A→Bは第2正規形で取り除かれているはず)

専攻科1年対象-後期の計算機システムの初めての授業。 選択で、生産・環境あわせて15名ほどの人数だった。 ガイダンスとして、授業の内容や試験・レポートの実施方法を解説する。 前半の私の担当では、コンピュータシステムで重要となる、 OSの話とネットワークの話…

コンピュータの歴史

コンピュータの歴史ということで、 ネピアの計算尺やパスカルの歯車計算機で計算するという概念の始まり、 ジャカールやバベッジによるパンチカードで仕事の順番を記述するという概念の始まり、 ブール代数やチューリングによる2進数と処理でコンピュータの理論の始まり といったあたりを簡単に紹介する。

次に、第1世代(真空管)、第2世代(半導体)、第3世代(IC)、第3.5世代(LSI)といった、 コンピュータの発達の歴史に沿って、プログラム言語やOSが出てきたあたりを説明する。 第4世代以降は、パソコンの世界の発達を中心に説明する。

4ビットコンピュータi4004,8ビットコンピュータi8080で、 インテル社がパソコン用CPUを売り出す話から、 モートローラの6800系の市場競争の始まりを説明し、16bitコンピュータが開発される際に、 i8080→i8086における命令互換性の配慮が成功の一因であったことを説明する。 また、IBM社のPC/ATにおける情報公開が、3rdパーティによる互換機発売＆価格競争で 低価格化＆普及となった成功について説明する。 この時代では、TinyBASICとMS-DOSでのビルゲイツの登場とマイクロソフト社が、 ソフトウェア中心の時代に変化させている。 これらの裏で、Apple社は、MacintoshでGUIの導入から、優れた操作性による成功を 収めつつ、ハードウェア情報非公開が高価格化＆衰退の原因となったことを紹介する。

次の授業では、シラバス配布せねば…
32bit化と保護機能の実装とOSのセキュリティの関係を解説の予定。

実験用に学科で導入。なんとなく、すげー

歯みがきロボコンを前にして、学生さんの画像処理型ロボットが少しづつ 動くようになってきました。 ブラシの部分は、学生さんが「キャタピラの部品がほしい」との話でしたが、 近所に売っている所もなかったので、私の方で歯の曲がり具合に応じて 円弧っぽく動くようなものを作ってみました。

画像処理型といっても、処理速度やアルゴリズムの都合で、画面上の数点の 明るさしか取得していないんですけどね…

プログラミング応用での後半では、構造体などの複合型とグラフィックスを説明する予定。 特に中間試験までは、構造体・共用体・列挙型といったプログラムのデータ構造の 記述のバリエーションが広がることを目標にする。

構造体の説明といっても、2年生でも一応習っている内容でもあり、 関連する情報なども交えながら解説を行う。 構造体は、COBOL(Common Business Oriented Language:商用向け言語)での、 複合データを記述する考え方から出ている。 同じように、プログラミング言語では、手続きの構造化などの発展と共に、 構造化プログラミング(Structured Programming)に発展する。 データの構造化・処理の構造化は、データに対する処理の記述から、 オブジェクト指向へと発展していく。

構造体が無かったら、プログラムが発展していくときに、面倒が増えるのかといった話題を 説明したあと、実際の文法の説明を行う。 この中で、タグ名(Person) , 要素名(name,kokugo…) といった用語を解説。

struct Person {
char  name[ 20 ] ;
int   kokugo ;
int   sansu ;
int   rika ;
} ;
struct Person saitoh ;
strcpy( saitoh.name , "Saitoh" ) ;
saitoh.kokugo = 59 ;

途中で、タグ名などで変数名と同じルールといっても通じなかったので、 変数名が [A-Za-z_][A-Za-z0-9_]* (正規表現でかくと)といったものが使用可能 であることを説明する。

複合の型の雰囲気を感じてもらうために、構造体の初期化、構造体の入れ子(nesting)、 同一構造体の一括代入などの説明を行う。

構造体の一括代入などは、ANSI-Cなどでの機能であり、K&Rだとダメ…とかいった、 話題をしたので、ちょっと脱線して、JIS規格とかK&R文法などを紹介する。

前期最後の双方向リストの次ということで、２分木の説明を行う。

最初に２分探索法について説明をして、検索処理速度のオーダーが、 で示されることを復習する。 その後、この方法が配列でランダムアクセスが可能で、a[(l+r)/2] が取り出せる からこそ有効であることを説明する。

これを踏まえ、２分木のイメージ図を示した後、ノード(節)とパス(枝)といった用語を説明し、 構造体の宣言を示してから、この概念を説明する。 ひとまず、処理の理解ということで、データ生成と検索処理までを示す。

struct Tree {
   int data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tcons( int x , struct Tree*l , struct Tree*r ) {
   struct Tree* ans ;
   ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( ans != NULL ) {
      ans->data  = x ;
      ans->left  = l ;
      ans->right = r ;
   }
   return ans ;
}
// データは、0..100の値と仮定し、見つからなかったら負
int find( struct Tree* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
void main() {
   struct Tree* top =
      tcons( 50 , tcons( 24 , NULL , NULL ) ,
                  tcons( 76 , NULL , NULL ) ) ;
   printf( "%d\n" , find( top , 20 ) ) ;
}

この２分木構造では、木の段数がM段あって、木が左右均一であれば、 全データ件数は、 の関係から、を満たし、処理時間は、 で示される。

ヒープ

2分木の欠点を考えると、データ１件につき、左右のポインタが必要であることから、 32bit コンピュータであれば、sizeof( struct Tree ) は12byte となり、単純な配列1件=4byte と比べればメモリのムダとなる。

この欠点の改善方法として、ヒープと呼ばれる方法がある。

この方法であれば、N番目のデータの左枝は2*N+1、右枝は2*N+2の位置に存在するため、 ポインタが不要となる。

授業を少し早目に終えて、昨日のホームルームの続きということで、 遠足の場所決め。最終的には、ふくい健康の森でバーベキューということになった。 ルートを確認すると、神明駅からの7Kmが徒歩で一番近いみたい。

大きな地図で見る

今日は、後期の最初の授業ということで、授業前に短いホームルーム時間がとられていた。 まずは、インターンシップ後の提出物や、高専祭の週の保護者面談の希望日程調査の 提出物を回収。4EIは後期実験のガイダンスとなった。

実験ガイダンスが予定より早く終わったので、残りの時間でホームルームの続きを行った。 この際、クラス役員の選挙と、11月の3年工場見学旅行中に行われる遠足を検討してもらった。 ただこの際に、なかなか行先アイデアが出てこない。1,2,3年の時の経験を踏まえれば、 もう少しアイデアが出てくるかと思ったら、担任クラスは色々と不可避なトラブルで、 クラスでのネタがいろいろとつぶれている。

1年生では、4月の新入生オリエンテーションが能登沖地震で、宿泊研修なし。 1年生の遠足は台風で中止。 昨年の3年では、新型インフルエンザで工場見学旅行が延期＆3月実施。 みごとなまでにクラス・レクリエーション系で、運が無い。

ということで、遠足の行先決めで、発展的意見がでず議論が発散するので、 希望の行先を考えてくるという宿題にて、一旦ホームルームを終了とした。