ホーム » 2015 » 10月

月別アーカイブ: 10月 2015

2015年10月
日	月	火	水	木	金	土
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

地域経済分析システムRESAS

2015年10月30日

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

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

福井県の耕作放棄地率

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

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

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

2分木の応用(構文木と決定木)

2015年10月30日

今日は、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 ) ;
}

SQLと串刺し処理と副問い合わせ

2015年10月26日

SQLの基本命令selectの使い方を説明したけど、複数の表を組合せた処理の記述の説明が不十分だったので、串刺しに相当する処理を説明

SQLの直積と串刺し処理

データベースの処理の例として、学生と科目の成績表を使って説明。

まずは、以下の様な表データがあったとする。

User(学生のテーブル)
uid  | name | ...
-----+------+------
1000 | 斉藤 | ...
1001 | 青山 | ...
1002 | 坂本 | ...
Subject(科目名のテーブル)
sid  | name | 単位...
-----+------+------
2000 | データベース ...
2001 | 数学 ...
2002 | 情報構造論
Result(成績表)
uid  | sid  | point
-----+------+-----
1000 | 2000 | 75
1001 | 2000 | 80
1002 | 2001 | 90

このデータの中から、80点以上の情報が欲しければ、SQL や C言語で書くなら、以下のようになるであろう。

(( SQL ))
select Result.point
   from Result
   where Result.point >= 80 ;
(( C言語 ))
for( i = 0  ; < Result.length ; i++ )
   if ( Result[ i ].point >= 80 )
   printf( "%d¥n" , Result[ i ].point ) ;

しかし、点数ではなく、氏名や科目名が欲しいのなら、C言語なら以下の様な処理を記述することになる。

// C言語で複数の表を串刺し
for( i = 0  ; i < Result.length ; i++ )
   if ( Result[ i ].point >= 80 ) {
      // 対応する名前を探す
      for( j = 0 ; j < User.length ; j++ )
         if ( User[j].uid == Result[i].uid )
            break ;
      // 対応する科目名を探す
      for( k = 0 ; k < Subject.length ; k++ )
         if ( Subject[k].sid == Result[i].sid )
            break ;
      printf( "%s %s¥n" , User[j].name , Subject[k].name ) ;
   }

この場合、if文の処理回数は、Result.length回 + (1/2)*User.length回 + (1/2)*Subject.length回となるであろう。 (1/2)は、単純検索の平均回数の意味。

この処理を SQL で行う場合は、以下のようになるであろう。

(( SQLでの串刺し ))
select User.name , Subject.name
   from User , Subject , Result
   where User.uid = Result.uid
         and Subject.sid = Result.sid
         and Result.point >= 80 ;
         -- 2つのand節が重要 --

この問い合わせ文では、"from User,Subject,Result"が直積で、すべての組合せを行うというイメージで捉えると、以下の様なC言語のイメージを持つであろう。

for( i = 0 ; i < Result.length ; i++ )
   for( j = 0 ; j < User.length ; j++ )
      for( k = 0 ; k < Subject.length ; k++ )
         if ( User[j].uid == Result[i].uid
              && Subject[k].sid == Result[i].sid
              && Result[i].point >= 80 ) {
            printf( "%s %s¥n",User[j].name,Subject[k].name ) ;
         }

このプログラムでは、ループ回数は、Result.length * User.length * Subject.length であり、これだけをみると、処理効率が悪いように見える。しかし、データベースシステムは、UserやSubjectの列の検索で、uid,sidの値から、ハッシュ法やB木を使って探すかもしれない。そうすれば、串刺し検索の処理も必ずしも効率が悪いとは言えないし、そういった部分はデータベースシステムに任せ、その他のプログラムを効率よく書けば生産性が高いはず。

where節で使える特殊な比較命令

where節で使える比較命令には、大小比較やand,or 以外にも、以下の様な条件も記述できる。

