跳到主要内容

大阪大学 情報科学研究科 情報工学 2018年8月実施 ネットワーク

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

(1)​

記憶がない情報源 S={a1,…,as}S=\{a_1,\ldots,a_s\} の記号数は s≥2s\ge2 とする。aia_i の生起確率は 2−mi2^{-m_i} であり、m1,…,msm_1,\ldots,m_s は 1≤m1≤⋯≤ms1\le m_1\le\cdots\le m_s を満たす整数とする。各 aia_i の符号語長が mim_i となる瞬時復号可能な2元符号の存在を考える。

  • (1-1) 特別な場合として、s=6,m1=1,m2=2,m3=m4=m5=m6=4s=6, m_1=1, m_2=2, m_3=m_4=m_5=m_6=4 である情報源 S0S_0 を考える。

    • (1-1-1) 復号木を一つ示せ。
    • (1-1-2) 平均符号語長と、底を2とするエントロピーを求めよ。

  • (1-2) 記号数 ss に関する数学的帰納法で、所要の符号が存在することを示す。

    • (1-2-1) 以下の文章の空欄（あ）〜（お）を埋めて、常に ms−1=msm_{s-1}=m_s であることを示せ。（い）〜（え）には「偶数」または「奇数」を入れよ。

      2ms∑i=1s2−mi=あ2^{m_s}\sum_{i=1}^{s}2^{-m_i}=\boxed{\text{あ}} である。ms≥1m_s\ge1 なので、2ms∑i=1s2−mi2^{m_s}\sum_{i=1}^{s}2^{-m_i} は（い）である。ms−1≠msm_{s-1}\ne m_s と仮定すれば、2ms∑i=1s−12−mi2^{m_s}\sum_{i=1}^{s-1}2^{-m_i} は（う）であり、これらの差 2ms∑i=1s2−mi−2ms∑i=1s−12−mi2^{m_s}\sum_{i=1}^{s}2^{-m_i}-2^{m_s}\sum_{i=1}^{s-1}2^{-m_i} は（え）となるが、差の値は

      2ms∑i=1s2−mi−2ms∑i=1s−12−mi=お2^{m_s}\sum_{i=1}^{s}2^{-m_i}-2^{m_s}\sum_{i=1}^{s-1}2^{-m_i}=\boxed{\text{お}}

      であり矛盾する。

    • (1-2-2) s=2s=2 の場合を示せ。

    • (1-2-3) s−1s-1 記号以下で成立すると仮定し、ss 記号でも成立することを示せ。

  • (1-3) 次の文章の空欄を埋めよ。（う）には人名の姓、（お）には「がある」または「はない」を入れよ。

    一般の場合に、情報源 SS の2を底とするエントロピーは（あ）である。小問 (1-2) で存在を示した符号化の平均符号語長は（い）であり、（う）の（え）定理から、SS の nn 次拡大に対する符号化を考えた場合に、一記号あたりの平均符号語長がより小さい符号化が存在する可能性（お）。

(2)​

同期的な距離ベクトル型ルーティングを考える。全ノードの集合を N\mathcal N、ノード ii から jj へのリンクコストを c(i,j)≥0c(i,j)\ge0 とする。c(i,i)=0c(i,i)=0 とし、リンクが存在しなければ c(i,j)=∞c(i,j)=\infty とする。di(j)d_i(j) はノード ii が保持する、ii から jj への最小コスト経路のコストである。N={x,y,z}\mathcal N=\{x,y,z\} なら Di=[di(x),di(y),di(z)]D_i=[d_i(x),d_i(y),d_i(z)] と表す。初期値は di(j)=c(i,j)d_i(j)=c(i,j) とし、各ステップで全ノードが同期的に次の動作I、IIを行う。

  • 動作I：各ノード ii は DiD_i を隣接ノードへ送り、自身へ送信された距離ベクトルを受信する。
  • 動作II：受信したすべての距離ベクトルを用いて、自身の DiD_i を更新する。

前ステップと現ステップの間で、すべての DiD_i に変化がなければ経路が収束したという。

  • (2-1) DiD_i の更新式を示せ。
  • (2-2) 次のネットワークで、送信された距離ベクトルは喪失せず届くものとする。初期状態の直後の更新をstep 1として、各ステップにノード xx が受信する Dy,DzD_y,D_z と更新後の DxD_x を、収束するまで示せ。
  • (2-3) 次のネットワークは切断前に収束しており、Dy=[1,0,1]D_y=[1,0,1] である。その後 x−yx-y 間が切断され、c(x,y)=c(y,x)=∞c(x,y)=c(y,x)=\infty となった。リンク切断直後の更新をstep 1とする。距離ベクトルは、切断されたリンクを介しては到着しないものとする。
  • (2-3-1) step 1〜3終了時の dy(x)d_y(x) を示せ。
  • (2-3-2) count-to-infinityが生じる理由を説明せよ。
  • (2-3-3) リンクステート型では同問題が生じない理由を説明せよ。

