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

対称通信路は一様入力を見る

この通信路は0と1が対称で、出力2への確率も両入力で同じである。そのため容量計算では、出力0と1を均等にする入力分布が自然に候補になる。

新記号の混合は二段階エントロピー

$Y$ は「新記号を出すかどうか」というベルヌーイ選択と、出さない場合の $X$ の値に分解できる。ここを直接和で展開すると計算が長くなる。

スターフリーは「禁止部分文字列」で表す

禁止部分文字列を含まない言語は、$\overline{\Sigma^*u\Sigma^*}$ の形にできる。問題文の定義では $\Sigma^*$ を $\overline{\emptyset}$ と見ればよい。

交換操作は2カウンタになる

操作3が入ると順序情報が消え、二つの独立な個数一致条件が残る。この二重一致が文脈自由性を壊す。

ヒープは添字で親を確認する

見た目ではなく、$Parent(i)=\lfloor(i-1)/2\rfloor$ で親を確定してから比較する。0始まりの配列なので、ここを1始まりに読み替えると誤る。

探索距離は等差級数か等比級数か

Algorithm 1 は折り返し距離が線形なので累積距離が二次になる。Algorithm 2 は倍々に伸びるので、直前までの総和が最後の距離と同じオーダーに収まる。

ドントケアを利用する

表に現れない $H$ の入力は、どちらの値を置いても外部出力に影響しない。最簡形ではこのドントケアを積極的に使う。

WB同一サイクル読み出しの意味

WBで書いた値を同じサイクルのIDで読めるため、隣接依存では2個の nop で足りる。3個入れる答案は過大である。