跳到主要内容

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

标签：

Author​

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

Description​

(1)​

記憶がない情報源 S0={a1,…,as}S_0=\{a_1,\ldots,a_s\} について、aia_i の生起確率を 2−mi2^{-m_i}、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 とする。
    • (1-1-1) 復号木を一つ示せ。
    • (1-1-2) 平均符号語長と、底を2とするエントロピーを求めよ。
  • (1-2) 記号数 ss に関する数学的帰納法で、所要の符号が存在することを示す。
    • (1-2-1) 確率和の偶奇性から ms−1=msm_{s-1}=m_s を示す文章の空欄（あ）〜（お）を埋めよ。
    • (1-2-2) s=2s=2 の場合を示せ。
    • (1-2-3) s−1s-1 記号以下で成立すると仮定し、ss 記号でも成立することを示せ。
  • (1-3) エントロピー、平均符号語長、シャノンの情報源符号化定理に関する空欄を埋め、拡大情報源によってさらに平均符号語長を短くできるか答えよ。

(2)​

同期的な距離ベクトル型ルーティングを考える。初期値は di(j)=c(i,j)d_i(j)=c(i,j) とし、各ステップでノード ii は距離ベクトル DiD_i を隣接ノードへ送り、受信したベクトルで更新する。

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

题目描述​

本题前半通过归纳法证明概率为二的负整数次幂时存在码长恰等于自信息的前缀码；后半考查同步距离向量更新、收敛过程与断链后的count-to-infinity，并与链路状态路由比较。

Kai​

(1)​

(1-1-1)​

一例として

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

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

root
├─0→ a₁
└─1
   ├─0→ a₂
   └─1
      ├─0
      │  ├─0→ a₃
      │  └─1→ a₄
      └─1
         ├─0→ a₅
         └─1→ a₆

(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は生じない。

本页目录