数日前にフクイ模型さんで発注をしようとしたけど、 お店に連絡がとれないので Amazon 部品をで発注を試みた。 しかし、タミヤの在庫が無いのか工作系ホビーショップの 商品しか表示されないし、しかも購入数がmax3個とかばっかり。

小分け発注は避けたいし職場でお世話になっているマルツ電波さんに お願いしたら、夏休みの工作宿題で受注が重なり、 納期遅れの可能性アリとの連絡をもらった。

ここまでくると仕方がないし、小分け発注を覚悟して 改めてAmazonで検索。 しかしタミヤさんも、Amazonさんには夏休み宿題に合わせ 大量に納めているのか、今日はAmazonのタミヤ出品で 希望数12個の発注できました。

# 綱渡りだな…

リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。

2進数を用いた集合計算

リストによる集合の前に、もっと簡単な集合処理を考える。 データ件数の上限が少ない場合には、2進数を用いるとC言語のビット演算命令で 和集合、積集合が考えられるので、簡単となる。

以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc の計算を行う例である。

void bit_print( unsigned int x ) {
for( int i = 0 ; i < 32 ; i++ )
if ( (x & (1 << i)) != 0 )
printf( "%d " , i ) ;
printf( "\n" ) ;
}
void main() {
unsigned int ba = (1<<1) | (1<<2) | (1<<3) ; // ba = {1,2,3}
unsigned int bb = (1<<2) | (1<<4) | (1<<6) ; // bb = {2,4,6}
unsigned int bc = (1<<4) | (1<<6) | (1<<9) ; // bc = {4,6,9}
bit_print( ba & bb ) ; // ba ∩ bb
bit_print( bb & bc ) ; // bb ∩ bc
bit_print( ba | bc ) ; // ba ∪ bc
}

このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数がある。 このアルゴリズムでは、各bitを整数に対応付けし、 素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。

unsigned int prime = 0 ;
void filter() {
for( int i = 2 ; i < 32 ; i++ ) {
if ( (prime & (1 << i)) == 0 ) {
for( int j = i + i ; j < 32 ; j += i )
prime |= (1 << j) ;
}
}
for( int i = 2 ; i < 32 ; i++ ) {
if ( (prime & (1 << i)) == 0 )
printf( "%d\n" , i ) ;
}
}

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。 しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)

しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。 また、今までの授業で説明してきた cons() などを使って表現すれば、 簡単なプログラムでリストの処理が記述できる。

