ネットワーク層とIPアドレス
前回の授業でL2スイッチのVLAN機能や、WiFi の話が不十分だったので、前回資料にて補足説明を行う。
説明したMACアドレスによるデータリンク層では、1つのサブネットの中で指定した相手にデータを送ることはできる。しかし、データリンク層だけでは、他のサブネットにいる相手にデータを送ることができない。(相手の名前を知っていても、住所を知らなければ郵便は送れない。)
ネットワーク層と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 を再分配している。
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アドレスを見て、パケットの送り先を判断する。
((Windows の場合))
C:> ipconfig /all インタフェース名: 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 en1: .... inet 192.168.xx.xx netmask 0xffffff00 ... $ arp -an .... (192.168.xx.xx) at 74:03:xx:xx:xx:xx ... .... (192.168.xx.yy) at b0:05:xx:xx:xx:xx ... $ netstat -rn Destination Gateway ... default 192.168.xx.1 ... 192.168.xx ...
プライベートアドレス
IPv4 では、32bit でコンピュータを識別することから、最大でも 232台≒40億台しか識別できない。実際、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) という機能を内蔵し、プライベートアドレスとグローバルアドレスの変換を行う。
IPv6アドレス
IPv4の32bit の IP アドレスでは、40億台のコンピュータを区別することしかできない。そこで、最近では 128bit の IPv6 アドレスが用いられる。IPv6 では、2004:6800:4004:0826:0000:0000:0000:0000:2003 (www.google.co.jp) といった16進数4桁(16bit)を8個を”:”区切りで書き連ねる書き方をする。ただし16進4桁の先行する0や、全部”0000″ は省略して、”2404:6800:4004:826::2003″ と書く。IPv6 は最近では普及がかなり進んでいるが、途中のルータなどがすべて IPv6 に対応する必要があり IPv4 しか使えない組織も多い。
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 アドレスの取得 (同上) $ nslookup -query=AAAA www.google.co.jp # IPv6 アドレスの取得 : Non-authoritative answer: Name: www.google.co.jp Address: 2404:6800:4004:826::2003
理解確認
- Cクラスのサブネットに設置できるコンピュータの台数は何台?
- “172.”で始まるプライベートアドレスでは最大何台?
- 192.168.11.2/24 のコンピュータから、192.168.1.50にデータを送る場合、どのような処理が行われるか、IPアドレス、サブネットマスク、ゲートウェイ、ネットワーク番号を使って説明せよ。
- 同じサブネット内で相手のIPアドレスが与えられた時、どのようにパケットが送られるか、MACアドレスとARPを交えて説明せよ。
SQLの基本
先週の、関係データベースの導入説明を終えて、実際のSQLの説明。
SQLの命令
SQL で使われる命令は、以下のものに分類される。((参考資料))
- データ定義言語 – CREATE, DROP, ALTER 等
- データ操作言語 – INSERT, UPDATE, DELETE, SELECT 等
- データ制御言語 – GRANT, REVOKE 等 (その他トランザクション制御命令など)
データベースは元々商用データの処理に使われることが多かったため、商用計算向けプログラム言語 COBOL と似ている点が多い。COBOL では、計算命令を 英語の文章の様に記述するのが特徴。
一般的な言語 // COBOL A_100 // A-100 変数名にハイフン(マイナス記号)が使える。Aから100を引くという意味ではない。 A = 100 ; // MOVE 100 TO A . A = A + B ; // ADD A B TO A .
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 ユーザ名 オブジェクトへの権限を剥奪する。
ただし、後に示す実験環境では、データベースのシステムにSQLiteを用いている。SQLite はネットワーク対応型のデータベースではないため、データベースをアクセスするユーザや権限の概念が存在せず、これらの命令は実行できても無視される。
create table
実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。
CREATE TABLE テーブル名 ( 要素名1 型 , 要素名2 型 ... ) ; PRIMARY KEY 制約 1つの属性でのキーの場合、型の後ろに"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 ;
理解確認
- キー・プライマリキー・外部キーについて説明せよ。
- 上記説明中の、科目テーブルにふさわしい create table 文を示せ。
- select文における、射影,結合,選択について説明せよ。
SQLの演習環境の使い方
SQL の演習は、Paiza.IO で動作確認をしてください。
SQLの基礎/select文と射影・結合・選択
ここまで述べたようにデータベースでは記録されているデータの読み書きは、SQL で行われ、射影・結合・選択を表す処理で構成されることを示した。SQL の機能を理解するために、同じ処理を C 言語で書いたらどうなるのかを示す。
((( 元のSQL ))) SELECT S.業者番号 -- 必要とされるデータを抽出する射影 -- FROM S -- 複数のテーブルを組合せる結合 -- WHERE S.優良度 >= 20 ; -- 対象となるデータを選び出す選択 -- ((( SQLをC言語で書いたら ))) // 配列の個数を求める #define 文 #define sizeofarray(ARY) (sizeof(ARY) / sizeof(ARY[0])) // C言語なら... S のデータを構造体宣言で書いてみる。 struct Table_S { char 業者番号[ 6 ] ; // 当然、C言語では要素名を char 業者名[ 22 ] ; // 漢字で宣言はできない。 int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; // SELECT...をC言語で書いた場合の命令のイメージ // 結合 for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // 選択 if ( S[i].優良度 >= 20 ) // 射影 printf( "%d¥n" , S[i].業者番号 ) ; }
Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。
SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;
WHERE 節で記述できる条件式では、= , <>(not equal) , < , > , <= , >= の比較演算子が使える。
# これ以外の演算機能は、次週にて紹介予定。
直積と結合処理
ここで、SQLの最も便利な機能は、直積による結合処理。複数の表を組み合わせる処理。単純な表形式の関係データベースで、複雑なデータを表現できる基本機能となっている。
SELECT SG.商品番号 , S.所在 FROM S , SG WHERE SG.業者番号 = S.業者番号
上記の様に FROM 節に複数のテーブルを書くと、それぞれのテーブルの直積(要素の全ての組み合わせ)を生成する処理が行われる。この機能が結合となる。しかし、これだけでは意味がないので、通常は外部キーが一致するレコードでのみ処理を行うように、WHERE SG.業者番号 = S.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。
SELECTの結合処理と処理内容
selectでの選択,結合,射影の処理(select 射影 from 結合 where 選択)を理解するために、同じ処理をC言語で書いたらどうなるかを示す。
// C言語なら struct Table_S { char 業者番号[ 6 ] ; char 業者名[ 22 ] ; int 優良度 ; char 所在[ 16 ] ; } S[] = { { "S1" , "ABC社" , 20 , "福井" } , : } ; struct Table_SG { char 業者番号[ 6 ] ; char 商品番号[ 6 ] ; int 在庫量 ; } = SG[] { { "S1" , "G1" , 300 } , : } ; // FROM S for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM SG for( int j = 0 ; j < sizeofarray( SG ) ; j++ ) { // WHERE S.業者番号 = SG.業者番号 if ( strcmp( S[i].業者番号 , SG[j].業者番号 ) == 0 ) { // SELECT SG.商品番号 , S.所在 printf( "%s %s¥n" , SG[j].商品番号 , S[i].所在 ) ; } } }
(1) i,jの2重forループが、FROM節の結合に相当し、(2) ループ内のif文がWHERE節の選択に相当し、(3) printfの表示内容が射影に相当している。
射影の処理では、データの一部分を抽出することから、1件の抽出レコードが同じになることもある。この際の重複したデータを1つにまとめる場合には、DISTINCT を指定する。
SELECT DISTINCT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ;
上記のプログラムでは、データの検索は単純 for ループで記載しているが、内部で HASH などが使われていると、昇順に処理が行われない場合も多い。出力されるデータの順序を指定したい場合には、ORDER BY … ASC (or DESC) を用いる
SELECT SG.商品番号, S.所在 FROM S, SG WHERE SG.業者番号 = S.業者番号 ORDER BY S.所在 ASC ; -- ASC:昇順 , DESC:降順 --
表型のデータと串刺し
FROM に記載する直積のための結合では、2つ以上のテーブルを指定しても良い。
SELECT S.業者名, G.商品名, SG.在庫量 FROM S, G, SG WHERE S.業者番号 = SG.業者番号 -- 外部キー業者番号の対応付け -- AND SG.商品番号 = G.商品番号 -- 外部キー商品番号の対応付け -- // 上記の処理をC言語で書いたら struct Table_G { char 商品番号[ 6 ] ; char 商品名[ 22 ] ; char 色[ 4 ] ; int 価格 ; char 所在[ 12 ] ; } = G[] = { { "G1" , "赤鉛筆" , "青" , 120 , "福井" } , : } ; // [結合] S,G,SGのすべての組み合わせ // FROM S -- 結合 for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { // FROM G -- 結合 for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { // FROM SG -- 結合 for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // [選択] 条件でレコードを選び出す // WHERE S.業者番号 = SG.業者番号 // AND SG.商品番号 = G.商品番号 if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 && strcmp( SG[k].商品番号 , G[j].商品番号 ) == 0 ) { // [射影] 使用するフィールドを出力 printf( "%s %s %d\n" , S[i].業者名 , G[j].商品名 , SG[k].在庫量 ) ; } } } }
ここで結合と選択で実行している内容は、外部キーである業者番号を S から探す、商品番号を G から探している。この、外部キー対応しているものを探すという視点で、上記 C 言語のプログラムを書き換えると、以下のように表せる。
// FROM SG for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) { // 外部キー SG.業者番号に対応するものを S から探す for( int i = 0 ; i < sizeofarray( S ) ; i++ ) { if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 ) { // 外部キー SG.商品番号に対応するものを G から探す for( int j = 0 ; j < sizeofarray( G ) ; j++ ) { if ( strcmp(SG[k].商品番号,G[j].商品番号) == 0 ) { printf( "%s %s %d\n" , S[i].業者名,G[j].商品名,SG[k].在庫量 ) ; } } } } }
このような、複数の表の実体と関係を対応付けた検索を、データベースの専門の人は「データを串刺しにする」という言い方をすることも多い。
また、SQL では、このようなイメージの繰り返し処理を、数行で分かりやすく記述できている。このプログラム例では、キーに対応するものを単純 for ループで説明しているが、SQL ではプライマリキーなら、B木やハッシュなどを用いた効率の良い検索が自動的に行われる。このため、SQLを扱う応用プログラマは、SQLの結合の処理方法は通常はあまり考えなくて良い。
Microsoft AutoUpdate Trouble
MacOS で、Office 系を立ち上げると、以下の警告ポップアップがしつこく表示されるようになった。ウィンドウ閉じても数秒後に沸いて出てくるし、OK 押しても同じ。
表示されたメッセージでググると、こちらのページが見つかる。/Library/Application Support/Microsoft の中を探して Microsoft AutoUpdate のフォルダを消せと書いてある。はぁ…
$ cd /Library/Application\ Support/Microsoft/ $ find -name "*AutoUpdate*" -print $ cd MAU2.0 $ sudo rm -rf Microsoft\ AutoUpdate.app
んで、うざい画面は出なくなったけど、当然ながら AutoUpdate が動かなくなったので、Office 365 の再インストール。Office系はすでにインストールをしてあるし、新たに AutoUpdate で問題があったので AutoUpdate をインストールするよ…と表示されて、無事復旧。
事の始めは、Microsoft Teams Classic を使ってたら、”新しい Teams” という表示があってインストールしたのが原因かも。ということで、新しい Teams は入れないのが正解かな。
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)
// 2分探索法 int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ; int bin_search( int a[] , int key , int L , int R ) { // Lは、範囲の左端 // Rは、範囲の右端+1 (注意!!) while( R > L ) { int m = (L + R) / 2 ; if ( a[m] == key ) return key ; else if ( a[m] > key ) R = m ; else L = m + 1 ; } return -1 ; // 見つからなかった } void main() { printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ; }
一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか?
2分探索木
ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。
この枝の特徴は何だろうか?この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。
特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。
このデータ構造をプログラムで書いてみよう。
struct Tree { struct Tree* left ; int data ; struct Tree* right ; } ; // 2分木を作る補助関数 struct Tree* tcons( struct Tree* L , int d , struct Tree* R ) { struct Tree* n = (struct Tree*)malloc( sizeof( struct Tree ) ) ; if ( n != NULL ) { /* (A) */ n->left = L ; n->data = d ; n->right = R ; } return n ; } // 2分探索木よりデータを探す int tree_search( struct List* p , int key ) { while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; // 見つからなかった } struct Tree* top = NULL ; void main() { // 木構造をtcons()を使って直接生成 (B) top = tcons( tcons( tcons( NULL , 13 , NULL ) , 27 , tcons( NULL , 38 , NULL ) ) , 42 , tcons( tcons( NULL , 64 , NULL ) , 72 , tcons( NULL , 81 , NULL ) ) ) ; printf( "%d¥n" , tree_search( top , 64 ) ) ; }
この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。
理解度確認
- 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
- 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。
2分木に対する処理
2分探索木に対する簡単な処理を記述してみよう。
// データを探す int search( struct Tree* p , int key ) { // 見つかったらその値、見つからないと-1 while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; } // データを全表示 void print( struct Tree* p ) { if ( p != NULL ) { print( p->left ) ; printf( "%d¥n" , p->data ) ; print( p->right ) ; } } // データ件数を求める int count( struct Tree* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } // データの合計を求める int sum( struct Tree* p ) { if ( p == NULL ) return 0 ; else return p->data + count( p->left ) + count( p->right ) ; } // データの最大値 int max( struct Tree* p ) { while( p->right != NULL ) p = p->right ; return p->data ; }
これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。
2分探索木にデータを追加
前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。
struct Tree* top = NULL ; // 2分探索木にデータを追加する処理 void entry( int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { if ( (*tail)->data == d ) // 同じデータが見つかった break ; else if ( (*tail)->data > d ) tail = &( (*tail)->left ) ; // 左の枝に進む else tail = &( (*tail)->right ) ; // 右の枝に進む } if ( (*tail) == NULL ) *tail = tcons( d , NULL , NULL ) ; } int main() { char buff[ 100 ] ; int x ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( x ) ; return 0 ; }
このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。
理解確認
- 関数entry() の14行目の if 判定を行う理由を説明せよ。
- 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
- sscanf() の返り値を 1 と比較している理由を説明せよ。
- entry() でデータを格納する処理時間のオーダを説明せよ。
ポインタのポインタを使わない挿入
struct Tree* insert( struct Tree* p , int x ) { if ( p == NULL ) p = tcons( NULL , x , NULL ) ; else if ( p->data == x ) ; else if ( p->data > x ) p->left = insert( p->left , x ) ; else p->right = insert( p->right , x ) ; return p ; } int main() { struct Tree* top = NULL ; int x ; while( scanf( "%d" , &x ) == 1 ) { top = insert( top , x ) ; } print( top ) ; return 0 ; }
日本ゲーム大賞2023「U18部門」で2EI福嶋君コラボレーションプラットフォーム賞🏆
一般社団法人コンピュータエンターテインメント協会による、18歳以下の方が開発したゲーム作品を対象に審査、表彰する「U18部門」で、2EI福嶋くんが
コラボレーションプラットフォーム賞(Nintendo Switch プチコン4 SmileBASIC 作品名:CRYPTFACTOR)を受賞🏆しました。
落ちてくる数字に、数を入力すると素因数分解され、1になると撃破….(^_^;
サブネットとWiFiネットワーク
CSMA/CD方式
Ethernet では、1本の線を共有するバス型であり、複数の機器が同時に信号を出力すると、電圧の高低がおかしい状態となる(衝突,コリジョン)ため、同時に信号を出さない工夫が必要となる。ただし、他の人が信号線を使っていないことを確認してから、信号を出せばいいけど、確認から信号を出すまでの遅延により、衝突を避けるのは難しい。
また、1本の線を共有する機器の数が増えてくると、衝突の発生の可能性が高まってくる。
これらの問題を解決するためのルールが CSMA/CD(Carrier Sense Multiple Access with Collision Detection)方式である。
- 機器は、信号を出す場合、信号線が空いている状態を待ち、出力を行う。
- もし、複数の機器が同時に信号を出した場合、電圧異常を検知したら衝突なので再送を試みる。
- 再送を行う場合には、乱数時間待つ。(機器が多い場合は、これでも衝突が起こるかもしれない)
- 乱数時間待っても信号線が空かない場合は、乱数時間の単位時間を倍にする。
どちらにしろ、バス共有する機器の台数が増えてくると、衝突の可能性は高まり、100台を越えるような状態は通信効率も悪くなる。
ただし、最近はスイッチングHUBで通信制御を行うことが一般的になり、CSMA/CD方式ではなくフロー制御が行われる。HUBのフロー制御では、基本的に衝突は起らないが、複数のネットワークケーブルから同時にHUBにデータが送られてくると、処理ができない場合がある。この際には CSMA/CD 方式での JAM 信号を使うことで衝突が発生しているように扱う。
スイッチングHUB
*BASE-T のような、HUB による接続では、複数の機器が異なる機器どうしで通信をする場合、その通信路を時分割多重するのではなく、通信相手に応じて内部回路を直接つながるように接続するスイッチングHUB(以下SW-HUB)が普及している。
ストア&フォワード方式では、フレーム(パケット)を全部読み込んで、宛先情報を確認してからパケットを送り出す方式。しかし、パケットを全部読み込んだ後の転送による遅延が問題となる。カットスルー方式は、フレーム先頭にあるMACアドレス(6byte)を読み込んで宛先が分かったらすぐにフレームを流す方式で遅延が少ない。しかしフレームにエラーが発生していてもそのままフレームを流してしまう欠点がある。この両者の利点を合わせた方式であるフラグメントフリー方式では、衝突を検出するために必要なフレームの先頭64byteを読み込んだ時点でフレームを流す方式。
バス型通信では、1本の線を共有するため、同じネットワーク内の別機器間の通信は、傍受することができる(タッピング)。しかし、SW-HUB の場合、機器同士が直接つながるので、傍受するのが困難であり、セキュリティ的にも望ましい。
SW-HUBでは、ネットワークケーブルがループ状になると、データ転送が無限に繰り返されるようになる(ブロードキャストストーム)ため、ネットワーク全体がダウンする。ブロードキャストフレームとは、新しくネットワークに入った機器が自分のMACアドレスを周囲の機器に伝えるためのパケット。ループが発生するとブロードキャストフレームが無限に繰り返し流れてしまう。
データリンク層とMACアドレス
前述のように、1つのバス型接続のネットワーク内部には、同時に設置できる機器の数には限界がある。このため、小さなネットワークに分割したもの(サブネット)を、ブリッジやルータで接続し、隣接するサブネットにサブネット内の通信情報が出ないように分割することを行う。
Ethernetに接続する機器は、機器ごとにユニークな番号(MACアドレス)を持っている。このMACアドレスは、8bit✕6個の48bitの値で、メーカー毎に割振られた範囲の値を、機器ごとに異なる値がついている。
Windows であれば、コマンドプロンプト(cmd.exe)を開き、ipconfig /allを実行するとMACアドレスを確認できる。
通信は、一般的に1500byte程のパケットを単位として送受信が行われる。サブネット内の通信では、自分宛のパケットかどうかをMACアドレスを見て受け取る。これらのレイヤーは、データリンク層と呼ばれる。
旧式のHUB(Dumb HUB)は、電気的に信号を増幅するだけなので、物理層(レイヤー1)だけで通信を行う。
スイッチングHUBは、MACアドレスを見て通信相手を判断(データリンク層/レイヤー2)する。最近では、SW-HUBのコネクタ毎に、パケットにタグを付加することで、1本のネットワーク経路に仮想的な複数のネットワークを構築するタグV-LANといった方式を使う場合もある。このような機能を持つSW-HUBは特にレイヤ2スイッチとも呼ばれる。
L2スイッチとL3スイッチ
サブネットに分割し、それぞれに異なるネットワーク番号を割り振り、中継するルータで FireWall を機能させることで、セキュリティを高めることが行われる。しかし、性能の高いスイッチングHUBは高価でもあり、1つのHUBに異なるネットワークを接続する必要がでてくることもある。この場合、IPアドレスを異なるネットワークの番号を偽装されると、データが盗み見られるかもしれない。
こういった相互に分離すべきネットワークであっても、柔軟なネットワーク構成とするためには、VLAN機能を持った L2スイッチ(レイヤ2スイッチングHUB) が使われる。タグVLAN機能付きのL2スイッチでは、特定のポートにVLANのタグ番号を割り当て、ポートに入る時にパケットに VLAN のタグ情報を付加し、そのパケットは同じ VLAN のタグをもつポートからしかデータを取り出せない。
L2スイッチ(レイヤ2スイッチ)は、機器のMACアドレスやパケットに付けられたVLANのタグ番号の情報(レイヤ2=データリンク層)でパケットの流れを制御している(下記OSI参照モデルの表を参照)。最近では、許可されていない機器がネットワークに侵入する不正侵入を防ぐために、登録されていないMACアドレスのパケットを通さないといった機能がある。
OSI参照モデルとレイヤ 第7層 アプリケーション層 アプリケーションの種類の規定 第6層 プレゼンテーション層 データフォーマットの交換 第5層 セッション層 コネクションの確立や切断などの管理 第4層 トランスポート層 パケットの分割合成や再送といった管理(TCP) 第3層 ネットワーク層 隣接するネットワーク間の通信(IPアドレス) 第2層 データリンク層 直接接続された機器間の通信(MACアドレス) 第1層 物理層 物理的な接続方法(コネクタや電圧など)
スイッチングHUBの中には、レイヤ3(IPアドレス)の情報でパケットの流れを制御するものもある。こういったスイッチは、L3スイッチ(レイヤ3スイッチ)と呼ばれるが、機能的にはルータと同じである。
一般的には、LANとWANを接続するための機器はルータ、LAN内部のネットワークを分離するためのものはL3スイッチと呼ぶ。
無線LANと暗号化
無線LAN(通称 WiFi)は、IEEE 802.11 にて規格が定められている。無線LANは、使う通信周波数で、2.4GHz帯を使うものと、最近増えてきた5GHz帯のものに分けられる。
- IEEE802.11a 5GHz帯を使う、最大54Mbps
- IEEE802.11b 2.4GHz帯を使う、最大11Mbps
- IEEE802.11g 2.4GHz帯を使う、最大54Mbps
- IEEE802.11n 2.4GHz/5GHzを使う、最大600Mbps
- IEEE802.11ac 5GHz帯を使う、最大6.9GBps
- IEEE802.11ad 60GHz 最大6.8Gbps
- IEEE802.11ax 2.4GHz/5GHz 最大 9.6Gbps
2.4GHz帯は、電子レンジで使う電波の周波数と重なるため、電波干渉を受けやすい。5GHz帯は、障害物の影響を受けやすい。
2.4GHzは様々な家電製品・電子機器で利用されているため、他の機器との干渉を受けやすく速度低下を起しやすいが、遠くまで電波が届きやすい。 5GHzは、この周波数帯を利用している機器が少ない為、干渉を受けにくく安定して通信できるが、あまり遠くには電波が届かず、通信が極端に不安定になる場合がある。
無線LANに接続する場合には、接続先(アクセスポイント)に付けられた名前(SSID)と、SSIDに割り振られたパスワードが必要となる。ただし無線は、電波で信号を飛ばすため、近くに行くだけで通信を傍受できる。このため、データの暗号化が必須となる。この暗号化は、そのアルゴリズムにより解読の困難さが変わる。
- WEP 64bit / 128bit – すでに古い暗号化で専用ソフトを使うとすぐに解読される可能性が高い。使うべきではない。
- WPA/WPA2 – 現時点の主流。
- 暗号化方式 TKIP や 暗号化アルゴリズム AES
無線LANでは、車でセキュリティの甘いアクセスポイント(暗号化無しやWEPを使うAP)を探し、その無線LANを使ってクラッキングなどをおこなう場合も多い。(ウォードライビング)
勝手に無線LANを使われないようにするために一般的には、(1)アクセスポイントに接続できる機器をMACアドレス(機器に割り当てられた48bitの固有値)で制限したり、(2)SSIDのステルス化(APが出す電波にSSIDを入れない方式)を行う場合も多い。ただし、これらの制限をかけても専用の機器を使えば通信は傍受可能。
携帯電話を使っていると、最近では高速大容量通信、多数同時接続、低遅延を特徴とする 5G 回線という言葉が出てくる。ここまでの話から、5G = 5GHz と勘違いするかもしれない。また、5G = 5G bps といった勘違いもあるかもしれないけど、5G = 第5世代移動通信システム(5th Generation) なので注意。
双方向リストとdeque
番兵と双方向循環リスト
前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?
同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?
こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。
しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。
deque(両端キュー)
この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。
理解確認
- 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
- 双方向リストの利点と欠点はなにか?
- 番兵を用いる利点を説明せよ。
- deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
- 双方向リストが使われる処理の例としてどのようなものがあるか?
第34回 高専プロコン 競技部門 優勝🏆
自由部門 敢闘賞 チャリレコ
同じく、自由部門にて本選に参加した 4EI 藤野間くん、中西くん、鈴木くん、山腰くん、治内 杏太、指導教員 小松 先生 のチームによるチャリレコも敢闘賞となりました。
メディア掲載
- 日刊県民福井Web 2023/10/16※
- 福井新聞 D刊 2023/10/15※
- 日本経済新聞 北陸 2023/10/16※
- 第34回高専プロコン福井で開催 – BCN
- 高専プロコン観戦記「高専就職・転職ガイド」
※は学内のみアクセス可