プログラミングコンテストの競技部門では、パズルのような組み合わせ問題が 出題されることが多い。そこで、この予備実験では、きわめて単純なパズル問題(組み合わせ問題) のプログラムについて扱う。

組み合わせ問題の基礎

簡単な問題として、「100未満の整数の値を３つ選び、その値を辺の長さとした場合、 直角三角形となるものをすべて表示する。」について考える。

一番簡単な方法は、以下となるであろう。

#include <stdio.h>
#include <math.h>
#include <time.h>
// 整数比の直角三角形の一覧を求める。
void integer_triangle( int n ) {
for( int a = 1 ; a < n ; a++ ) {
for( int b = 1 ; b < n ; b++ ) {
// 一番ダサい方法
for( int c = 1 ; c < n ; c++ ) {
if ( a*a + b*b == c*c ) {
printf( "%d %d %d\n" , a , b , c ) ;
}
}
}
}
}
int main() {
integer_triangle( 100 ) ;
return 0 ;
}

しかしこのプログラムの欠点としては、100×100×100回のループで無駄な処理が多い。

ループ回数を減らすだけなら、最も内側の処理を、計算で整数値か確認すればいい。

void integer_triangle( int n ) {
for( int a = 1 ; a < n ; a++ ) {
for( int b = 1 ; b < n ; b++ ) { // ココも改良できるよね？
int d = a*a + b*b ;
int c = (int)sqrt( d ) ; // 斜辺Cの整数値を求め、改めて確認する。
if ( c*c == d ) {
printf( "%d %d %d\n" , a , b , c ) ;
}
}
}
}

また、この2つのプログラムの処理時間を実際に比べてみる。

int main() {
time_t start , end ;
// time() 関数は、秒数しか求まらないので、
// あえて処理を1000回繰り返し、数秒かかる処理にする。
start = time( NULL ) ;
for( int i = 0 ; i < 1000 ; i++ ) {
// ただし、関数内のprintfをコメントアウトしておくこと
integer_triangle( 100 ) ;
}
end = time( NULL ) ;
printf( "%lf\n" , difftime( end , start ) ) ;
return 0 ;
}

再帰プログラミング

組み合わせ問題では、forループの多重の入れ子で問題を解けない場合が多い。 (書けないことはないけど無駄なループで処理が遅くなるか、入れ子段数が可変にできない。)

こういった場合には、再帰プログラミングがよく利用される。 もっとも簡単な再帰の例として、階乗のプログラムを考える。 通常であれば、以下のような for ループで記述することになるだろう。

// 階乗の計算
int fact( int x )
{ // ループ
int f = 1 ;
for( int i = 2 ; i <= x ; i++ )
f = f * i ;
return f ;
}

再帰呼び出しでは、関数の処理の中に、自分自身の関数呼び出しが含まれる。 また、無限に自分自身を呼び出したら処理が止まらないので、 問題を一つ小さくして、これ以上小さくできないときは処理を止めるように記述する。

int fact( int x )
{ // 再帰呼び出し
if ( x <= 1 )
return 1 ;
else
return x * fact( x - 1 ) ;
}

指定長を指定辺の組み合わせで作る

再帰を使った簡単なパズル問題として、以下のプログラムを作成したい。

配列の中に、複数の辺の長さが入っている。これを組み合わせて指定した長さを作れ。 使用する辺はできるだけ少ない方がよい。
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
(例) 辺の長さ10を作るには、(5,4,1)とか(7,3)などが考えられる。
これは、ナップサック問題の基本問題で、容量の決まったナップサックに最大量入れる組合せを求めるのと同じである。

このプログラムを解くには…

10 を [4,5,2,1,3,7] で作るには...
　(0) 6=10-4 を [5,2,1,3,7]で作る。
　(1) 5=10-5 を [4,2,1,3,7]で作る。
　(2) 8=10-2 を [5,4,1,3,7]で作る。
　(3) 9=10-1 を [5,2,4,3,7]で作る。
　(4) 7=10-3 を [5,2,1,4,7]で作る。
　(5) 3=10-7 を [5,2,1,3,4]で作る。

そこで、ここまでの考えを、以下のようなプログラムで記述してみる。

// 指定されたデータを入れ替える。
void swap( int*a , int*b )
{ int x = *a ;
*a = *b ;
*b = x ;
}
void check( int array[] , int size , int len , int n )
{
// array[] 配列
// size    配列サイズ
// len     作りたい長さ
// n       使った個数
for( int i = n ; i < size ; i++ ) {
// i番目を先頭に...
swap( &array[ n ] , &array[ i ] ) ;
printf( "check( array , %d , %d , %d )\n" ,
size , len - array[ n ] , n+1 ) ;
// 最初のswapでの変更を元に戻す。
swap( &array[ i ] , &array[ n ] ) ;
}
}
int main() [
int a[] = { 4 , 5 , 2 , 1 , 3 , 7 } ;
check( a , 6 , 10 , 0 ) ;
}