((集合計算))
where 式 in ( 値1,値2, ... ) ;
((範囲計算))
where 式 between 値1 and 値2 ;
((空判定))
where 式 is null ;
((文字列パターンマッチ))
where 文字列 like 'c%t' ;
_ 1文字の任意文字　　c_t = cat ◯ , chart ×
% 0文字以上の任意文字 c%t = cat ◯ , chart ◯

自己結合

from による直積では、異なる表のすべての組合せを簡単に実現できるが、１つの表の組合せはどうであろうか？このためのfrom節の書き方に自己結合がある。

例えば、前例のUserの中で、同姓同名の人がいるかどうかを探したい場合は、自己結合で以下のように記述する。

select U1.name
   from  U1 User , U2 User
   where U1.name = U2.name
         and U1.uid <> U2.uid ;

副問い合わせ命令

SQLの問い合わせで便利なのが副問い合わせ命令であろう。特殊な相関副問い合わせを考えないのであれば、 () の中に記述された select 文を先に実行すると考えればいいであろう。

(( 斉藤の80点以上を出力 ))
select User.name
   from  User
   where User.uid in ( select Result.uid
                          from  Result
                          where Result.point >= 80 )

この副問い合わせでは、() の中の問い合わせを先に実行すると、1001,1002 が求まり、 where User.uid in ( 1001 , 1002 ) という条件となり、最終的にその名前が求まる。

2015年10月25日(第446回)

2015年10月25日

高専祭の反省
遠足・研修旅行について
ジャズバー歴史　１８杯目「割り算と文化」

担当：松島（４Ｃ）、田中（２Ｂ、ＭＣ）、川﨑（２ＥＩ、ＭＩＸ）、鷲田（１ＥＩ）、西（教員）

GPS・QZSSロボットカーコンテスト/ダブルパイロンレース優勝

2015年10月25日

2015年10月24日に東京海洋大学で開催された、 GPS・QZSSロボットカーコンテストで、4EI牛若くん・小川くんが、ダブルパイロンレースで参加14チームの中で優勝でした。

GPS航法のコンテストということで、加速度センサーを使ってはいけないという条件のなか、なかなかスムーズな走りを見せてくれました。

走行動画

他の写真

構造体のワード境界

2015年10月20日

今日は、構造体を使ったプログラミングの演習。単純な演習だけでは、来週に研修旅行を予定している3年は授業の遅れも心配なので、前半にワード境界の話をする。

ワード境界

struct Data {
   char name[3] ;
   int  point ;
} ;
struct Data array[3] ;
// 構造体の大きさは何バイト？
printf( "%d\n" , sizeof( struct Data ) ) ;
printf( "%d\n" , sizeof( array ) ) ;

簡単なデータのバイト数の知識だけであれば、Dataの大きさは、3byte+4byteの 7byteと思うかもしれない。しかし、この考えだと、array の配列は、メモリ上に以下に並ぶと思うであろう。

n1,n1,n1が、array[1].nameの3byteをあらわすとする。
n0,n0,n0,p0,p0,p0,p0,n1,n1,n1,p1,p1,p1,p1,n2,n2,n2,p2,p2,p2,p2

しかし、最近のコンピュータでは、CPUクロック2GHz,メモリクロック1GHzといった速度で、メモリの速度はCPUに比べて遅い。このため、CPUがメモリのデータを読み出す際は、複数のbyte数を一括して読み込む。このデータの単位は32bitコンピュータであれば、 4byte単位であったりする。

ワード境界を考えない構造体要素の配置の場合
0行目:n0,n0,n0,p0,
1行目:p0,p0,p0,n1,
2行目:n1,n1,p1,p1,
3行目:p1,p1,n2,n2,
4行目:n2,p2,p2,p2,
5行目:p2,--,--,--,

この場合、array[1].pointを読み出そうとすると2行目と3行目の2回にわけてデータを読み込むことになり、プログラムの速度が落ちてしまう。

このため、構造体の要素をメモリに保存する場合、4byte毎の「ワード境界」をまたがってデータを配置しないようにするのが普通である。こういうメモリへの配置を「ワードアライメント」という。

