ホーム » スタッフ » 斉藤徹 » 講義録 (ページ 4)

「講義録」カテゴリーアーカイブ

2024年5月
日 月 火 水 木 金 土
 1234
567891011
12131415161718
19202122232425
262728293031  

リンク集

検索・リンク

Google Office 365

ハッシュ法

2023年12月18日

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか？

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

// メモリ無駄遣いな超高速方法
struct PhoneName {
   int  phone ;
   char name[ 20 ] ;
} ;

// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?

// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
   table[ phone ].phone = phone ;
   strcpy( table[ phone ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   return table[ phone ].name ;
}

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

// ハッシュ衝突を考えないハッシュ法

#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;

// ハッシュ関数
int hash_func( int phone ) {
   return phone % HASH_SIZE ;
}

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   return table[ idx ].name ;
}

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムとは言えない。このことから、ハッシュ関数には以下のような特徴が必要となる。

  • 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
  • 簡単な計算で求まること。
  • 同じデータに対し常に、同じハッシュ値が求まること。

ここで改めて、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いのだろうか？

ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか？

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 )
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故？
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ;
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 ) {
      if ( table[ idx ].phone == phone )
         return table[ idx ].name ;
      idx = (idx + 1) % HASH_SIZE ; // ひとつ後ろの席
   }                                // idx++ でないのは何故？
   return NULL ; // 見つからなかった
}

注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum + s[i] ;
   }
   return sum % SIZE ;
}

文字列順で異なる値となるように

前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum*2 + s[i] ;
      // sum = (sum * 小さい素数 + s[i]) % 大きい素数 ;
   }
   return sum % SIZE ;
}

理解度確認

毎年、冬休み期間中の自主的な理解度確認として、CBT を用いた理解度確認を行っています。今年も実施しますので、下記のシステムにログインし情報構造論では「ソフトウェア」(50分) を受講して下さい。

  • https://cbt.kosen-ac.jp/
  • 認証には、MS-365 のアカウントとパスワードでログインしてください。

ポート番号とファイアウォールとメール

2023年12月13日

ポート番号

サーバとなるコンピュータでは、1台のコンピュータで様々なサービスを提供することから、サービスを区別する必要がある。このためにポート番号が使われる。1台毎のコンピュータに割り当てられたIPアドレスを電話番号に例えるなら、ポート番号は内線電話番号に例えることができる。

サーバと通信する場合、サービスを提供するプログラムに応じて標準的なポート番号が決められている。サーバに届いたパケットは、ポート番号に応じてサービスプログラムを起動する。以下の表によく使われるポート番号の一例をあげる。

ポート番号 プロトコル 概要
20 ftp ファイル転送(データ)
21 ftp ファイル転送(命令)
22 ssh リモート接続(暗号対策あり)
23 telnet リモート接続(暗号化なし)
25 smtp 電子メール送信
465 smtps 電子メール送信(暗号化)
53 DNS ドメインネームサービス
80 http Web
443 https Web(暗号化)
110 pop3 メールダウンロード
995 pop3s メールダウンロード(暗号化)
143 imap メール閲覧
993 imaps メール閲覧(暗号化)
137,138,139 netbios Windows のファイル共有

 

通信パケットには、送信元IPアドレス、送信元ポート番号、送信先IPアドレス、送信先ポート番号の情報がある。
パソコンがサーバと通信する場合は、(1)自分のIPアドレスを送信元IPアドレス、(2)その時に使われていないポート番号をランダムに選び、送信元ポート番号とする。(3)通信相手のIPアドレスと、(4)通信先のサービスのポート番号をセットして、パケットを送付する。サーバは、サービスを要求してきたクライアントの送信先ポート番号をみて、対応するサーバのプログラムが動作する。プログラムの結果を送り返す時は、送信元と送信先のIPアドレス、ポート番号を入替えてパケットを送信する。

1024未満のポート番号(ウェルノウンポート番号)は、サービスを受けとるために用途が決められているので、通常の通信プログラムでは使われない。これ以外のポート番号は、通信の送信元のポート番号として使われ、エフェメラルポート番号と呼ばれる。

 

ファイアウォール

ネットワークのサービスの中には、組織外に見せたくないものも多い。また、インターネットでは、悪意のあるプログラマが通信して攻撃を加えてくるかもしれない。基本的には個々のサーバのプログラムで、送信元のプログラムのIPアドレスを見て接続を拒否することもできるが、末端のサーバで設定がいい加減だと攻撃をうけてしまうかもしれない。そこで、組織全体でネットワークを守る必要がでてくる。そこでルータなどの機能で、パケットの送信相手のポート番号や、送信元のIPアドレスをみて、パケットを廃棄する場合がある。こういう、ネットワークからの攻撃を防ぐ装置は、ファイアウォール(防火壁)と呼ばれる。

