授業を前にひとまず、話のネタを整理しながらメモ。 授業が終わったら、加筆しまーす。 んで、今日はハッシュ法について説明を行う。 テスト前が今日を含め2回なので、説明は終わるだろう。 後期中間試験後は、参照カウンタなどのネタから説明の予定。

ハッシュ法

リスト構造や2分木などを今までの授業で解説してきたが、 O(N)やO(log N)の検索時間がかかる処理。 さらなる高速化にはハッシュ法が取られる。

電話番号でデータベースを作る場合、電話番号自身を配列の添字にすれば、 検索時も添字でアクセスするだけで、検索時間も一定でありO(1)にできる。

// 電話番号XX-XXXXの6桁で名前を検索
char name[ 1000000 ][ 20 ] ;
strcpy( 272925 , "t-saitoh" ) ;

しかしながら、この方法では大量のメモリ空間が必要となる。 ハッシュ法では、データの一部を配列の添字とする方式。 データの保存場所はハッシュ値、ハッシュ値を取り出す関数をハッシュ関数と呼ぶ。 データの一部を取り出すことから、異なるデータなのに同じハッシュ値となる場合がある。 これをハッシュ衝突と呼ぶ。

実際には、ハッシュ衝突の対策が問題となる。 例として、電話番号が使われているのかチェックする処理を考える。

#define SIZE 100
int  table[ SIZE ] ; // ハッシュ表には電話番号を保存
int hash_func( int tel ) { return tel % SIZE ; }
int idx = hash_func( 272925 ) ;
table[ idx ] = 272925 ;

上記のような処理でデータを扱う場合、ハッシュ衝突対策の例は以下のようになる。

void entry( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] != 0 ) {  // 先着データがあれば+1に保存
idx = ( idx + 1 ) % SIZE ;
}
table[ idx ] = tel ;
}
int search( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] == 0 ) {
if ( table[ idx ] == tel )  // 見つかった
return tel ;
idx = ( idx + 1 ) % SIZE ;
}
return 0 ; // 見つからない
}

ただし上記のプログラムでは、ハッシュ表がすべて埋まったら無限ループになってしまうので、その対処を追加する必要がある。

最初に、SQLで説明のしてなかった、CREATE VIEW を補足説明し、 後半はデータベースの設計の話をする。 悪い設計の例ということで、学校で使っている緊急連絡システムや授業アンケートを 例にとりながら、手抜きでOKな部分と不整合などの問題点を、 設計の腕の見せ所…という点で説明を行う。

SQLの補足

CREATE VIEW 命令は、アプリケーションプログラマーが データベースを扱いやすいように、 SELECT命令で取り出されたテーブルを、あたかもそういうテーブルが あるように見せかける機能。 これにより、外部スキーマとして分かりやすくプログラムが書ける。

CREATE VIEW 名前( 要素 ... )
AS
SELECT 要素 FROM テーブル WHERE ... ;

教科書では、ホスト言語での取り扱いが記載されていたが、 授業ではホスト言語と連携する際のプログラムの問題として、 SQLインジェクションの危険性を示した。

データベースの設計

データベースの設計の話として、学生が授業を受講する際のデータベースを例にしながら、 悪い設計と、不整合の問題を説明する。 これらの不整合を解決するには、データベースの設計が重要であり、一般的には ER図などを書きながら設計を行う。

ER図の１つは実体(Entity)であり、図に示す際は四角枠に名前を記載。 これに属性を丸枠で囲んで、線で結ぶ。丸枠内の属性名は、主キーであれば 下線をつけて記載する。 関連(Relationship)は、複数の実体間の相互関係を表すもので、 菱形の四角で示す。

改めて、ネットでER図を探すと、属性をUMLのクラス図と同様に書く方が主流になってきているみたい。

前回の割り込みの説明の補足として、 システムコールについて説明する。

システムコールなど

OSでは、資源保護のために、CPUの特権モードなどを活用する。 周辺装置やCPU内の重要な情報の制御は、特権モードでしか使えない。 ユーザモードでは、入出力機器の制御などの命令は「不当命令エラー」で実行できない。

ユーザが入出力命令を使うためには、システムコールが利用される。 これはソフトウェア割り込み機能を用いて実現される。 システムコールが実行されると、特権モードに移行し実際の周辺機器の制御の前に、 不当な資源アクセスをしていないか、チェックが行われる。 ユーザがシステムコールを経由せずに、入出力命令を実行すれば、 不当命令エラーとなるため、不正に資源を操作することができなくなる。

