ホーム » スタッフ » 斉藤徹

斉藤徹」カテゴリーアーカイブ

2018年12月
« 11月    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

香港のSTEM事情

APIEMSの発表会場近くのショッピングモールで、子供向けのパソコン教材のお店。STEM教材のロボットや、交換パーツまで売ってて驚き。
日本なら大きい電気屋の一角なんだろうけど。
{CAPTION}

{CAPTION}

{CAPTION}

APIEMS 2018 in Hong Kong

12/5-12/8まで香港にて開催されているAPIEMS 2018 にて、12/6に斉藤、12/7に、5EI 小林さん、PS2 前田くん、西先生が発表しました。12/8にPS1 田中さん、PS2 山田くんが、発表し無事に終えることができました。

{CAPTION}

12/6 初日

{CAPTION}

12/7 2日目・午前

{CAPTION}

{CAPTION}

{CAPTION}

12/7 2日目・午後

{CAPTION}

{CAPTION}

12/8 最終日

{CAPTION}

{CAPTION}

情報構造論・後期中間テスト結果の講評

情報構造論のテストが終わり、採点中。今回は、各ページごとに採点中。

  1. 設問1のイメージ図は、ほぼ全員が正解。簡単過ぎたか。
    設問2でprintf(“\n(%d)\n”,i) で、未だに¥と\が同じことを知らないのか!?!?
  2. 設問1の正規表現は、それなりに不正解が多い。
    設問2は、インタプリタ,コンパイラの欠点を述べるとき、「時間がかかる」という表現では「1命令毎に時間がかかる」のか「ソースコードから機械語が生成されてプログラムが動きだすまでの時間がかかる」(ビルド時間)のか不明確なものは、✕とする。
    「コンパイラはエラーが見つけにくい」との回答があったけど、インタプリタは未実行の命令部にバグが残る可能性があるので、どんなエラーのことなのか明記してなければ✕とする。
  3. 採点前
  4. 採点前
  5. 採点前
  6. 採点前

icloud.com メールが届かない

qmail の DNS 512byte パケット問題のパッチをあてたものを使っているつもりだが、また緊急連絡システムのメールQueueが icloud.com 宛のメールで埋まっていた。

そこで、参考記事(icloud.comやme.comやhotmailにメールが届かない時)を参考に以下の設定を行った。

mail.add_x_header

(( /etc/php/7.0/apache/php.ini ))
mail.add_x_header = Off

smtproutes

(( /var/qmail/control/smtproutes ))
icloud.com:     mx1.mail.icloud.com
me.com:         mx1.mail.icloud.com
nifty.com:      smmx.nifty.com
hotmail.com:    mx1.hotmail.com
:

((2018/11/30))
icloud.com の情報を smtproutes に書き込んで、メールが流れるようになったけど、改めて確認したら、me.com 宛が詰まってた。”me.com:mx1.mail.icloud.com”を追加。

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT                             RESULT
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90

((SQLの例))
select STUDENT.name , RESULT.subject , RESULT.point --射影--
   from STUDENT , RESULT                            --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --     --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

Wikipedia B+木 より引用

JavaScriptの再帰の例題

再帰呼び出しで分割統治法の考え方のプログラムをJavaScriptで書いたサンプル

単純に、配列の指定範囲の合計を求める関数を、再帰を用いて記述する。