データベースサーバの保護するためにファイアウォールを設置する例を示す。Webサービスを提供するためのデータベースだけど、インターネットから接続されると情報漏洩が発生するかもしれない。そこでデータベースサーバ(mysql)に接続するための3306ポートは、ファイアウォール(ルータ)で組織外からは接続させない。

許可リスト方式と拒否リスト方式

ファイアウォールの設定では、信頼できる人だけを接続させる許可リスト方式と、怪しい人を除外する拒否リスト方式がある。

許可リスト方式は、接続していい相手のIPアドレスや、ポート番号だけをFireWallを通過させる方式。以前はホワイトリスト方式と呼ぶことが多かった。これとは逆に、攻撃をしてきそうな怪しいIPアドレスや、怪しいポート番号のパケットを捨てて接続させない方式は拒否リスト方式とよぶ。以前はブラックリスト方式と呼ぶことが多かった。学校のサーバは、学内への攻撃を防ぐため、ポート番号については http, https など以外の受信は許可リスト方式となっている。

メールが届くまで

電子メールは、非常に迅速にメッセージを相手に届けることができ、そのメッセージを蓄積・加工・編集・転送できる。また、音声や画像といった情報も、複雑な文字情報に置き換えることで、転送できるようになっている。

メールは、利用者のコンピュータに直接届けられるわけではなく、多くの場合はメールを蓄積するメールサーバに送られる。利用者がメールを読む場合、メールサーバから自分の端末に蓄積されたメッセージを読み込み、メッセージを確認する。このメールのやり取りにおいて、メールを送る時、あるいはメールサーバ間でメールを中継するときには、SMTP(Simple Mail Transfer Protocol) が用いられる。一方、メールサーバからメール
を読み出すときには、POP(Post Office Protocol) やIMAP(Internet Message Access Protocol) と呼ばれるプロトコルが用いられる。最近では、IMAPを使ったメールの読み書きをブラウザの中で実行できる WebMail が使われることが増えている。

メールが届くまでの流れは、aさんが”foo@bar.jp“に送る場合、

  1. aさんは、自分の組織のメールサーバに、SMTPでメールを送る。
  2. メールサーバは、メールアドレスのコンピュータ名部分”bar.jp“をDNSに問合せ、そのIPアドレスを調べ、そのコンピュータにSMTPでメールを送る。※
  3. “bar.jp“のメールサーバは、メールアドレスのユーザ名”foo“を取り出し、各ユーザ毎にメールを保存する。
  4. “foo”さんは、自分宛のメールを確認するために、POPまたはIMAPで自分のメールサーバ”bar.jp”に接続し、ユーザ名,パスワードで認証して自分宛のメールを受け取る。

※上記の手順２で、相手のメールサーバに直接送れない場合は、コンピュータ名のMXレコードをDNSに問合せを行い、そこで得られたメールサーバに中継を依頼する。

$ nslookup -query=MX fukui-nct.ac.jp.
Non-authoritative answer:
fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com.jp

上記手順4で自分のメールを読みだす際のプロトコルで、POPは一般的に、メールサーバから自分のメール閲覧ソフトに自分宛のメールをダウンロードして削除する。このため、様々なコンピュータでメールを読む人には不便となってきた。IMAPでは、メールを読んでも、既読の目印をつけサーバに残しておく方式であり、別のコンピュータでメールを閲覧したい時にもサーバ上のメールを読むことができる。メールをフォルダに分類して保存することもできる。最近利用される Webメール では、自分が利用しているメールサーバまでは Web の機能で接続し、Webサーバとメールサーバにて IMAP を使う。

通常、SMTPでメールを送る際には、ユーザ認証が行われない。このため、ウィルスに感染したプログラムから迷惑メール(spam)を出すことに利用されることが多い。そこで、SMTP送信の前にPOP/IMAP接続しユーザ認証を行った時だけメールを送ることができる、POP before SMTP(or IMAP before SMTP)といった方式をとる場合も多い。

POP, IMAP, SMTPでは、暗号化されない平文が使われることから、通信内容を暗号化して通信する POPS, IMAPS, SMTPS といったプロトコルも使用される。

理解度確認

コンパイラと正規表現とBNF記法