ワード境界を考え、途中に空き(xx)を配置した例
0行目:n0,n0,n0,xx,
1行目:p0,p0,p0,p0,
2行目:n1,n1,n1,xx,
3行目:p1,p1,p1,p1,
4行目:n2,n2,n2,xx,
5行目:p2,p2,p2,p2

ということで、sizeof( struct Data ) は、8byteとなるのが普通である。ただし、処理速度を犠牲にしてメモリ量を節約する必要がある場合には、 "#pragma …."といったプリプロセッサ命令で、隙間を詰めることもできる。

「ワード」とは、8bit = 1byte より大きいデータ単位で、16bitであったり、32bitであったりする。機械語でプログラムを記述する際には、以下のように区別することが多い。
16bit = 2byte = ワード(WORD),対応する型：short int
32bit = 4byte = ダブルワード(DWORD)、対応する型：int,float
64bit = 8byte = QWORD、対応する型：double

2015年10月18日(第445回)

2015年10月18日

高専祭について
弁論大会の結果について
ジャズバー歴史　１７杯目「人物の肖像」

担当：松島（４Ｃ、ＭＣ）、田嶋（３Ｃ）、島脇（２Ｂ）、田中（２Ｂ、ＭＩＸ）、西（教員）

校内プロコンの問題

2015年10月14日

高専プロコンの競技部門や、プログラミング甲子園に、学生さんが参加しているけど、パズル問題は再帰呼び出しとかの経験がないと難しい。

そこで、校内プロコンをやって実力をつけてもらおう…という話がでてきたので、定番のパズル問題を、私なりにひねってみた。プログラミング甲子園でも、同じ問題があったかもしれないけど、一応私が考えた問題をいかに示す。

ぷよぷよ連鎖

6×6のます目に、ぷよぷよのブロックがいくつか落ちた状態の情報が記録されている。ブロックを１つ落とすなら、どこがいいか答えよ。

問題は、C言語の配列で与えられる。

ぷよぷよのブロックの色は、アルファベット1文字で表現し、黄Y,緑G,赤R,青Bの4色とする。
ブロックの無い場所には空白が入っている。
1行の7文字目には\0が入っていて、C言語の配列としては6×7とする。

(例)
char field[6][7] = {
   "      " ,
   "  GGGB" ,
   " YYYBG" ,
   " RRGRR" ,
   "BBRGRB" ,
   "RRBGBR" ,
} ;

このマス目にぷよぷよのブロックを1つ落とす。どこに何色を落とすと何ブロック消せるか求め、消えるブロック数が最大となる場合の、場所と色を答えよ。連鎖のルールはぷよぷよと同じとする。

最大の式

文字列で与えられた数字と演算子を組み合わせて数式を作る。その数式の最大値を答えよ。

式をつくる条件は以下の通りとする。

数字は1桁とし、必ず間に演算子を挟むこと。(43はNG)
すべての文字を使わなくてもいい
同じ数字や演算子を2度使うのは禁止。112+*が与えられた場合、2*2+2はNG。2*1+1はOK
与えられる文字は、0-9,+,-,*,/,(,)
0除算が発生する式はNGで、C言語の文法として正しいこと。

int max_exp( char exp[] , char src[] ) {
   // src: 与えられる文字
   // exp: 答えの式
   // 返り値: その式の値
}
int main() {
   char ans[ 10 ] ;
   int ans = max_exp( ans , "1234+-*" ) ;
   printf( "%s = %d\n" , exp , ans ) ;
   // たぶん、4*3+2 が答えだと思う。
   return 0 ;
}

8クイーンの将棋バージョン

プログラミングの組み合わせ問題の有名なもので、8クイーンがある。 8クイーンは、チェスの盤面にお互いに取られないように、8つのクイーンの置き方を答える問題。

これの将棋バージョンの問題として、以下2つの問題を答えよ。

9竜馬
9桂馬