Kai​

(1)​

(1-1-1)​

一例として

a₁ = 0
a₂ = 10
a₃ = 1100
a₄ = 1101
a₅ = 1110
a₆ = 1111

とする。復号木は次の通りである。

(1-1-2)​

Lˉ=12⋅1+14⋅2+4⋅116⋅4=2.\bar L=\frac12\cdot1+\frac14\cdot2+4\cdot\frac1{16}\cdot4=\boxed{2}.

pi=2−mip_i=2^{-m_i} より

H(S0)=−∑ipilog⁡2pi=∑imi2−mi=2.H(S_0)=-\sum_i p_i\log_2p_i=\sum_i m_i2^{-m_i}=\boxed{2}.

(1-2-1)​

(あ)=2ms,(い)=偶数,(う)=偶数,(え)=偶数,(お)=1.\boxed{(\text{あ})=2^{m_s}},\quad \boxed{(\text{い})=\text{偶数}},\quad \boxed{(\text{う})=\text{偶数}},\quad \boxed{(\text{え})=\text{偶数}},\quad \boxed{(\text{お})=1}.

確率和に 2ms2^{m_s} を掛けると

2ms∑i=1s2−mi=2ms2^{m_s}\sum_{i=1}^{s}2^{-m_i}=2^{m_s}

は偶数である。ms−1≠msm_{s-1}\ne m_s なら i≤s−1i\le s-1 の項の和も偶数だが、残る第 ss 項は 2ms2−ms=12^{m_s}2^{-m_s}=1 となり矛盾する。よって ms−1=msm_{s-1}=m_s である。

(1-2-2)​

s=2s=2 では m1=m2=mm_1=m_2=m であり、2⋅2−m=12\cdot2^{-m}=1 から m=1m=1。a1↦0,a2↦1a_1\mapsto0, a_2\mapsto1 とすればよい。

(1-2-3)​

ms−1=ms=mm_{s-1}=m_s=m とし、as−1,asa_{s-1},a_s を確率

2−m+2−m=2−(m−1)2^{-m}+2^{-m}=2^{-(m-1)}

の一記号 a′a' に併合する。帰納法の仮定により得られる a′a' の符号語を ww とし、as−1↦w0,as↦w1a_{s-1}\mapsto w0, a_s\mapsto w1 に置換すれば、符号語長はともに mm で接頭語条件も保たれる。

(1-3)​

(あ)=∑i=1smi2−mi,(い)=∑i=1smi2−mi,(う)=シャノン,(え)=第一,(お)=はない.\boxed{ (\text{あ})=\sum_{i=1}^{s}m_i2^{-m_i},\quad (\text{い})=\sum_{i=1}^{s}m_i2^{-m_i},\quad (\text{う})=\text{シャノン},\quad (\text{え})=\text{第一},\quad (\text{お})=\text{はない} }.

平均符号語長がエントロピーに等しく下限を達成しているため、拡大情報源でも一記号当たりの平均符号語長をさらに小さくできない。

(2)​

(2-1)​

ノード ii の隣接ノード集合を Γ(i)\Gamma(i) とすると、j≠ij\ne i について

dinew(j)=min⁡k∈Γ(i)(c(i,k)+dk(j)).\boxed{ d_i^{\mathrm{new}}(j)= \min_{k\in\Gamma(i)}\bigl(c(i,k)+d_k(j)\bigr) }.

また dinew(i)=0d_i^{\mathrm{new}}(i)=0 とする。旧値 di(j)d_i(j) を独立な候補として残すのではなく、旧経路を使う場合も、その次ホップが広告した距離を介して評価する。

(2-2)​

初期値は

Dx=[0,2,8],Dy=[2,0,3],Dz=[8,3,0].D_x=[0,2,8],\quad D_y=[2,0,3],\quad D_z=[8,3,0].
ステップxx が受信する DyD_yxx が受信する DzD_z更新後の DxD_x
1[2,0,3][2,0,3][8,3,0][8,3,0][0,2,5][0,2,5]
2[2,0,3][2,0,3][5,3,0][5,3,0][0,2,5][0,2,5]

step 2で変化がなくなり収束する。

(2-3-1)​

切断直前に zz が広告した xx までのコスト2をstep 1で利用するため

step 1step 2step 3dy(x)335\boxed{ \begin{array}{c|ccc} &\text{step 1}&\text{step 2}&\text{step 3}\\ \hline d_y(x)&3&3&5 \end{array}}

となる。

(2-3-2)​

切断後も yy は「zz が xx への経路を持つ」、zz は「yy が xx への経路を持つ」と互いの古い距離情報を採用する。このため広告コストが 3,4,5,…3,4,5,\ldots と増加し続ける。

(2-3-3)​

リンクステート型では、切断情報を全ノードへフラッディングし、各ノードが同じトポロジから最短経路を再計算する。隣接ノードの距離値を互いに経路として信じ続けないため、count-to-infinityは生じない。

本页目录