2023年12月11日

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

  • インタプリタ(interpreter:通訳)
    • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
  • コンパイラ(compiler:翻訳)
    • ソースプログラムから機械語を生成し、実行する際には機械語を実行
  • トランスコンパイラ
    • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
      最初のC++の実装(Cfront)では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
  • バイトコードインタプリタ
    • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
  • エミュレーター
    • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
      近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。

      • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

C言語で機械語が生成されるまで

C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。

foo.c C言語のソース
↓     プリプロセッサ処理                cpp
foo.c(#行の無いC言語のソース)
↓     コンパイラ                       gcc
foo.obj(オブジェクトファイル/中間コード)  unix系では foo.o
↓
(+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの)
↓     リンカ(リンケージエディタ)          ld
foo.exe

コンパイラの処理

コンパイラが命令を処理する際には、以下の処理が行われる。

  1. 字句解析(lexical analysys)
    文字列を言語要素(token)に分解
  2. 構文解析(syntax analysys)
    tokenの並び順に意味を反映した構造を生成
  3. 意味解析(semantics analysys)
    命令に合わせた中間コードを生成
  4. 最適化(code optimization)
    中間コードを変形して効率よいプログラムに変換
  5. コード生成(code generation)
    実際の命令コード(オブジェクトファイル)として出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
　↓       Java コンパイラ
foo.class (中間コード)
　↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

字句解析でトークンを表現するために、規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言　　　  「abd|acd」は、abd または acd にマッチする。
グループ化　「a(b|c)d」は、真ん中の c|b をグループ化
量化　　　　パターンの後ろに、繰り返し何回を指定
　　　　　　? 直前パターンが0個か1個
　　　　　　　「colou?r」
　　　　　　* 直前パターンが0個以上繰り返す
　　　　　　　「go*gle」は、ggle,gogle,google
　　　　　　+ 直前パターンが1個以上繰り返す
　　　　　　　「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
　　　　　　「[0-9]+」012,31415,...数字の列
^　　　　　行頭にマッチ
$　　　　　行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

構文とバッカス記法

言語の文法(構文)を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>    【要注意】わざと間違っている部分あり
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

理解度確認

  • インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
  • 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
  • ソースプログラムがコンパイラにより機械語が生成されるまでの処理について説明せよ。

ドメイン名とDNS

2023年12月7日

ドメイン名とDNS

インターネットでの通信では、IPプロトコルでコンピュータを指定するが、IPアドレスは無機質で覚えるのが大変であり、コンピュータに名前をつけて利用する。この際に、コンピュータの所属などが分かるようにしたものをドメイン名と呼ぶ。

例えば、電子情報工学科のドメイン名 www.ei.fukui-nct.ac.jp は、ピリオド部分で区切られ、以下のような意味を持つ。

  • .jp – 国ドメイン(.uk イギリス,.ch 中国,アメリカは無し)
  • .ac – 種別ドメイン(.co.jp,.com:会社,.ne.jp,net:ネットワーク系)
  • fukui-nct – 組織ドメイン
  • .ei. – サブドメイン(組織内が細分化されている場合)
  • www. – ホスト名※

このような省略されていない、対象となるコンピュータを指定するためのドメイン名は、FQDN(Fully Qualified Domain Name)と呼ばれる。FQDNでの名前を ホスト名※ と呼ぶことも多い。

ただしアメリカでは、国ドメインを一般的に使わない※。また最近では、世界的な企業では国ドメインが意味をなさないので、アメリカ以外でも .com や .net といった、汎用トップレベルドメイン(gTLD)が使われる。様々なサービスを展開している企業では、組織種別が意味をなさないため、toyota.jp といった種別ドメインがないドメイン名も増えてきた。高専機構のドメイン名 kosen-ac.jp も、”kosen-ac” が高専機構の組織ドメイン名なので注意。

以下に、主要な組織ドメイン・国ドメインをあげる。

国ドメイン 国名
.jp 日本
.us アメリカ※
.uk イギリス
.fr フランス
.de ドイツ
.cn 中国
.to トンガ
.tv ツバル
.gl グリーンランド
種別ドメイン(日本) 種別ドメイン 国名
.ac.jp .edu 教育機関
.go.jp .gov 政府機関
.co.jp .com ※ 企業
.ne.jp .net ※ ネットワーク組織
.or.jp .org ※ 公益法人
— .biz ※ ビジネス用途
— .info ※ 情報関係用途
— .name ※ 名前

※はgTLD

 

DNSのしくみ

DNSは、Domain Name Service であり、コンピュータ名(ドメイン名)から、IPアドレスを調べるサービスで、ポート番号53,UDPを使っている。

インターネットに接続する際には、最も身近なDNS※の情報が与えられ、ユーザがコンピュータ名を問い合わせると、身近なDNSがコンピュータのIPアドレスを返してくれる。この際に、検索結果はキャッシュとして一定期間保存される。身近なDNSがそのコンピュータ名を知らない場合は、上位のDNSに問い合わせを行い、DNSルートサーバもコンピュータ名をキャッシュしていない場合は、管理元の組織のDNSに問い合わせが行われる。このようにすることで特定のDNSサーバに問い合わせが集中しないようになっている(負荷分散)。 DNSサーバの情報は DHCP サーバからIPアドレスなどと一緒に取得することができる。


DNSと正引きと逆引き

DNSの使い方としては、一般的な使い方は、ドメイン名からIPアドレスを調べる正引きが多い。ブラウザは http://www.fukui-nct.ac.jp/ というURLが与えられたら、DNSに www.fukui-nct.ac.jp を問い合わせ、104.215.53.205 の結果が得られることで、http://104.215.53.205/ のコンピュータに接続を試みる。

これとは逆に、サーバ側では接続してきた相手のコンピュータが信頼できる相手か調べたい時がある。この時には IPアドレスからドメイン名を調べる逆引きを行う。これにより、IP アドレスをきちんと管理している組織であれば、ドメイン名が分かるのでどの組織から接続されているのか確認ができる。

DNSの情報を調べるためのコマンドは、nslookup を用いる。(詳細は以前の講義資料で確認)

DNSと様々な情報

DNS では、様々な情報が取得できる。IPアドレス以外にも、メールを送ってもらうサーバのIPアドレス(MXレコード)なども取得できる。

((( 正引きの例 )))
$ nslookup www.google.com
Server:         172.31.208.1
Address:        172.31.208.1#53

Non-authoritative answer:
Name:   www.google.com
Address: 142.250.206.228                                          # 調べる度に異なる値が返ってくるかも
Name:   www.google.com
Address: 2404:6800:400a:804::2004

((( 逆引きの例 )))
$ nslookup 142.250.206.228
228.206.250.142.in-addr.arpa    name = kix06s10-in-f4.1e100.net.  # 正引きと逆引きが一致していない例

Authoritative answers can be found from:

((( MX レコードを調べる例 )))
$ nslookup -query=MX fukui-nct.ac.jp   # MXレコード = そのドメイン宛のメールはどのコンピュータに送ればいい？
Non-authoritative answer:
fukui-nct.ac.jp mail exchanger = 10 fukuinct-ac-jp01c.mail.protection.outlook.com.

((( AAAA レコードを調べる例 )))
$ nslookup -query=AAAA www.google.com  # AAAAレコード = IPv6アドレスを指定した正引き
Non-authoritative answer:
Name:   www.google.com
Address: 2404:6800:400a:813::2004

DNSとセキュリティ

DNSは、コンピュータ名とIPアドレスを対応付けるものであり、これには正引き(コンピュータ名からIPアドレスを求める)と、逆引き(IPアドレスからコンピュータ名を求める)がある。セキュリティ対策が厳しい場所では、

  • 正引きを使うことで、特定の組織のドメイン名を持つコンピュータからのアクセスを許可/禁止する。(例:国ドメイン.xxからは接続拒否)
  • 正引きで、コンピュータ名が登録されている所からのみ許可する。(例:組織ドメイン.fukui-nct.ac.jpからは接続許可)
  • IPアドレスから逆引きして求めたコンピュータ名をさらに正引きして同じIPアドレスが求まるかを確認

といった対策を行う。

  • DNSのドメイン名は、当初は最初に申請した人に割り当てられる。このため、nintendo.com といったドメイン名を、関係ない人が取得するといったトラブルがあった。(サイバースクワッティング)
  • DNSを用いたクラッキングでは、ウィルスに感染させたパソコンに偽物のIPアドレスを教えることで、偽装した別コンピュータに誘導し個人情報を盗む手口がある。(DNSポイズニング)
  • 他にもウィルスに感染させた大量のパソコンから、同時にルートサーバに大量のDNSの問合せを送ることで、処理能力を低下させると、インターネット全体でDNS参照ができなくなる攻撃もある。(DNSルートサーバへの分散DoSアタック)
  • DNSは、他のコンピュータに接続するための重要な情報だが、独裁国家などでは国にとって不都合な情報が得られるドメイン名のIPアドレスを改ざんしアクセスできないようにすることもある。このため、Google 社では 覚えやすい 8.8.8.8 という IPアドレスの DNS サーバを提供している。この 8.8.8.8 は、DNS の返答速度も速いことから、ブラウザの表示速度を高速化するために自分のPCに設定する人も多い。

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

2023年11月21日

昨年度までの試験問題を例に解説を行い、その後、データベースの設計において、重要な正規形についての説明の導入。

正規形

データベースにおいて、様々な不整合を防ぐために正しい設計が必要であることを 改めて説明し、それには正規形としての条件を満たしている必要があることを説明する。一般的に不整合が発生しないためには、以下の第1正規形、第2正規形、第3正規形を満たすように表を分ければよい。

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

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

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

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

第1正規化 第2正規化

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

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

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

  • 推移従属性とは、データ項目でA→B→Cと、次々と値が求められる関係を指す。

第三正規形とは、 候補キー以外の非キーデータ項目は、候補キーに完全従属し、 かつどの候補キーにも推移従属しない関係をいう。

第3正規化

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

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

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

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

2023年11月20日

前回の授業で説明が不足していた DHCP についての説明

DHCP

前回の IP では、異なるサブネットを繋ぐ役割としての Internet Protocol (IP) について説明をした。IP での通信では、IPアドレスが必要だが、正しく接続ができるためには、(1)IPアドレス、(2)サブネットマスク、(3)ゲートウェイアドレス が必要となる。しかし、この情報は初心者には設定が難しいし、IPアドレスが他の利用者と重複させないためには、きちんとした管理が必要となる。

この時に使われるのが DHCP(Dynamic Host Configuration Protocol) であり、通常のパソコンは、IPの自動設定としておけば、DHCP を用いて前述の(1),(2),(3) の情報が自動で設定される。DHCP機能は、一般的にルータや WiFi の AP(アクセスポイント)の中に組み込まれている。

DHCPサーバには、使用可能なIPアドレスを登録しておく。利用者が DHCP クライアントとして接続する際には、ブロードキャストパケットを使い、同じサブネット内に DHCP リクエストを送る。このリクエストを DHCPサーバが受信したら、サーバはクライアントに向かって、貸し出し用の IP アドレスの１つをクライアントに提供する(サブネットマスクやゲートウェイなども提供)。

データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。またTCPの通信の欠点を補うUDPがある。この授業では、TCPとUDPによるトランスポート層の説明を行う。

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番号(シーケンス番号/32bit)とACK番号(アクノリッジ番号/32bit)という情報がついており、送信元はACK番号を確認することで、どのパケットが正しく届いたのかを認識できる。3wayハンドシェーク時には、相手のSEQ番号に1を加えたACK番号をつけてパケットを返送することで通信が始められることが確認できる。実際のデータを送信する際には、受け取ったデータ長をSEQ番号に加えた値を、ACK番号にして受信に成功したことを相手に伝える。これにより、小分けにされたパケットで次に何を送れば良いのか判別できる。
(Acknowledge = 承認する)

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

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

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

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

TCP FINパケット

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

UDP

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

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

UDP通信は返信を待つ必要がないので、動画・音声配信などのリアルタイム性が求められる通信でよく使われる。UDPは正しく通信ができずパケットが途絶えても、一時的に動画が止まるなり音声が止まるといったように、問題が少ないような場合に有用となる。

ICMP/ping

IPプロトコルのプロトコルの１つとして ICMP (Internet Control Message Protocol) がある。このプロトコルは、ネットワーク機器(ノード)の間で、通信の確認をするためのもので、ping コマンドや traceroute コマンドで使われる。

基本的に、ICMPパケットを相手コンピュータに送り、返事が返ってくるかを確認する。ping や traceroute は、返事が返ってくるまでの時間や、パケットをいくつ送っていくつ返ってきた…などの情報を表示することができ、相手コンピュータまでの通信路が正常かどうかが判断できる。

$ ping www.google.co.jp
PING www.google.co.jp (172.217.25.163) 56(84) バイトのデータ
64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=1 ttl=115 時間=7.85ミリ秒
64 バイト応答 送信元 syd09s13-in-f3.1e100.net (172.217.25.163): icmp_seq=2 ttl=115 時間=8.02ミリ秒
^C   # 途中で強制終了させるために Ctrl-C で止める
]$ traceroute www.google.co.jp
traceroute to www.google.co.jp (172.217.25.163), 30 hops max, 60 byte packets
 1  airstation.ei.fukui-nct.ac.jp (192.168.2.1)  0.355 ms  0.529 ms  0.549 ms
