vmware の Webリモートコンソールの画面に接続しようとしたら、 『サーバーは短い一時 Diffie-Hellman 公開鍵を使用しています』といった 警告メッセージが表示されて接続に失敗する。 「IEだったらうまくいく」とのことだったけど、こっちはMacなので対応できず。

調べてみると、下記のような設定をすれば、Firefox なら接続できた。

(( Firefox にて ))
address bar にて、"about:config" を入力
検索で"dhe_rsa_aes"を検索すると、
o security.ssl3.dhe_rsa_aes_128_sha ユーザ設定 真偽値 true
o security.ssl3.dhe_rsa_aes_128_sha ユーザ設定 真偽値 true
が表示されるので、項目をクリックして、false に修正すればいい。

出張の都合により、今日は授業を入替え、3年の授業。
構造体の理解については、明日の授業で演習を行う。今日は、振替えで演習室も使えないので、 普通の講義。

ビットフィールド

例えば、生年月日を記憶する場合、構造体を使えば以下のように宣言できるが、 int型(32bit=4byte)であれば、12byteを要する。

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

しかし、生年月日の比較などをする場合であれば、 年月日を10進数の桁に合わせて、日付を 20151109 といった数値で表すことも多い。 この場合であれば、int 型 2^31-1 = 2,000,000,000 にも収まる。 プログラムも解りやすくするのであれば、以下の様な補助関数を準備すれば良い。

int ymd10_year( int ymd ) {
   return ymd / 10000 ;
}
int ymd10_month( int ymd ) {
   return (ymd / 100) % 100 ;
}
int ymd10_day( int ymd ) {
   return ymd % 100 ;
}

しかし、このプログラムでは、日の1〜31までの数字のために、0〜99の10進2桁を使う。 月の1〜12のために0〜99の10進2桁を使う。 また、各桁を抜き出すために、除算を使うため処理も手間がかかる。

そこで、年月日を2進数の桁の組合せで保存することを考える。こうすれば、2進数のビットシフト命令で機械語では扱いやすくなる。

// 年(12bit),月(4bit),日(5bit) = Y,YYYY,YYYY,YYYM,MMMD,DDDD
int ymd2( int y , int m , int d ) {
   return (y << 9) | (m << 5) | d ;
}
int ymd2_year ( int ymd ) {
   return ymd >> 9 ;
}
int ymd2_month( int ymd ) {
   return (ymd >> 5) & 0xF ;
}
int ymd2 _day( int ymd ) {
   return ymd & 0x1F ;
}

しかし、この方法でデータを扱うと、月の値を1つ増やすといった処理を書こうと思うと、2進数の扱いに慣れていないと プログラムも間違いやすい。

int ymd = ymd2( 2015 , 11 , 9 ) ;
// ymd の月を12月に変更したい。
ymd = (ymd  & 0x1FFE1F) | (12 << 5) ;

このような処理のために、ビットフィールドを使用する。使い方は、構造体の要素の宣言の後ろに、": bit数"をかけばいい。 こうすれば、構造体の要素の参照の式をかけば、必要に応じて2進数を使った機械語命令をコンパイラが書いてくれる。

struct YMD {
   unsigned int  year  : 12 ;
   unsigned int  month : 4 ;
   unsigned int  day   : 5 ;
} ;

共用体

構造体と同じような文法の一つに共用体がある。 構造体では、異なる型の各要素のメモリの領域を準備するが、共用体では全要素が同じ場所を使う。 このため、どれか１つの値を覚えるだけでいい場合に使う。

union int_str4 {
   int  data ;
   char str[4] ;
} ;

union int_str4  a[4] ;
a[0].data = 1234 ;
strcpy( a[1].str , "ABC" ) ;
a[2].data = 2345 ;
strcpy( a[3].str , "BCD" ) ;
printf( "%d¥n" , sizeof( a ) ) ; // 4byte×4 = 16

この異なる型を同じ場所に覚えるための文法は、最近のオブジェクト指向のプログラム言語では、仮想関数という考え方 が利用できるので、あまり利用することは少なくなっている。

列挙型

プログラムの中で週のような情報を覚える時、日付の処理を考えると、 日=0,月=1,火=2,水=3,木=4,金=5,土=6　といった割り当てをすることも多い。 しかし、水曜の処理だったら…という時に、if ( week == 3 ) という書き方では、分かりにくい。

int wd = 1 ; // 月初めが月曜の場合...
int day ;
for( day = 1 ; day <= 31 ; day++ , wd = (wd + 1) % 7 ) {
   if ( wd == 3 ) {
      水曜日の処理...
   }
}
// マジックナンバーを使わない場合
#define SUN 0
#define MON 1
#define TUE 2
#define WED 3
: (略)
int wd = MON ; // 月初めが月曜の場合...
int day ;
for( day = 1 ; day <= 31 ; day++ , wd = (wd + 1) % 7 ) {
   if ( wd == WED ) {
      水曜日の処理...
   }
}

上のプログラムの後半のマジックナンバーを使わない例であれば、プログラムの意味も解りやすくなる。 しかし、#define を7つも書き並べるのは面倒だし、対応する数値を1つづつ増やしながら書くのは、 間違って修正するかもしれない。 こういう場合には、列挙型を用いる。