void check( int array[] , int size , int len , int n )
{
// array[] 配列
// size    配列サイズ
// len     作りたい長さ
// n       使った個数
if ( len < 0 ) {
// 指定した丁度の長さを作れなかった。
;
} else if ( len == 0 ) {
// 指定した長さを作れたので答えを表示。
for( int i = 0 ; i < n ; i++ ) {
printf( "%d " , array[ i ] ) ;
}
printf( "\n" ) ;
} else {
// 問題を一つ小さくして再帰。
for( int i = n ; i < size ; i++ ) {
swap( &array[ n ] , &array[ i ] ) ;
printf( "check( array , %d , %d , %d )\n" ,
size , len - array[ n ] , n+1 ) ;
check( array , size , len - array[ n ] , n + 1 ) ;
swap( &array[ i ] , &array[ n ] ) ;
}
}
}

今日は午後から、武生高校バド部との練習試合でした。

情報公開制度

法人に、個人や法人が(理由を問わず)情報公開を求めることができる制度。 請求書は、300円の手数料。不開示情報でなければ、ありのまま原則公開。

不開示情報とは、個人情報・個人他機関の利益を害する恐れがあるものなど。(情報公開法第5条)

存否応答拒否(法8条): 個人情報が含まれる場合や、特定の法人名を指定した請求では、「文書の有無をお答えできません。」

不開示理由の提示では、どの情報が不開示情報に該当するのか、開示するとどういった支障があるのか、法5条何号に該当するのか….を最低でも示す必要がある。

個人情報の保護について

個人情報とは、特定の個人を識別できるもの。保有個人情報は、法人職員が業務上作成取得したもの。 非個人情報になるものとして、法人などの団体そのものに関する情報。 記号や数字の文字列だけから個人を特定できないもの。(学籍番号などは、他の情報とヒモ付すれば個人特定ができるので個人情報) 特定の個人を識別できない統計情報。

利用目的以外のために、保有個人情報を利用したり提供はダメ。

保有個人情報の開示請求

退官される先生から、磁気テープもらいました。(^_^)
容量わかると良いんだけど、不明っす。
授業の雑談のネタに使わせてもらいます。

授業アンケートは、情報処理センターが機器入替えで、 5年以上の回答しかないけど、5EIデータベースと1PSの計算機システムの 回答が集まった。

5EIデータベースは 88.8ポイントで、高いポイントがもらえた。 例年、"黒板とOHP"といった板書については、 評価が厳しい場合も多いけど、プロジェクタを使った説明を多用したこともあり、 評価が高かったかな。

専攻科の計算機システムの講義では、76.4ポイント。 授業の中では、技術要素の説明中心であり、演習量の所のポイントが低い。 他学科学生も多いことから、関心興味のポイントが若干低いが、 教員の説明のポイントは高いことから、ひとまずうまくできたと思っておこう。

新しいiMacを使うようになり、そろそろテスト時期。 LaTeXで作成しているテスト問題の編集をしようと思ったら、 Emacsでバックスラッシュが入力できず、円マークが表示される。 古い iMac では、￥で＼が普通に入力できたのに。

同様のトラブルの記事があったので、仕様が変わったのかな。 ということで、以下の設定を加える。

(if (eq window-system 'mac)
(progn
;; Mac日本語キーボードの ￥→＼ の変換
(define-key global-map [?￥] [?＼＼])
(define-key global-map [?＼C-￥] [?＼C-＼＼])))

計算機システムの授業のシメということで、 ネットワークのセキュリティ対策の説明を行う。 以下、キーワード抜粋。

セキュリティトラブルの原因

• ウィルスによる嫌がらせ
  • 愉快犯
  • 個人情報収集目的
  • 実行プログラムの添付ファイル
  • 記録媒体経由の感染
  • メールソフトの不備を攻撃(バッファオーバーフローなど)
• リモート接続での乗っ取り
  • クラッキングの踏み台
  • 個人情報収集
• DoSアタック
  • サービス停止
• 　悪さをしかける方法は様々。(総称してマルウェア)

対策

• ウィルス対策ソフトの導入
  • ウィルスデータベースとの比較による検出
  • 変異型ウィルス
• ファイアウォール
  • 様々なネットワークサービスで、サーバ側プログラムの不備を攻撃。
  • 不備のあるサーバは絨毯爆撃方式
  • 不用意にネットワークサービスに接続させないために
    　　ポートを塞ぐ。怪しいIPアドレスをブロック
• 個人レベルで防げない事例
  • DNSポイズニング
  • 特定攻撃型ウィルス
• 個人情報収集と暗号化
  • パケットスニッファ・WiFiの簡単な暗号化の危険性
  • SSL通信と公開鍵暗号
  • SNSでの不用意な友達申請の脅威
  • パスワードの2段階認証
• どうすべきか
  • ウィルス対策ソフト
  • ファイアウォール
  • OSとウィルス対策ソフトのデータベースの更新
  • ウィルス情報に注意
  • 怪しい添付を開かない、怪しいサイトに近づかない。
• ウィルスなどの被害にあったら、即ネットワーク切断。
  • 別パソコンでウィルス情報や対策ソフトを仕入れて書き込み禁止USBで。
  • 放置すれば、Botで被害拡大の手助けとなる。