(略)
 9  108.170.243.33 (108.170.243.33)  8.245 ms 108.170.243.65 (108.170.243.65)  6.893 ms  6.936 ms
10  72.14.239.25 (72.14.239.25)  6.899 ms  7.125 ms 72.14.238.23 (72.14.238.23)  7.140 ms
11  syd09s13-in-f163.1e100.net (172.217.25.163)  7.014 ms  7.007 ms  6.961 ms

トランスポート層

OSI参照モデルでは、TCPプロトコルとUDPプロトコルをあわせてトランスポート層と呼び、TCP+UDPとネットワーク層のIPプロトコルでの通信が、今日のインターネット通信の基本プロトコルとなっており、総称して TCP/IPとかインターネット・プロトコル・スイート と呼ぶ。(suite=”一連のものや一緒に機能するものの集まり”/sweetじゃない)

2分木による構文木とデータベースとB木

2023年11月20日

コンパイラの処理の流れ

構文の構造を表すために、2分木を使うという話をこの後に行うが、その前にコンパイラが機械語を生成するまでの処理の流れについて説明をする。

Cコンパイラのソース
　　↓
プリプロセッサ (#define,#includeなどの処理)
　　↓
コンパイラ
・字句解析(ソースコードをトークンに切り分ける)
・構文解析(トークンから構文木を生成)
・最適化(命令を効率よく動かすために命令を早い命令に書き換え)
・コード生成(構文木から中間コードを生成)
　　|
　　|　リンカでライブラリと結合
　（+）←---ライブラリ
　　↓ 
　機械語

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝が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 ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      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 ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) ,
                        tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • 上記プログラム中の(A)～(F)の型を答えよ。