<html>
<head>
</head>
<body>
 <p>
  このプログラムは、実行結果を console.log() で出力するので、
  Ctrl+Shift+I で、JavaScript の console を表示させてね。
 </p>
 <script type="text/javascript">
   // a : 配列
   // start : 合計を計算する範囲の戦闘
   // end : 合計を計算する範囲の最後+1
   // 配列の合計は、配列の先頭 + 残りの合計
   function array_sum( a , start , end ) {
     console.log( "array_sum:" + start + "," + end ) ;
     if ( start == end ) {
       console.log( "array_sum(" + start + "," + end + ")=0" ) ;
       return 0 ;
     } else {
       var ans = a[ start ] + array_sum( a , start + 1 , end ) ;
       console.log( "array_sum("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   var array = new Array( 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 ) ;
   console.log( array_sum( array , 0 , array.length ) ) ;

   // 配列の合計は、データが1個ならその値。
   // そうでなければ、配列の前半の合計 + 配列の後半の合計
   function array_sum2( a , start , end ) {
     console.log( "array_sum2:" + start + "," + end ) ;
     if ( start + 1 == end ) {
       var ans = a[ start ] ;
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     } else {
       var mid = Math.floor( ( start + end ) / 2 ) ;
       var ans = array_sum2( a , start , mid ) // 配列前半の合計を求める
               + array_sum2( a , mid , end ) ; // 配列後半の合計を求める
       console.log( "array_sum2("+start+","+end+")="+ans ) ;
       return ans ;
     }
   }
   console.log( array_sum2( array , 0 , array.length ) ) ;
  </script>
</body>
</html>

データベースの設計と正規形

適切でないデータベースを例にしながら、更新不整合が発生することを説明する。 (不整合には、修正不整合・挿入不整合・削除不整合がある。) この不整合が発生しないデータベース(表)を作るためには、どうすべきかを解説。

ERモデル

不整合が起こらないようなデータベースとするには、実体関連にモデル化を行う。 実体・関連には、属性(attribute)が付随し、実体を長方形、関連をひし形、属性を楕円で表現する ER図を描く。

学生や教員といった実体は、人という汎化した視点であれば、識別番号と名前の属性で 表現できると意味で、共通である。人を学生という視点で特化した先に、学科名や学年といった 属性を持つと考えられる。こういった汎化階層は、オブジェクト指向と同じ。

実体の中には、他の実体と関連を持って初めて意味を持つ実体もある。 関連先の実体が消えれば、存在自体が無意味になってしまう実体は、弱実体と呼ぶ。

正規形

データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。

第一正規形は、すべての要素が原子値である条件を満たせばいい。 要素の中が複数の項目であったり表形式のデータがあると、 表構造のリレーショナルデータベースにはできない。

キーの説明:超キー(スーパーキー)とは、データベースで1つのデータを 選び出すために必要なデータ項目であり、複数の項目で1データを指定 できる場合もある。

候補キーとは、必要最小限の項目となっているものを指す。 1項目が抜けても選別できなくなるようであれば、候補キーとは言わない。 主キーとは、候補キーのなかで管理の都合上便利なもの。

データ項目の値が決まると、他のデータ項目が自動的に決まるものは、 従属関係があるという。

第1正規化 第2正規化

第二正規形は、部分従属がなく、すべての非キーデータ項目が、候補キーに 完全従属する場合をいう。

完全従属とは、候補キーを構成する全てのデータ項目に、非キーデータ項目が従属していること。 部分従属とは、候補キーを構成するデータ項目の一部のデータ項目に、非キー項目が従属していること。


この例において、単価は商品が決まれば自動的に求まる情報。 (単価が日々変化することはないという条件で…) これは、部分従属となる。

推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。 このなかで、第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。

第3正規化

上記の例では、単価と個数が決まれば、金額が求まる推移従属の関係が含まれている。

おまけ:BC正規形,第4,5正規形

この他にも、 さらに非キーからキーに関数従属性がある場合にそれを取り除く、 ボイスコッド正規形(BC正規化)。 「対称性のある多値従属性(キーを決めると複数データが該当)」を分解して得られる第4正規形や、 「元になるテーブルの結合従属性を維持して分解することにより得られる第5正規形などがある。

トランスポート層・TCPとUDP

サブネット同士をつなぐプロトコルとして、IPプロトコルを紹介したが、データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。

TCP

TCP(Transmission Control Protocol/トランスミッションコントロールプロトコル)では、分割されたパケットを元の順序に組み上げたり、パケットが途中で消えた場合の再送などの処理を行う。この機能により確実に相手に送る機能が実現されている。

3way ハンドシェーク

TCPの通信では、最初に相互に通信が可能かを確認するハンドシェークが行われる。パケットには、SYN,ACK,FINといった種別を表すフラグがついており、SYNは接続確立の要求を表す。ACKは了解を表す。FINは切断要求を表す。通信開始の時には、(1)通信OK?、(2)OKだよ,そっちもOK?、(3)OKだよ! といった3つの通信パケットで確認してから通信を行う。この最初のやり取りを3way ハンドシェークという。

  • SYN flood攻撃 – 3wayハンドシェークは、今後のパケット並び替えの準備も含めるとコストが高い。通信ルールを無視して相手にSYNパケットだけを大量に送ると相手は他の通信が困難になる場合がある。

SEQ番号,ACK番号

また、通信パケットには、SEQ番号ACK番号という情報がついており、3wayハンドシェーク時には、相手のSEQ番号に1を加えたACK番号をつけてパケットを返送する。これにより、どの通信に対する返事か判るようにしている。さらに、実際のデータを送信する際には、受け取ったデータ長をSEQ番号に加えた値を、ACK番号にして受信に成功したことを相手に伝える。これにより、小分けにされたパケットで次に何を送れば良いのか判別できる。

通信で、パケット分割して送って、その一つ毎の返答を待つと、通信の待ち時間が増えてしまう。このため、相手が受け取り可能であれば、一度に前回の2倍のパケットを返信を待たずに送る。(ウィンドウサイズの拡大)

チェックサムとタイムアウト

通信では、送る途中でデータにノイズが混入したり、パケットが消失することがある。このため、パケットにはパケットのチェックサム(バイトデータを加算した値)を付けて送り、受信時に比較してノイズ混入を確認する。こういった際には、パケットが正しく届かない。パケットが消失したりして、通信相手からの返送が届かないで一定の待ち時間が経過することをタイムアウトと呼ぶ。この時、返信パケットにはデータのSEQ番号とACK番号の情報があるため、受け取りに失敗したパケットが判別できるので、送り側は失敗したパケットを再送する。

受け取り側は、同じくSEQ番号やACK番号を元にパケットの順番を正しく並べ戻すことができる。

TCP FINパケット

通信を切断する場合には、相互に切断して良いか確認する4回の通信で終了する。

UDP

TCPによる通信は、相手側からの受け取った返事を待ちながら通信を行う。このため、通信にかかる時間を要する。また、複数の利用者に一斉にデータをばらまくブロードキャスト通信では、個別のパケット欠落を修復しようとすると、処理が複雑になる。

これらの対応策として、UDP(User Datagram Protocol)がある。これは、TCP通信でのパケット分割や再送処理を行わない極めて単純な送信方法である。このため、相手側に正しくデータが送られる保証はない。確実に相手に送る必要があれば、確認や再送は上位プロトコルの責任となる。

UDP通信は、動画・音声配信などのリアルタイム性のある通信で、正しく通信ができず一時的に動画が止まるなり音声が止まっても、問題が少ないような場合に有効となる。

トランスポート層

OSI参照モデルでは、TCPプロトコルとUDPプロトコルをあわせてトランスポート層と呼び、TCP+UDPとIPプロトコルでの通信が、今日のインターネット通信の基本プロトコルとなっており、総称して TCP/IPとかインターネット・プロトコル・スイート と呼ぶ。

データベースの設計とER図

データベースの設計

リレーショナル・データベースでは、データは表形式であればなんでも良い訳ではない。

例えば、学生の成績データが以下のような構造であった場合、

 ID   | name   | grade | subject  | teacher
------+--------+-------+----------+---------
20101 | aoyama |   1   | database | saitoh
20101 | aoyama |   1   | software | murata
20002 | suzuki |   2   | database | saitoh
20002 | suzuki |   2   | compiler | nomura
30203 | yamada |   3   | media    | ogoshi
  • 修正不整合: 授業担当が saitoh → sasaki のように変更になったら、複数のテーブルを修正しなければならない。
  • 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
  • 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。

これらを考慮すると、以下のような3つの表で設計するべきである。

学生                      受講            科目
ID    | name   | grade    ID   | SubID   SubID | subject | teacher
------+--------+-------  ------+-------  ------+----------+--------
20101 | aoyama | 1       20101 | 1001     1001 | database | saitoh → sasaki
20002 | suzuki | 2       20101 | 1002     1002 | software | murata
30203 | yamada | 3       20002 | 1001     1003 | compiler | nomura
                         20002 | 1003     1004 | media    | ogoshi
                  消す→ 30203 | 1004     1005 | internet | foobar → 追加

データベースの設計では、(1)概念設計、(2)論理設計、(3)物理設計が行われる。

  • 概念設計:概念スキーマの決定(実体・関係モデルを使う)。上記の受講データベースの設計例
  • 論理設計:論理スキーマの決定。関係データベースで実装?ほかのデータベース?
  • 物理設計:物理スキーマの決定。データの格納方法や管理方法を決める。

実体関連モデル(ERモデル)

データベース設計では、実体関連モデル(ERモデル:Entity-Relation model)が使われる。 実体とは、モデル化しようとする対象で独立した存在となれるもの。 実体が持つ色々な特性は属性と呼ばれる。 属性の取りうる値の集合を定義域、同一種類の実体の集まりを実体集合と呼ぶ。 関連とは、実体同士の相互関係をモデル化したもの。

実体関連図(ER図)では、実体を長方形、関連をひし形、属性を楕円で表現する。 属性で、キーとなるものには下線をつけて表す。

ER図で調べると、実際にはもっと細かい規定で表現が行われている。 参考:IDEF1X表記とIE表記

演算子と2分木による式の表現


2分木の応用として、式の表現を行うけどその前に…

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         push( *p - '0' ) ;
      } else if ( *p == '+' ) {
         int r = pop() ;
         int l = pop() ;
         push( l + r ) ;
      } else if ( *p == '*' ) {
         int r = pop() ;
         int l = pop() ;
         push( l * r ) ;
      }//~~~~~~~~~~~~~(B)
   }
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で扱うと都合が良い。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして…

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 ) {     // ~~~~~~~~~~~~~~~~~~~~~(C)
      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 ) ;
      }              // ~~~~~~~~~~~~~~~(D)      ~~~~~~~~(E)
}

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

理解度確認

  • 上記プログラム中の(A),(B),(C),(D)の方を答えよ。