メモリ管理の説明として、上限・下限レジスタによる許可範囲外のメモリアクセスを 止める機能を解説する。 また、メモリ管理機能として、メモリ階層構造の話をする。 メモリは、CPUレジスタ・キャッシュ・DRAMによる主記憶・HDDによる補助記憶の４段階に分けられ、高速＆高価＆小容量なメモリから、低速＆安価＆大容量なメモリに分類できる。 これらのメモリでは、利用頻度の高いデータを、高速メモリ側にコピーしながら使うことで、 高速＆大容量のメモリがあるかのように使える。

ネットワークの導入説明

ネットワークの利用目的の説明として、プリンタ共有・ファイル共有・リモート接続での計算能力の共有などの「共有」の視点と、処理能力不足を補うための負荷分散、コンピュータ故障対策としてのリスク分散などの「分散」の視点を説明する。

ネットワークの物理層の説明として、様々なインタフェースの例を示す。 パラレル接続では、単位時間あたりの通信量を増やすために、複数の信号線を使う。 しかし、ケーブル本数が増え全体の太さから取り扱いが難しい。 シリアル接続では、本数が少ないためケーブルの取り扱いが容易で、長距離配線などで よく利用される。 通信速度の高速化をするためには、マイクロインダクタンスや線間容量などの影響で、 信号波形の劣化が問題となる。これらの対策としてインピーダンスマッチングなどが重要で、 SCSIなどでは、末端抵抗(ターミネータ)が重要となる。

最近のシリアル通信では、信号劣化対策を少ない信号線に施すことで、パラレル方式より高速化された方式が増えてきた。

プログラミング応用の後半で、グラフィックスのネタをするため、まずはグラフィックスの 構造について説明を行う。

最初に、CRT(陰極管方式)の説明として、電子銃から出た電子が、表示面の蛍光体を 光らせる構造を説明する。 これらを利用した表示方法に、ベクタスキャン方式（一筆書きの要領でXY座標情報で制御）と ラスタスキャン方式（走査線方式）を説明する。 ラスタスキャンでは、電子のぶつかる場所を、左右に移動させながら水平線を描き、 その水平線の場所を上下に移動させながら全体を描く説明を行う。

ラスタスキャンのCRTをカラー化する場合の構造を説明し、利点・欠点をまとめる。 利点は、色の再現性や残像が無い点だけど、欠点として、 表示面が平面にしづらい・四隅に色にじみが発生しやすい・巨大化できない、奥行きサイズを 薄くできないなど。

これらの改善として、液晶ディスプレイがある。液晶は電圧により偏光方向を制御ができる。 この液晶を、透明電極の間にはさみ、光源からの振動方向のまざった光から、一方向に 偏光した光をとりだす。これを偏光板を通して明るい点・暗い点を表示する。 利点として薄い構造のディスプレイを作れるが、欠点として斜め方向からの視野で 見づらい点や、色再現性が低い、残像が残るなどの問題点を紹介。

有機ELは、おおざっぱに言えば、発光ダイオードを面上に並べたような構造。 発光体が並ぶことから、液晶のようなバックライトが不要で薄型化ができることや、 斜め方向から見ても問題がないことを紹介する。

プラズマディスプレィは、高圧をかけたプラズマで発光するものを面上にならべた構造。 巨大ディスプレイに向いている。

後半では、ディスプレイなどでの色の扱いや、情報量について説明。

色は、光の三原色(赤,緑,青)の配合ですべての色を表現する(加色系)。 逆に、絵の具の三原色は、シアン・マゼンダ・黄色で色を表現する方法。 ただし黒をきれいに印刷するために、黒のインクの4色が一般的。(減色系)

R,G,Bは、一般的に各色が0～255の8bit、256諧調で１画素を表現することから、 絵の情報量を解説。情報そのままでは、メモリを浪費してしまうため、圧縮などの 必要性を説明し、JPEGなどを紹介する。

• 11/16 Kinectで動くロボット、卒研でやりたいネタだよね。"Maker FaireにMicrosoftが出展したKinectロボットほか" http://tinyurl.com/bnxx42o #fnct

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

今日は、知的財産教育の講演会が開催されました。

「自転車型ロボット"ムラタセイサク君"の開発と知的財産」
　　　　"知的財産はどのようにして生み出されたのか"
村田製作所　広報部企業広報課　係長
自転車型ロボット「ムラタセイサク君(R)」開発者　
吉川　浩一　氏