2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。

B木の構造

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

B木からデータの検索

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

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の例 2つの表の串刺し))
-- 60点以上の学生名,科目名,点数を出力 --
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++ )                   // 結合(from)
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択(where)
           && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影(select)
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

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

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。下図で示すB+木では、青で示す検索用のB木の部分と、赤で示す順次処理を行うためのシーケンスセットの部分から構成される。

ネットワーク層とIPアドレス

2023年11月16日

前回説明したMACアドレスによるデータリンク層では、１つのサブネットの中で指定した相手にデータを送ることはできる。しかし、データリンク層だけでは、他のサブネットにいる相手にデータを送ることができない。(相手の名前を知っていても、住所を知らなければ郵便は送れない。)

ネットワーク層とIPアドレス(IPv4)

サブネットに分割し、隣接するサブネット、さらには上流のインターネットと通信をするためには、IPアドレスを用いた通信が行われる。

ネットワークに接続する機器には、それぞれユニークな32bitの番号(IPv4アドレス)を割り振る。

コンピュータへのIPアドレスの設定には、(a)IPアドレス,(b)サブネットマスク,(c)ゲートウェイの情報が必要となる。

  • IPアドレス: 192.156.145.100 といった、0～255の8bitの値をピリオド区切りで4つ並べて表記するのが一般的。
  • サブネットマスク: 255.255.255.0 といった値で、IPアドレスを2進数で書き並べた32bitと、サブネットマスクの32bitで、2進数の論理積をとった値は、ネットワーク番号と呼ばれ、機器が存在する場所を表す。
    また、IPアドレスとサブネットマスクの否定と論理積をとった値は、ホスト番号と呼ばれる。
    サブネットマスクは、先行する1のbit数で書き表すことも多い。255.255.255.0は、”/24″のように書く。
  • ゲートウェイ: 自分自身のネットワーク番号と通信相手のネットワーク番号が異なる場合は、異なるサブネットにいるので、パケットを中継してもらう機器(ルータ,ゲートウェイ)にパケットを送る。

  • IPアドレスとクラス: IPアドレスは、先頭8bit をネットワーク番号とするクラスA,16bitのクラスB,24bitのクラスCに分類されている。以前は、IPアドレスを割り当てる企業規模に応じて、大規模な大学だからクラスA、中規模ならクラスB(福井大学は133.7.0.0/16 ←このような書き方はCIDR記法という)、小規模ならクラスCを割り当てていた。(福井高専はCクラスを5本192.156.145～149.0/24 : 福井高専のIPアドレスでは3つのCIDR記法で表現できる。 192.156.145.0/24,　192.156.146.0/23, 192.156.148.0/23)
    しかし、最近では IPv4 アドレスの不足から、大きな組織に割り振られた クラスA を再分配しているため、先頭が0～126で始まるアドレスでも大きなネットワーク組織とは限らない。

