ホーム » 2015 » 10月

月別アーカイブ: 10月 2015

2015年10月
« 9月   11月 »
 123
45678910
11121314151617
18192021222324
25262728293031

最近の投稿(電子情報)

アーカイブ

カテゴリー

地域経済分析システムRESAS

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

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

1510302149_1024x768.jpeg
1510302149-1_1024x768.jpeg

福井県の耕作放棄地率

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

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

1510302149_681x589.PNG

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

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

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

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

2項演算と構文木

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

   +
  / \
 1   *
    / \
   2   3

1つのノードは、演算子か末端の数値であることに注目し、 右枝・左枝が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と串刺し処理と副問い合わせ

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 による直積では、異なる表のすべての組合せを簡単に実現できるが、 1つの表の組合せはどうであろうか?このための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回)

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

担当:松島(4C)、田中(2B、MC)、川﨑(2EI、MIX)、鷲田(1EI)、西(教員)

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

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

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

1510250910-3_1024x768.JPG

走行動画

他の写真

1510250910-2_1024x768.JPG
1510250910_1024x768.JPG
1510250910-1_1024x768.JPG
1510250910-4_1024x768.JPG

構造体のワード境界

今日は、構造体を使ったプログラミングの演習。 単純な演習だけでは、来週に研修旅行を予定している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回)

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

担当:松島(4C、MC)、田嶋(3C)、島脇(2B)、田中(2B、MIX)、西(教員)

校内プロコンの問題

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

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

ぷよぷよ連鎖

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

問題は、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×9の将棋盤上に、竜馬(成り角)をお互い取られないように並べたい。 最大おける個数とその配置を答えよ。別解が複数ある場合は、最低1つ出力すればよい(全解でもよい)。
9桂馬
同じく、9×9の将棋盤上に、敵方向に向いた桂馬をできるだけ多く並べたい。 ただし、各桂馬は、次の1手が打てること。 次の1手で移動した先に、他の桂馬が無いこと。
この条件を満たすように桂馬を置く場合、最大いくつ置けるか? その配置も答えよ。

評価方法

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

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

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

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

Debianのapache2の設定方法

学生が、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)

  1. 必要なモジュールをインストールすると、 設定ファイルは /etc/apache2/mods-available に書き込まれる。
    (モジュール名.load モジュール名.conf)
      使えるモジュールは、以下のコマンドを使えば、一覧が見れる。
      $ aptitude search libapache2-mod
      インストールしたいモジュールが見つかったら
      $ sudo aptitude install libapache2-mod-モジュール
    
  2. 本当に使いたいモジュールは、以下のコマンドを実行。
      $ sudo /usr/sbin/a2enmod モジュール名
      /etc/apache2/mods-enabled に、mods-available への
      シンボリックリンクを作ってくれる。
    

    使いたくなくなったら、

      $ sudo /usr/sbin/a2dismod モジュール名
    
  3. a2enmodなどを実行したら、以下のコマンドで apache2を再起動
      $ sudo /etc/init.d/apache2 restart
    

    基本原則 /etc/apache2/mods-enabled の配下の設定ファイルは触らない。 どうしても設定ファイルを変更したい場合は、conf-enabled , site-enabled で設定。

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

  1. apache2では、1台のコンピュータで複数のwebサイトを構築できる。 バーチャルホストの設定は1つのホスト毎に、sites-available の *.conf に記述。 ホスト毎の細かい設定は、この中に記述する。
  2. そのホストを使えるようにしたかったら、以下のコマンド。
      $ sudo /usr/sbin/a2ensite ホスト
      /etc/apache2/site-enabled に、site-available への
      シンボリックリンクを作ってくれる。
    

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

      $sudo /usr/sbin/a2dissite ホスト
    
  3. a2ensite を実行したら、"/etc/init.d/apache2 restart"

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

  1. site-* では、各ホスト毎の設定を書くけど、すべての仮想ホストに共通な 設定は、conf-enabled / conf-available を使う。
  2. 設定を /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の最初

関係データベースの導入説明が終わったので、実際の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 ;