高専では、Microsoftの包括協定にて、OSやOfficeのインストールにて、 適正なライセンス手続きを経れば、無償でOS,Officeをインストールできるようになった。

んで、今回Office2010を卒研用のPCに入れようとしたけど、かなり苦戦。

学内のサーバより、教員のメールID、パスワードを入力すれば、インストール用の データをダウンロードできる。これを使ってインストールを開始すると、 改めてメールID,パスワード,パソコンの管理台帳の番号を入力すれば、 利用ができる。

でもOfficeをインストールをすると、どうしても失敗する。 OSが、「Windows 7/Vista/XPじゃない」って文句を言ってくるけど、 購入時にWindows 7 Home Edition 64bit が入ってるじゃん。 よくよくインストールの手順書を見ると、7/Professional/Enterpriseじゃないとダメ らしい。 じゃあということで、Windows 7 の Anytime Update で、アップグレード をしようとするが、なぜか失敗。 OSの方も、包括協定でのアップグレードが必要みたい。 しかし、ライセンスを設定するプログラムは、サーバからダウンロードできるけど、 アップグレードには今度は学校指定のメディアが必要とな。
# 面倒だなぁ…イライラ。

2分木の応用として、式の表現の説明を行う。

まず、式の表現にあたって、演算子の優先順位の話として、 "1+2+3"が、"((1+2)+3)"として扱われる左結合で、 "x=y=z=0"は、"x=(y=(z=0))"で扱われる右結合といった話を説明する。 これらの優先順位情報は、分かり難いのでプログラムと処理しやすいように扱う必要がある。 "2+3*4"といった式は、前置記法では"+,2,*,3,4"と表現される。 一方、後置記法(逆ポーランド記法)では、"2,3,4,*,+"となる。 特に逆ポーランド記法は、計算の機械語生成に結びつくので、よく利用される。

でも、2項演算子は2分木として表現できるため、以下のようなプログラムで 式を扱うこともできる。

struct Exp {
int type ;
int data ;
struct Exp* left ;
struct Exp* right ;
} ;
struct Exp* Integer( int x ) {
struct Exp* n ;
n = (struct Exp*)malloc( sizeof( struct Exp ) ) ;
if ( n != NULL ) {
n->type = 0 ;
n->data = x ;
n->left = n->right = NULL ;
}
return n ;
}
struct Exp* Operator( int op , struct Exp*l , struct Exp*r ) {
struct Exp* n ;
n = (struct Exp*)malloc( sizeof( struct Exp ) ) ;
if ( n != NULL ) {
n->type = 1 ;
n->data = op ;
n->left = l ;
n->right = r ;
}
return n ;
}
int eval( struct Exp* x ) {
if ( x->type == 0 ) {
return x->data ;
} else {
int l = eval( x->left ) ;
int r = eval( x->right ) ;
switch( x->data ) {
case '+' : return l + r ;
case '*' : return l * r ;
}
}
}
void main() {
struct Exp* x =
Operator( '+' , Integer( 2 ) ,
Operator( '*' , Integer( 3 ) ,
Integer( 4 ) ) ) ;
printf( "%d" , eval( x ) ) ;
}

次に、演算子といっても単項演算子、2項演算子、3項演算子などがあり、 これらのデータを表現することを考えると、2分木は3分木といった拡張の イメージもでてくるであろう。これをもっと一般的にすれば、n分木も 考えられる。これをデータベース用にしたものはB木となる。 この方式は、n件のデータと(n+1)件のポインタで実装される。 詳しくは、B木にて。

この話のおまけとして、データベースシステムについて簡単に話す。 特に、データベースが使われるような巨大なシステムになると、 3段スキーマ構成といった事例や、SQLによるアクセスといった、 一般的な話の導入について紹介する。

# 前回の授業から間が長かったのもあり、内容忘れ気味。
前回の授業で説明が抜けていた、集約関数(count,sum,avg,max,min)、 集合演算子(union,except,intersection)、ソート(order by)、グループ化(group by … having…)をひと通り説明する。

第１週に渡した演習の環境の説明資料を元に、 https://www.ei.fukui-nct.ac.jp/~t-saitoh/edu/DB/exp/の使い方を説明する。

演習テーマは、何らかの意味のある２つのSQL命令を実行し、 その動作結果を確認、さらにその命令と同じような処理をするC言語のプログラムを 作成し、データベース命令の意味やその便利さを確認する。 レポートには、動作結果とその内容の説明や分かったことを記載すること。

• 演習の環境の説明資料
• SQL演習環境
• C言語で書いたSQL命令の例