ユニキャスト、マルチキャスト、ブロードキャスト通信

通信では、機器が1対1でデータを送る(ユニキャスト通信)だけでなく、複数の機器に同時にデータを送りたいこともある。

同じサブネット内の全てにデータを送る時には、ブロードキャスト通信が用いられる。この際には、IPアドレスのサブネットにおけるホスト番号部分が全て1のアドレスを使う。Cクラスの 192.168.11.x/24 のネットワークであれば、192.168.11.255 がブロードキャスト通信用のアドレスとなる。一般的にホスト番号部分が全て0のアドレスは、サブネット全体を表すために使われることから、192.168.11.0 のIPアドレスも通常の通信には使えない。このため、Cクラス(サブネットマスク24bit)であれば、256台-2台(全て0と全て1のホスト番号)を引いた254台の機器が設置できる。(実際には、他のネットワークに接続するためのゲートウェイアドレスも必要なので 253台)

動画などの配信では、ユニキャスト通信が使われると、サーバから通信相手までのルータまでに同じデータが送られてくる。こういった方式では大量の視聴者がいる場合、ネットワークの帯域が埋まってしまい、効率の良い配信ができない。同じデータを同じタイミングで複数の機器に配信したい場合はマルチキャスト通信を使う。IPv4では 224.0.0.0/4 を使う。

