電子情報工学科

GrWinを使ったグラフィックスの理解の第2ステップとして、座標の平行移動・拡大縮小・回転 について解説を行う。

// 平行移動       // 授業では行列表記も説明したけど、
X = x + x0 ;     // blogでmimetexを使って行列はつらい...
Y = y + y0 ;
// 拡大縮小
X = k * x ;
Y = k * y ;
// 回転
X = x cosθ - y sinθ ;
Y = x sinθ + y cosθ ;

これに加えて、これらの変換を１つの行列で表現するアフィン変換の式も示しておいた。

[ X ]   [ a11 a12 a13 ]   [ x ]
[ Y ] = [ a21 a22 a23 ] × [ y ]
[ 1 ]   [ a31 a32 a33 ]   [ 1 ]

また、このプログラムを書くにあたり、座標を構造体struct XY{ float x,y ; } で扱う場合や、 サイズ2の配列で扱う方法について説明し、変換用関数を作る際に、関数配列渡しや 構造体ポインタ渡しなどの違いを解説する。

グラフィックス2次元演習課題

ここまでの2次元の移動・拡大・回転をしていることが解るプログラムを作成し、 レポートとして作成する。授業後半で3次元グラフィックスの課題を出すことから、 レポートでは、プログラムリストと実行結果と簡単な説明でいい。

表示するための図は、関数グラフでもいいし、座標列を定数で与えた図形でも良い。

ゲーム好きが、ムダにゲーム業界就職に興味をもたれても困るので、 Blogで取り上げるのは好きではないが、面白いやり方が色々書いてあるので…

ゲーム開発のセガにて、社員教育の方法が取り上げられている。 面白いのは、厳しい採用試験に通っているとはいえ、デザイナー・クリエータ・プログラマと分業が進み、得意分野を持っているからこそ、知識のレベルはバラバラみたい。

面白いのは、英語教育にも力を入れている点。

『さらに英語の重要性も新入社員に伝えているという。康氏は、ネット上の価値ある情報の多くが英語で書かれていることを挙げつつ、それを読み解き使いこなすためには、学校教育で得られる英語力だけでは不十分だとする。特にプログラマーは問題の自己解決能力が重要であり、最先端の開発に取り組むほど、英語力の有り無しの影響は大きい。』

また、自由な服装が当たり前とも思われる業界だけど、研修中はスーツ・ネクタイが義務だとは。

さらに面白いのは、職場での相互モニタをつかったペア作業だ。 プログラミングでは、ペアプログラミングというのが有名だけど、これのデザイナ版かもしれない。 ペア作業の2人でペア相手の画面がセカンダリモニターで見れるらしい。 常にペア相手の作業風景が見れる常態で窮屈にも見えるけど、 『自分なりのやり方』だけでは、レベルアップが難しいというのが理由。

学生さんより、授業演習レポートをメールで送ったとの連絡の中、 何人かが「送ったのに…」とのお話し。 どれも、yahooアカウントから。以前はyahooからのしつこいspamがあり、 .procmailrc のレシピにて、下記のような設定。 学内spamフィルタで、レーティングされた値を元に、消すようにしているんだけど、 条件が厳しいのかなぁ….

:0
* ^From:.*@yahoo.co.jp
* ^X-NAI-Spam-Level: \*\*\*\*\*\*\*\*
/dev/null

ひとまず、学生さんは印刷し提出してもらったけど、 トラブル抑制でこのレシピをコメントアウト。
# フリーメール使うにしても、GMail とかの方がお勧めだど。

自宅ページでは、MovableType-OpenSource(MTOS) のバージョンが 4.32-en で、 コメントなどの認証で OpenIDやGoogle,Yahooの認証が使えるようになったので、 学科のMovableTypeも4.23-enよりバージョンアップを行う。 現在、学科サーバはDebian/stableにて運用しているため、testing混在となったが、 思ったより少なめのパッケージで済んだ…

今年度は校舎の改修と新型インフルエンザで、学校行事は特例ばかり。 しかし、ようやく本館の改修もひと段落で、電子情報棟の実験室を仮設教室にしていた 教室を、本来の教室に戻すお引越しの日。

担任の教室も本館に移動だけど、移動先も他クラスが今日いっぱい使うし、 出て行く教室にも、他実験室に移動していたクラスが戻ってくる。 ということで、原則教室内のものは、すべて持ち帰り。 HRで持ち帰りと伝えていた割りに、机やロッカーに大量に「教科書」などを蓄えている人も多い。 んで、「今日全部持ち帰りはムリ！」という学生さんがチラホラ。 さて、放課後の移動はスムーズに終わるかな….

昨夜より福井県の平野部でも、シーズン最初の本格的な雪。 我が家では車の上に、3cm ほどの積雪であった。 学校につくと、早々に学生さんより「雪で電車が遅れてます」との連絡多数。 1限目の授業にも影響が出た様子。 シーズン最初の雪だし、しかたがないか….