評価方法

以上のプログラムを、すべての提出されたプログラムがそろった段階で、すべてを実行させ最適解を答えられたものについて、処理速度とシンプルさで評価する。

処理速度は、答えやデバッグ用出力をすべてコメントアウトし、処理関数を100回とか1000回とか複数回実行させるようにしたプログラムで、コンパイルする。処理開始、処理終了の時間差を求めて比較する。(unixのtimeコマンドなどで比較)

プログラム言語は、問題趣旨に沿っていれば、なんでもよい。ただし、コンパイル結果の時間で比べるため、同一プログラムがJavaプログラムとCプログラムであれば、 C言語の方が有利となる。

プログラムのシンプルさについては、空白行やC言語のプリプロセッサ行を消した状態で、一般的なプログラム清書プログラム(例えばcb)にかけた結果の行数が少ないものを勝ちとする。

Debianのapache2の設定方法

2015年10月14日

学生が、Raspberry-PiでCGIを使いたいらしいけど、設定の方法がDebianは一癖あるので、説明資料を記述。

Debianの原則

Debianでは、基本的な設定ファイルは極力自分で触らない主義。

apache2 も同様で、便利なモジュールも設定ファイルは、必要なものはモジュール毎にインストール時に読み込ませて、触らない主義。

このための設定があって、 CGIとかPHPといったものは、モジュールで管理。

DebianのApache2設定ファイルの考え方

一般的なApacheでは、設定は、/etc/apache2/apache2.conf とか、 /etc/apache2/httpd.conf に記述する。しかし、いくつものモジュールを使うと、これらの設定ファイルが、巨大で理解困難になってしまう。