ARP(IPアドレスとMACアドレスの橋渡し)

同じサブネットの中では、データリンク層でMACアドレスを用いて通信相手を指定するが、ネットワーク層ではIPアドレスを用いて通信相手を指定する。この違いを埋めるためのプロトコルがARPである。

サブネット内に相手先IPアドレスの指定されたパケット(10.10.22.102)が届くと、通信機器はサブネット内の全ての機器相手に ARPリクエストを送信する。(10.10.22.102はいますか？ブロードキャスト通信を使う)

この時、10.10.22.102 のコンピュータは、自分宛てのパケットがあることを知るので、送信元のコンピュータに、自分のMACアドレスを付けたARPリプライを送り返す。(10.10.22.102は、私 “FE:DC:BA:98:76:54” です!)。送信元は、ARP通信をへらすために、その情報を記憶して、2度目以降は覚えたMACアドレスですぐに通信を始める。

ルータとRIP

ルータは、隣接するサブネットの間に入る機器で、各サブネットにゲートウェイとなるインタフェースを持つ。ルータの内部では受け取ったパケットをどこに流すか…という経路情報が重要となる。

  • 静的ルーティング – 末端のルータの設定で、管理者が経路を設定
  • 動的ルーティング – 上流ルータでRIPにより設定

経路設定には2種類あり、(a)末端のルータではこのネットワーク番号はどのルータに送るという情報をルータに直接設定する静的ルーティングがとられる。(b)上流のルータでは、末端のルータの設定が変更されることがあるので、ルータ同士がルーティング情報を送りあう動的ルーティングがとられる。動的ルーティングでは、RIPというプロトコルにより、各サブネットのつながっている経路情報が送られてくる。この経路情報を見て、パケットのIPアドレスを見て、パケットの送り先を判断する。(ネットワークの上流では、複数のネットワーク経路を操る BGP などが使われる)

((Windows の場合))

C:> ipconfig
インタフェース名:
　IPv4アドレス............192.168.xx.xx
　サブネットマスク.........255.255.255.0
　デフォルトゲートウェイ....192.168.xx.1
C:> arp -a
インタフェース:
　192.168.xx.xx     74-03-xx-xx-xx-xx 動的
　192.168.xx.yy     B0-05-xx-xx-xx-xx 動的
C:> netstat -r
ネットワーク宛先 ネットマスク　ゲートウェイ　インタフェース　メトリック
      0.0.0.0        0.0.0.0   192.168.xx.1  192.168.xx.xx 45
 192.168.xx.0  255.255.255.0   ....

((Unix の場合))

$ ifconfig -a             # もしくは ip addr
en1: ....
     inet 192.168.xx.xx netmask 0xffffff00 ...
$ arp -an                 # もしくは ip neigh
.... (192.168.xx.xx) at 74:03:xx:xx:xx:xx ...
.... (192.168.xx.yy) at b0:05:xx:xx:xx:xx ...
$ netstat -rn             # もしくは ip route
Destination  Gateway ...
default      192.168.xx.1  ...
192.168.xx   ...

プライベートアドレス

IPv4 では、32bit でコンピュータを識別することから、最大でも 232台≒40億台(4×103×3台)しか識別できない。実際、IPアドレスの管理団体では、2017年度には IPv4 アドレスは使い切った状態となっている。この対応として、その組織やその家庭内だけで使われる IPアドレス である、プライベートアドレスが用いられる。

  • 10.0.0.0～10.255.255.255 / 8 – 大きな機関向け
  • 172.16.0.0～172.31.255.255 / 12
  • 192.168.0.0～192.168.255.255 /16 – 個人向け