// 先週までに説明してきたリスト構造と補助関数
struct List {
int     data ;
struct List* next ;
} ;
struct List* cons( int x , struct List* n ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
void print( struct List* p ) {
for( ; p != NULL ; p = p->next ) {
printf( "%d " , p->data ) ;
}
printf( "\n" ) ;
}
int find( struct List* p , int key ) {
for( ; p != NULL ; p = p->next )
if ( p->data == key )
return 1 ;
return 0 ;
}

例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。

struct List* set_prod( struct List* a , struct List* b ) {
struct List* ans = NULL ;
for( ; a != NULL ; a = a->next ) {
if ( find( b , a->data ) )
ans = cons( a->data , ans ) ;
}
return ans ;
}
void main() {
struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List* b = cons( 2 , cons( 4 , cons( 6 , NULL ) ) ) ;
struct List* c = cons( 4 , cons( 6 , cons( 9 , NULL ) ) ) ;
print( set_prod( a , b ) ) ;
print( set_prod( b , c ) ) ;
}

例題として、和集合、差集合などを考えてみよう。

リストの共有と削除の問題

リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。 リストの全要素を捨てる処理であれば、以下のようになるであろう。

void list_free( struct List* p ) {
while( p != NULL ) {
struct List* d = p ;
p = p->next ;
free( d ) ; // 順序に注意
}
}

一方、前説明の和集合のプログラムを以下のように作った場合、list_freeの処理は問題となる。

struct List* set_union( struct List*a , struct List*b )
{
struct List* ans = b ;
for( ; a != NULL ; a = a->next )
if ( !find( b , a->data ) )
ans = cons( a->data , ans ) ;
return ans ;
}
void main() {
struct List*a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List*b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
struct List*c = set_union( a , b ) ;
// a,b,cを使った処理
// 処理が終わったので、a,b,cを捨てる
list_free( a ) ;
list_free( b ) ;
list_free( c ) ;
// c = { 1 , (bのリスト) }
// (b)の部分は先のlist_free(b)で解放済み
}

UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。

クラス図

クラス図は、構造図の中の基本的な図で、 枠の中に、上段：クラス名、中段：属性(要素)、下段：メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、"-":private、"+":public、"#":protected 可視性に応じて、"+-#"などを記載する。

関連

クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連:単純に関係がある場合、
(b)集約:部品として持つが弱い結びつき。関係先が消滅しても別に存在可能。
(c)コンポジション:部品として持つが強い結びつき。関係先と一緒に消滅。
(d)依存:依存関係にあるだけ
(e)派生:派生・継承した関係
(f)実現: Javaでのinterfaceによる多重継承

上図の例では、乗り物クラスVehicleから自動車がCarが派生し、 自動車は、エンジン(Engine)を部品として持つ。エンジンは車体と一緒に廃棄なら、コンポジションで実装する。
自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約で実装する。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。

is-a 、has-a の関係

前の課題でのFigureクラスで、Color 情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、"is-a"の関係、"has-a"の関係で考えると、部品なのか継承なのか判断しやすい。

たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、"Car is-a Vehicle" といえるので、is-a の関係。 "Car is-a Engine"と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、"Car has-a Engine"といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。

オブジェクト図

クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き、中段の属性の所には具体的な値を書き込んで示す。

その他の構成図

その他の構成図としては、コンポーネント図(物理的な構成要素から、システムの構造を表現する図)、 配置図(ハードウェアとアプリケーションの関係を図示したもの)、パッケージ図(パッケージ同士の関係をグループ化した図) なども用いる。

Figureクラスで図形描画を仮想関数を用いて演習を行ったが、 課題のテーマとした色を用いたクラスを実装する場合には、様々な方法がある。 レポート課題と取り組まれている中とは思うけど、次のテーマの多重継承の導入として総括する。

また、後半は、UMLの基本を説明する。

色付き図形の実装方法

最初の基本となるFigure(FigureColor)が、色情報を持つ方法。 しかしこの方法は、基底クラスから異なるデータ構造として定義することになるため、 全体のプログラムを書き換えることになる。 この場合、すでにFigure,FigureBox…といったクラスでプログラムを 書いている人がいたら、全面的なプログラム修正が必要となるため、 混乱の元になる。

(( FigureColorが色情報を持つ基底クラス ))
class FigureColor {
private:
int color ;
public:
FigureColor( int c )
: color( c ) { }
virtual void draw( int , int ) = 0 ;
} ;
// FigureColorから派生
class FigureColorBox : public FigureColor {
private:
int width , height ;
public:
FigureColorBox( int w , int h , int c ) {
: FigureColor( c ) ,
width( w ) , height( h ) {}
virtual void draw( int , int ) {
}
} ;

授業で説明した、FigureBoxからFigureBoxColorを派生する方法は、 既存のプログラムの延長で機能を追加できる。このため、既存のコードの 有効利用ができるのが利点。 しかし、FigureBox以外に、FigureCircle,FigureStar,FigureTriangle….といった 様々な派生がすでに存在する時は、色に関するコードが後付なので、 色に関するクラスをさらに作る場合は、色の設定処理が洗練された書き方にできない。

(( Figure→FigureBox→FigureBoxColor ))
class Figure {
(略)
} ;
class FigureBox : public Figure {
(略)
} ;
class FigureBoxColor : public FigureBox {
private:
int color ;
public:
virtual void draw( int x , int w ) {
GWsetpen( ... , color , ... ) ; // ださい
FigureBox::draw( x , y ) ;
}
} ;

多重継承

前のFigureBoxColorの例は、色のクラスが後付なので、色に関する処理が複雑であったとして、 その処理を隠蔽化するにはどうすればよいか？ 一つの方法が、多重継承である。

class Figure {
(略)
} ;
// 色を扱うクラス
class Color {
private:
int color ;
public
Color( int c ) ;
void setcolor() {
GWsetcolor( ... , color , ... ) ;
}
} ;
// 色無しのクラスはそのまま使える
class FigureBox : public Figure {
(略)
} ;
class FigureBoxColor : public FigureBox , public Color {
public:
FigureBoxColor( int w , int h , int c )
: FigureBox( w , h ) ,
Color( c ) {}
virtual void draw( int x , int y ) {
setcolor() ; // Colorのメソッドを使う
FigureBox::draw( x , y ) ;
}
} ;

ただし多重継承は以下の理由から、実装が複雑化することから、Javaなどの言語では別の方法を用いる。

• 継承は、派生したクラスのデータが基底クラスの後ろに繋がる形で実装される。 データ領域の先頭部分は基底クラスのデータ領域であり、基底クラスの参照は極めて単純。 しかし、多重継承を認めると、データ領域の後ろに派生データを追加する方法では、 途中に別の基底クラスのデータ領域を挟み込む形になるため、基底クラスを参照することが複雑になる。
• また、基底クラスに同名のメソッドがあった場合、派生クラスでのメソッド呼び出しでどちらを呼び出すべきか、曖昧になる。
• さらに、ダイヤモンド継承があると、基底クラスのデータが2重化する可能性がある。

  (( ダイヤモンド継承 ))
  　　　動物クラス[誕生日]
  　　／　　　　＼
  鳥クラス[羽]　　哺乳類クラス[手]
  　　＼　　　　／　
  　　　カモノハシ
  // 鳥クラスは要素として[誕生日,羽]を持つ
  // 哺乳類クラスは、[誕生日,手]を持つ
  // カモノハシクラスは、[誕生日,羽,誕生日,手]を持つ？？？
  

UML

UML(Unified Modeling Language)とは、オブジェクト指向で、データ構造や処理の流れを図で表現するための手法として 考えられた。

例えば、処理の流れを図示する場合のフローチャートは、初心者でも分かりやすい。 しかし、長方形のマスの中に複雑な処理を記入するのは困難となる。 改良版として、PADという記法もあるが、あまり普及していない。

歴史的に見れば、 ランボーの提唱したオブジェクトモデル化技法(OMT)、 ブーチがオブジェクト指向設計(OOD)でのBooch法、 ヤコブソンのオブジェクト指向ソフトウェア工学(OOSE)の考え方を元に、 UML(統一モデリング言語)が策定された。

UMLでの図の表現は、データ構造を表現するクラス図、コンポーネント図、オブジェクト図、パッケージ図などがあり、 一方で処理の振舞いを記述する、アクティビティ図、ユースケース図、状態遷移図、相互作用図、シーケンス図などがある。 詳しくは次週の講義にて、説明。

学術研究機関を対象とした、無償のSSL認証キーの発行サービスの申請のTSVファイル生成だが、 機構管理下となったので、手順が一部変更となった。 手順が長いので、肝心な所は記載しないが、その入力などの内容をメモ。 最終的に、電子情報工学科のTSVファイルと、緊急連絡システム用のTSVファイルを作った。

# mkdir /etc/apache2/ssl.key/
# cd /etc/apache2/ssl.key/
# cp 大きいファイル1 randfile1.txt
# cp 大きいファイル2 randfile2.txt
# cp 大きいファイル3 randfile3.txt
# openssl genrsa -des3
-rand randfile1.txt:randfile2.txt:randfile3.txt 2048
> iris.key
Enter pass phrase: [passphrase]
Verifying - Enter pass phrase: [passphrase]
# lv iris.key
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,xxxxxxxxx
:
-----END RSA PRIVATE KEY-----
# openssl req -new -key iris.key -sha1 -out iris.csr
Enter pass phrase for maisy.key: [passphrase]
Country Name (2 letter code) [AU]:JP
State or Province Name (full name) [Some-State]:.
Locality Name (eg, city) []:Academe
Organization Name (eg, company) [Internet Widgits Pty Ltd]:National Institute of Technology
Organizational Unit Name (eg, section) []:Fukui College
Common Name (eg, YOUR name) []:www.ei.fukui-nct.ac.jp
Email Address []:.
Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:.
An optional company name []:.
maisy:/etc/apache2/ssl.key# lv iris.csr
-----BEGIN CERTIFICATE REQUEST-----
:
-----END CERTIFICATE REQUEST-----
maisy:/etc/apache2/ssl.key# openssl req -noout -text -in iris.csr
Certificate Request:
Data:
Version: 0 (0x0)
Subject: C=JP, L=Academe2, O=Fukui National College of Technology,
OU=Electronics and Information Department,
CN=www.ei.fukui-nct.ac.jp
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (2048 bit)
Modulus (2048 bit):
https://certs.nii.ac.jp/cgi-bin/tsvtool.cgi
TSV作成ツール:発行申請TSV
・CSRファイルから　iris.csr [CSR送信]
CSR
主体者DN CN=www.ei.fukui-nct.ac.jp,OU=...
サーバFQDN www.ei.fukui-nct.ac.jp
dNSName   なし
加入者Email 自分のメール
加入者氏名   斉藤　徹
加入者所属   福井工業高等専門学校電子情報工学科
ソフトウェア名等  Apache 2.4.6
[完了]
[ダウンロード]
issue-YYYYMMDD.tsv

実際に鍵を登録

UPKIの事務局に、issue-YYYYMMDD.tsv を送ったら、 鍵を入手するための「UKPI-ODCert]Webサーバ証明書発行受付通知」なるメールが 送られてきた。指定されたURLをアクセスして、サーバ証明書を受け取る。 ファイル名は、"サーバFQDN.cer"であった。(Apacheへの登録では"*.crt"に直す)
これに加えて、別途 "nii-odca3sha1.cer" を入手しておく。

このままだと、Webサーバ起動時にパスフレーズを聞かれるので、

# openssl rsa -in iris.key -out iris-passphrase.key
:
Enter pass phrase for iris.key: [passphrase]

# cd /etc/apache2/ssl.key
# mv ...PATH.../サーバFQDN.cer ./iris.crt
# vi /etc/apache2/sites-enabled/100-default-ssl
:
SSLCertificateFile    /etc/apache2/ssl.key/iris.crt
SSLCertificateKeyFile /etc/apache2/ssl.key/iris-passphrase.key
SSLCertificateChainFile /etc/apache2/ssl.key/nii-odca3sha1.crt
:
# /etc/init.d/apache2 restart