情報科学⼊⾨（⼤⻄）⼩テスト(2015 年６⽉ 23 ⽇) 所属学籍番号⽒名 1. ｎ通りの値（x1, x2,.., xn）を取りうる離散確率変数 X がある． Pr[ X  x i ]  p i (i  1,2,  , n) として，下記の問に答えよ． (1) 確率変数 X の平均情報量，すなわちエントロピーH(X) の計算式を⽰せ．（７点）答え n H ( X )   pi log 2 pi i 1 (2) H(X)が最⼤となる時の Pr[ X  x i ]  p i (i  1,2,  , n) と，H(X)の最⼤値を⽰せ．（７点）答え 2. P( xi )  1 n (i  1,2, , n) n の時に最⼤となり，最⼤値は H (X )   1 i 1 図のマルコフ情報源について，下記の問に答えよ． 2 1  log 2 n n 0/0.6 1/0.8 1/0.4 (1) 状態遷移確率⾏列Ｐを⽰せ．（5 点）答え  n log S1  0.6 0.4   P    0.2 0.8  S2 0/0.2 (2) 定常状態確率 P(S1), P(S2)を求めよ．解の導出過程を記すこと．（5 点）答え 0.6 P(S1)+ 0.2 P(S2) = P(S1), P(S1) + P(S2) = 1 より P(S1)=1/3, P(S2)=2/3． (3) 情報源エントロピーH(S)を求める数値の⼊った式を⽰せよ．（5 点）答え H(S) = 1/3* H(0.4)+2/3* H(0.2)= 2/3* 0.97+1/3* 0.72=0.89． 3. 次式の⽣起確率を持つ記憶なし情報源 S={a,b,c,d,e}について下記の問に答えよ． P(a) = 0.3 , P(b) = 0.25 , P(c) = 0.16 , P(d) = 0.15 , P(e) = 0.14 (1) ２元ハフマン符号をつくれ．ただし，確率の⼤きい⽅に，"1"を割り当てること．解の導出過程を記すこと．（７点） a:11, b=01, c=00, d=101, e=100 a 0.3 b 0.25 1 c 0.16 d 0.15 1 1 e 0.14 (2) 平均符号⻑ L を求めよ．解の導出過程を記すこと．（5 点）答 4. L=2*(0.3+0.25+0.16)+3*(0.15+0.14)=2*0.71+3*0.29=2.29 ハミング符号があり，その検査ビット c1, c2, c3 は次式で与えられる．下記の問に答えよ． c1  x 2  x3  x 4 , c 2  x1  x 2  x 4 , c3  x1  x3  x 4 (1) この符号のシンドローム s1, s2, s3 を計算する式を⽰せ．（5 点）答え s1  x 2  x3  x 4  c1 , s 2  x1  x 2  x 4  c 2 , s 3  x1  x3  x 4  c3 (2) 受信語（x1 x2 x3 x4 c1 c2 c3）が (1 0 1 1 1 0 0) である時，シンドロームを計算せよ．（5 点）答え s1  0  1  1  1  1, s 2  1  0  1  0  0, s3  1  1  1  0  1 (3) (2)の受信語の誤り箇所を特定し，訂正した符号語を求めよ．（5 点）答え X3 の桁で誤り発⽣．訂正後の符号語は(1 0 0 1 1 0 0)である． 5. 下線部に適当な語句を書き⼊れよ．（各３点で計 24 点） (1) 暗号は，公開鍵暗号と共通鍵暗号とに分類される．後者は，送信者と受信者が同じ鍵を使⽤するので，受信者ごとに鍵を変えなければならない． (2) 公開鍵暗号化では，暗号化の鍵と復号の鍵が異なる．暗号化の鍵は公開される（認証局に登録する）．送信者は受信者の公開鍵を使って，情報を暗号化する．受信者は暗号⽂を復号する．ここで，注意するべきことは「なりすまし」である．これは他⼈の名前をかたって，その⼈の鍵を登録することで，これを防ぐには本⼈確認を厳密にすることが必要である． (3) 公開鍵暗号である RSA は，公開鍵の⼀つである整数 n が⼗分⼤きいため，その素因数分解である p, q を実⽤的な時間で求めることができないため，計算的に安全な暗号である．以上