このためDebianのapache2 では、/etc/apache2/*-enabled で対応する。 /etc/apache2/apache2.conf には、以下のような行が書いてあり、 *-enabled配下の設定ファイルをすべて読み込んで起動する。

(( /etc/apache2/apache2.confの一部 ))
　IncludeOptional mods-enabled/*.load
　IncludeOptional mods-enabled/*.conf
　IncludeOptional conf-enabled/*.conf
　IncludeOptional site-enabled/*.conf

/etc/apache2/mods-enabled (mods-available)

必要なモジュールをインストールすると、設定ファイルは /etc/apache2/mods-available に書き込まれる。
(モジュール名.load モジュール名.conf)

　　使えるモジュールは、以下のコマンドを使えば、一覧が見れる。
　　$ aptitude search libapache2-mod
　　インストールしたいモジュールが見つかったら
　　$ sudo aptitude install libapache2-mod-モジュール

本当に使いたいモジュールは、以下のコマンドを実行。

　　$ sudo /usr/sbin/a2enmod モジュール名
　　/etc/apache2/mods-enabled に、mods-available への
　　シンボリックリンクを作ってくれる。

使いたくなくなったら、

　　$ sudo /usr/sbin/a2dismod モジュール名

a2enmodなどを実行したら、以下のコマンドで apache2を再起動
```
　　$ sudo /etc/init.d/apache2 restart
```
基本原則 /etc/apache2/mods-enabled の配下の設定ファイルは触らない。どうしても設定ファイルを変更したい場合は、conf-enabled , site-enabled で設定。

/etc/apache2/sites-enabled (sites-available)

apache2では、1台のコンピュータで複数のwebサイトを構築できる。バーチャルホストの設定は1つのホスト毎に、sites-available の *.conf に記述。ホスト毎の細かい設定は、この中に記述する。

そのホストを使えるようにしたかったら、以下のコマンド。

　　$ sudo /usr/sbin/a2ensite ホスト
　　/etc/apache2/site-enabled に、site-available への
　　シンボリックリンクを作ってくれる。

ホストを使えないようにする。

　　$sudo /usr/sbin/a2dissite ホスト

a2ensite を実行したら、"/etc/init.d/apache2 restart"

/etc/apache2/conf-enabled (cont-available)

site-* では、各ホスト毎の設定を書くけど、すべての仮想ホストに共通な設定は、conf-enabled / conf-available を使う。
設定を /etc/apache2/conf-available の中に、設定名.conf で記述し、以下のコマンドで有効にする。
```
　　$ sudo /usr/sbin/a2enconf 設定名
　　$ sudo /usr/sbin/a2disconf 設定名
```

(例)

CGIを使いたい (CGIは基本モジュールなのでlibapache2-mod-cgi などはしなくていい)

　$ sudo /usr/sbin/a2enmod cgi　　# cgiモジュールの有効化
　$ sudo /etc/init.d/apache2 restart

PHP5を使いたい

　$ sudo aptitude install php5 　　# PHP5をインストール
　$ sudo aptitude install libapache2-mods-php5
　                          # apache2のphp5モジュールをインストール
　$ sudo /usr/sbin/a2enmod php5　　# php5モジュールの有効化
　$ sudo /etc/init.d/apache2 restart　　# apache2 の再起動

ページは各ユーザの /home/user/public_html/ 配下に作らせたい。

　$ sudo /usr/sbin/a2enmod userdir

SSLのhttps://を使いたい

　$ sudo vi /etc/apache2/site-available/default-ssl.conf
　$ sudo /usr/sbin/a2ensite default-ssl
　$ sudo /etc/init.d/apache2 restart

SQLの最初

2015年10月13日

関係データベースの導入説明が終わったので、実際のSQLの説明。

create user

データベースを扱う際の create user 文は、DDL(Data Definition Language)で行う。

CREATE USER ユーザ名
IDENTIFIED BY "パスワード"

grant

テーブルに対する権限を与える命令。

GRANT システム権限 TO ユーザ名
   データベースシステム全体に関わる権限をユーザに与える。
   (例) GRANT execute ON admin.my_package TO saitoh
GRANT オブジェクト権限 ON オブジェクト名 TO ユーザ名
   作られたテーブルなどのオブジェクトに関する権限を与える。
   (例) GRANT select,update,delete,insert ON admin.my_table TO saitoh
REVOKE オブジェクト権限 ON オブジェクト名 TO ユーザ名
   オブジェクトへの権限を剥奪する。

create table

実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。

CREATE TABLE テーブル名
   ( 要素名1  型 , 要素名2 型 ... ) ;
   PRIMARY KEY 制約
   型の後ろに"PRIMARY KEY"をつける、
   もしくは、要素列の最後に、PRIMARY KEY(要素名,...)をつける。
   これによりKEYに指定した物は、重複した値を格納できない。

型には、以下の様なものがある。(Oracle)
   CHAR( size)  : 固定長文字列 / NCHAR国際文字
   VARCHAR2( size ) : 可変長文字列 / NVARCHAR2...
   NUMBER(桁) :指定 桁数を扱える数
   BINARY_FLOAT / BINARY_DOUBLE : 浮動小数点(float / double)
   DATE : 日付(年月日時分秒)
   SQLiteでの型
   INTEGER : int型
   REAL : float/double型
   TEXT : 可変長文字列型
   BLOB : 大きいバイナリデータ

DROP TABLE テーブル名
   テーブルを削除する命令

insert,update,delete

指定したテーブルに新しいデータを登録,更新,削除する命令

INSERT INTO テーブル名 ( 要素名,... ) VALUES ( 値,... ) ;
   要素に対応する値をそれぞれ代入する。
UPDATE テーブル名 SET 要素名=値 WHERE 条件
   指定した条件の列の値を更新する。
DELETE FROM テーブル名 WHERE 条件
   指定した条件の列を削除する。

select

データ問い合わせは、select文を用いる、 select文は、(1)必要なカラムを指定する射影、(2)指定条件にあうレコードを指定する選択、 (3)複数のテーブルの直積を処理する結合から構成される。

SELECT 射影 FROM 結合 WHERE 選択
   (例) SELECT S.業者番号 FROM S WHERE S.優良度 > 30 ;