enum Week {
   SUN , MON , TUE , WED , THR , FRI , SAT
} ;
enum Week wd = MON ;
int day ;

for( day = 1 ; day <= 31 ; day++ ) {
   if ( wd == WED ) {
      水曜日の処理...
   }
   // wd 型は int ではないので、週番号を増やすのはちょっと面倒
   wd = (enum Week)( ( (int) wd + 1 ) % 7 ) ;
}

SQLの説明も大体終わったので、演習を行う。

SQLの演習

学内のアカウントでログインすれば、SQLite3 を使った簡単な演習ができる環境を 準備しているので、それを使って演習。 教科書で示されるデータなども、簡単に読み込めるようにしてある。

演習内容は、SQLでデータを検索する処理を2つ考え動かしてみる。 最低でも、2つのテーブルにまたがった処理であること。 できれば、副問い合わせなどを含んだ処理などにチャレンジすること。 また、そのSQL命令をC言語で記述したものを作り、 直積処理などの意味を考える。

提出は、SQL命令、C言語、説明、動作確認、考察が記載されていること。

• SQL実験環境
• C言語で書いた場合

前回の授業で、２分木の話の中にて構文木とかで複数の枝を持つ データ構造の話をしたので、今回はB木について説明

B木

B木はデータベースに利用されているデータ構造であり、 位数をNとした場合、１ノード内には、N個以上、2N未満のデータを持つ。 また、data[i-1] < x < data[ i ] の条件を満たすデータは、pointer[ i ] で示すノードに保存する。

// B木のデータ構造の宣言例
#define SIZE 2
struct BTree {
   int  size ; // ノード内のデータ件数
   int  data[ SIZE * 2 ] ;
   struct BTree* pointer[ SIZE * 2 + 1 ] ;
} ;

B木では、ノードにデータを追加する場合には、ノードが2Nにならないのであれば、単純にそのノードに データを追加する。追加してノード内データが2N個を越える場合には、 追加後のデータ列の中央値を、上位ノードに移動させ、そのノードは中央値の前後の２つのノードに分割を行う。

こうすることにより、データ追加時に一方的に延びる不均一な構造を避けることができる。

データベースシステム

このB木では、データを効率よく扱えるが、データベースシステムでは、目的の１件を探すだけでなく、 条件に合ったデータの組合せを全データの中から探す処理も重要となる。

この全件処理は、2分木であれば、再帰処理などを伴いデータベースシステムには取り扱いが困難となる。 そこで、全件をシーケンシャルにアクセスするための改良を施したB+木やB*木などを使う。

データベースシステムでは、データすべてを表形式で覚え、その表の組合せることで複雑なデータを表現する リレーショナルデータベースを使うことが多い。 詳しくは、５年データベースの講義資料を参照。

先日(10/28)の4EIの交流会にてバーベキューに参加しました。

地域経済分析システムRESASの出前講座を 内閣府地方創生推進室の方を招いて開催していただきました。

地方創成に何が必要かを分析するために、 オープンデータなどを集め視覚的に表示してくれるシステムであり、 様々な角度でのデータを地図上やグラフで表示してくれます。

福井県の耕作放棄地率

試しに、越前市などの農地情報を表示させてみましたが、 簡単な操作で耕作放棄地の率が表示できたりします。 そして、鯖江市や越前市が 放棄率が県平均よりかなり低く、 奥越の勝山市大野市も低いことが解りました。

だったら、県内の何処が耕作放棄地率を高めているのか…. 比較グラフを表示させてみたら、下記グラフのように、 嶺南….。 地方の様々な問題が、簡単に浮き彫りにできちゃいます。

ちなみに、RESASを用いた、「地方創生☆政策アイデアコンテスト」が開催中だそうです。

今日は、2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。

時間があまったので、対話システムの雑談から、eliza の話をして、 本当は人工無能「うずら」ちゃんの話をしようと思っていたけど、 チューリングテストの話になって、 アラン・チューリングの話になって、 映画イミテーションゲームの説明をして、 2045年問題の話をして….どんどん暗い話題に…

2項演算と構文木

先週の講義で、演算子の話をしておいたので、演算式の2分木で扱うプログラムを説明。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

１つのノードは、演算子か末端の数値であることに注目し、 右枝・左枝がNULLなら数値、それ以外は演算子として扱うとして…

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x )
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op ,
         struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = op ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL )
      return p->data ;
   else
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }
}

void main() {
   struct Tree* exp =
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) , tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

関連する雑談として、プログラム言語の構文木の説明を行い、 (1) 字句解析 , (2) 構文解析 を組み合わせて作るけど、 字句解析支援ソフト(lex)や構文解析支援ソフト(yacc)などの紹介も行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

((意思決定木の例:うちの子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s , struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ" ,
                    dtree( "速攻で病院" , NULL , NULL ) ,
                    dtree( "解熱剤で病院" , NULL , NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる" , NULL , NULL ) ,
                    dtree( "氷枕で病院" , NULL , NULL ) ) ) ;
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scant( "%d" , &ans ) ;
      if ( ans == 1 )
         d = d->yes ;
      else if ( ans == 0 )
         d = d->no ;
   }
   printf( "%s¥n" , d->qa ) ;
}