九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2022年度 院試 解答例・解説

加法雑音通信路の見方

第1問は、出力が入力から必ず1ビットだけ反転したベクトルになる、という通信路である。どのビットが反転するかを表す雑音 $Z$ を導入すると、対称な加法雑音通信路になる。対称通信路では一様入力が容量を達成するため、$H(Y)$ の最大値 $k$ から雑音の不確実性 $\log_2 k$ を引けばよい。

エントロピーレートの計算

マルコフ情報源では、現在状態 $i$ が分かっているときの次状態の不確実性を、定常確率 $\pi_i$ で平均する。行列全体のエントロピーを一度に計算しようとするより、各行の分岐だけを見る方がミスが少ない。

ハフマン符号

$(X_1,X_2)$ の確率は $\Pr(X_1=i,X_2=j)=\pi_i P_{ij}$ で求まる。ハフマン符号は同確率の項の結合順に自由度があるため、符号語そのものは一意ではない。重要なのは、確率の高い $(4,4)$ に短い符号を割り当て、接頭語条件と平均符号長を確認することである。

状態対の意味

構成されたオートマトンでは、各入力記号が二つの成分を異なる速度で進める。$0$ は両成分を1ステップずつ、$1$ は第1成分を1ステップ、第2成分を2ステップ進める。この「ステップ数」に言い換えれば、複雑に見える遷移式を単なる剰余計算として処理できる。

部分文字列数の差

$L_2$ で使う事実は、文字列を左から右へ見たとき、$a$ から $b$ への切替回数が $\#_{ab}$、$b$ から $a$ への切替回数が $\#_{ba}$ になることである。切替回数の差は先頭と末尾の組だけで決まるため、有限オートマトンで判定できる。

文脈自由文法の確認

$L_5$ の文法では、$A$ が $a$ と対応する $b$ を作り、$C$ が $c$ と対応する $b$ を作る。連結すると $a^i b^i b^k c^k=a^i b^{i+k}c^k$ となり、条件 $j=i+k$ をちょうど満たす。

再帰処理の不変量

recur\_NumList(alist, newL) では、newL に「すでに見た部分から取り出した数値」を蓄積する、と決めておくと空欄が自然に決まる。先頭がリストなら、そのリストを先に再帰処理してから残りに進む。

自然結合でタプルが増える理由

射影で $\mathrm{Id}$ を落とした $S_2$ は、同姓同名の区別を失う。したがって $\mathrm{Tanaka}$ の行が自然結合時に組合せとして増え、元の $S$ より大きい関係になる。可逆に分解するには、結合キーとして一意に行を識別できる属性を残す必要がある。

関係除算

$R\div T$ は「$T$ に含まれる全ての値に対して、対応する組が $R$ に存在するもの」を返す演算である。全称条件を処理していると考えると、$(R\times S)\div T$ の答えも $R$ の $A1=02$ と $A1=04$ に共通する $A2$ を探す問題に帰着する。

ドントケアを使う理由

部分回路 $F$ の出力 $f$ は直接表で与えられていない。$G_1,G_2$ の表を通して、指定された $X,Y$ を再現できる $f$ を逆算する。入力によっては $f=0$ でも $f=1$ でも同じ $X,Y$ になるため、その入力はドントケアとして簡単化に利用できる。

ストール数の数え方

RAW ハザードは、消費命令の ID が生産命令の WB より前に来ると発生する。この問題では「WB と同じサイクルの ID 読み出しは可能」と明記されているため、消費命令の ID を生産命令の WB と同じサイクルまで遅らせればよい。

性能向上率

サイクル数だけなら $14/12$ 倍だが、拡張でクロック周波数が下がる。実行時間で比較し、$T_{\mathrm{old}}/T_{\mathrm{new}}$ を取ると、周波数低下を含む実効的な速度向上が得られる。