処理速度と関係して説明するアルゴリズムの最後？として、ハッシュ法を解説する。 例年どおりの『電話番号から名前を検索する』という例をもとに、 ハッシュ関数に電話番号末尾２桁をアドレスとする方法を説明する。 また、ハッシュ表サイズ100件に、40件を入れる場合ということで、 電話番号末尾2桁ではハッシュ衝突が発生する場合もあり、 その対応方法を説明。

ハッシュ関数の選び方としては、簡単に計算でき、異なるデータに対するハッシュ値の出現頻度が均一(一見デタラメな値)を選ぶことを説明する。 簡単な計算で、データの保存場所が一発で計算できることから、 一定時間でデータを参照できる。処理時間のオーダは、O(1)となることを説明する。

クローズドアドレス法

ハッシュ衝突が発生した場合の対応として、 「椅子取りゲームで椅子が先にとられている時に、１つ後ろの席に座る」 という対応を概念として説明し、簡単なコードを示す。 衝突してたら、空きが見つかるまで+1を繰り返し、途中でハッシュ表サイズに 達したときは先頭から…という方法を示す。

授業ではクローズハッシュと用語を説明したけれど、 正確にはクローズドハッシュ法(closed hash)であった…

チェイン法

クローズドアドレスハッシュ法は、データ件数がハッシュ表サイズに近づけば、 空椅子を何度も探す状態になり、処理時間がO(N)になってしまうし、データ件数が ハッシュ表サイズ(配列サイズ)を超えることができない。

このことから、同じハッシュ値を持つデータを、リスト構造で保存する方法をとる。 この方式は、オープンアドレスハッシュ法とかチェイン法とか呼ばれている。

文字データのハッシュ関数

電話番号から名前を調べる場合は、電話番号末尾は"100の余り"で簡単に計算できた。 しかし、名前から電話番号を検索したいといった場合は、前述の計算ができない。

文字列のデータからハッシュ値を求める場合、数値だけみればランダムに見えれば いいのだから、文字コードの合計といった方法がとられる。

int hash_func( char *str ) {
   int s = 0 ;
   for( int i = 0 ; str[i] != '¥0' ; i++ )
      s += str[i] ;
   return s % HASH_SIZE ;
}

文字列の順序違いで同じハッシュ値が求まるのが問題であれば、合計の計算部分を、 以下のようにする場合も多い。

s = ( s * (小さい素数) + str[ i ] ) % (大きい素数) ;

授業の進度を確認すると、説明が薄いのか予定より早く進んでいるし、後期レポート課題の 説明の後、トランザクション処理について解説する。

後期レポート課題

前期のレポート課題に引き続き、後期のレポート課題を以下のように説明した。

卒研のテーマや身の回りのデータをテーマに、データベースを設計せよ。 ただし、レポート作成に当たり、以下の点を行うこと。

• 2つ以上のテーブルから構成されるデータベースであること。
• ER図を描くこと
• 業務仕様書を作成し、実体・関係を適切に選んでER図を描く。(トップダウン設計)
• 第一正規形、第二正規形、第三正規形を満たすことが分かるような説明をすること。 (ボトムアップ設計)
• そのデータベースをWebの実験環境にデータ数は少しでいいので実際に入力し、SQLの命令を実行すること。
• そのSQLは、実際の業務のどういう場面で実行し、その結果をどう使うことになるかを説明すること。

課題にあたり、SQLで"CREATE TABLE"などの説明が不十分であったため、SQLite,Oracle のデータ型の宣言や特徴を解説を行う。Webのデータベース実験環境は、SQLite なので、 型対応が柔軟なので、もっと簡単な説明でよかったのかもしれない。

トランザクション処理

改めて、Atomicity/Consistency/Isolation/Durability (ACID特性)を説明した後、直列化可能性の 説明を行う。同時実行制御には、ロッキング方式と、時刻印方式(タイムスタンプ方式)がある。 ロッキング方式で、ロックされていると解除まで待たされる。ロックの粒度が大きいと、 広範囲にロックされて、待ち時間が増えてしまう。

ロック方式には、共有ロック(Shared Lock / Read Lock)と、専有ロック(exclusive Lock/Write Lock)があり、共有ロックは重複してロックができる。これにより、ロックで待たされる時間を軽減できるようになる。しかしながら、直列化可能スケジュールでないと、この方式でも更新異常となる。

この対応として、2相ロッキング方式があり、ロックをかける操作の成長相と、ロック解除の縮退相に分離する。ロック解除がはじまったらすべてのロックがはずれるまで待つ。

こういったロックによる排他制御を行う場合、自分がかけたロックの影響によって、自分の処理がロック解除待ちにならず、処理が停止してしまうことがある。これをデッドロックといい、避けることができない。データとトランザクションの間のロック関係を、資源グラフで管理し、資源グラフに周回が発生したら、デッドロック発生とみなす。デッドロックの防止のために、(a)ロックの一括獲得の方法や、(b)使用データに順序付けを行う方法や、(c)トランザクションに優先順序を与える方式などがある。