プライベートアドレスを利用する組織では、インターネットに接続するルータでは NAT(もしくはNAPT) という機能を内蔵し、プライベートアドレスとグローバルアドレスの変換を行う。

ローカルループバックアドレス

ネットワーク通信では、1つのコンピュータの中でもプロセスとプロセスの間でデータ通信を行うことも多い。この時に使われるIPアドレスは、ローカルループバックアドレスと呼ばれ、IPv4では 127.0.0.1 のIPアドレスを使う。このアドレスには localhost というドメイン名が割り振られる。

IPv6アドレス

IPv4の32bit の IP アドレスでは、40億台のコンピュータを区別することしかできない。そこで、最近では 128bit の IPv6 アドレスが用いられる(256×102412台≒340×1036台)。 IPv6 では、2004:6800:4004:0826:0000:0000:0000:2003  (www.google.co.jp) といった16進数4桁(16bit)を8個を”:”区切りで書き連ねる書き方をする。ただし16進4桁の先行する0や、全部”0000″ は省略して、”2404:6800:4004:826::2003″ と書く。IPv6 は最近では普及がかなり進んでいるが、途中のルータなどがすべて IPv6 に対応する必要があり IPv4 しか使えない組織も多い。

IPv6でも、同じサブネット内だけで使えるIPv6リンクローカルアドレス(fe80::/10)や、同じ組織内だけで使えるIPv6サイトローカルアドレス(fec0::/10)、ループバックアドレス(::1)などが規定されている。

DNS と nslookup

IPアドレスみたいな数字の羅列は覚えることが難しい。このためコンピュータの名前からIPアドレスを調べるサービスがあり、Domain Name Service(DNS) と呼ばれる。詳しい仕組みは ドメイン名の説明の際に行うが、IP アドレスの調べ方を説明する。

ドメイン名から、IP アドレスを調べるには、nslookup (もしくは dig) を使用する。

$ nslookup www.fukui-nct.ac.jp
:
Non-authoritative answer:
Name:   www.fukui-nct.ac.jp
Address: 104.215.53.205

$ nslookup -query=A www.fukui-nct.ac.jp   # IPv4 アドレスの取得
(同上)                                     # もしくは dig www.fukui-nct.ac.jp A +short

$ nslookup -query=AAAA www.google.co.jp   # IPv6 アドレスの取得
:                                         # もしくは dig www.google.co.jp AAAA +short
Non-authoritative answer:
Name:   www.google.co.jp
Address: 2404:6800:4004:826::2003

理解確認

  • Formsによる理解度確認問題
  • 192.168.11.2/24 のコンピュータから、192.168.1.50にデータを送る場合、どのような処理が行われるか、IPアドレス、サブネットマスク、ゲートウェイ、ネットワーク番号を使って説明せよ。
  • 同じサブネット内で相手のIPアドレスが与えられた時、どのようにパケットが送られるか、MACアドレスとARPを交えて説明せよ。

ERモデル

2023年11月15日

データベースの設計

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

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

ID name grade subject teacher
20101 aoyama 1 database saitoh
20101 aoyama 1 software murata
20002 suzuki 2 database saitoh
20002 suzuki 2 compiler nishi
30203 yamada 3 media ogoshi
× × × internet foobar
  • 修正不整合: 授業担当が saitoh → takaku のように変更になったら、複数のテーブルを修正しなければならない。大量のレコード修正は、時間がかかるし、その途中にシステムダウンしたらデータの整合性に問題が発生するかも。
  • 挿入不整合: 新しい科目 internet を追加したいけど、受講学生が決まらないとデータを挿入できない。
  • 削除不整合: yamada が受講を取りやめたら、科目 media も消えてしまう。

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

■学生(実体)

ID name grade
20101 aoyama 1
20002 suzuki 2
30203 yamada 3
■受講(関係)

ID SubID
20101 1001
20101 1002
20002 1001
20002 1003
30203 1004

30203を消してもmedia
の科目のデータは残る

 ■科目(実体)

SubID Subject teacher
1001 database saitoh
1002 software murata
1003 compiler nishi
1004 media ogoshi
1005 internet foobar

saitoh→takakuに変更したら
複数のレコードを要修正。

internetを追加しても問題なし

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

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

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

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

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

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

意思決定木と演算子

2023年11月13日

データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。

意思決定木

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

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

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。

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 ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

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

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

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

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

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

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

投稿ナビゲーション

← 過去の投稿 新しい投稿 →

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー