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

定常分布では対称性を先に使う

この問題では、図の形をそのまま連立方程式にするより、1列目と2列目の式が一致することに気づくと短い。特に $p=q$ の後半では $\pi_1=\pi_2$ を最初に置くことで、エントロピーレートの計算が一行になる。

ハフマン符号は一例でよい

同じ確率の語があるため、ハフマン符号は一意ではない。必要なのは、短い符号語が高確率語に割り当てられ、平均符号長が一致していることを示すことである。

操作1は多重集合化

操作1を何度でも使えると、文字列の順序情報は消え、各文字の出現回数だけが残る。この観察で $P_1$ の問題は一気に数え上げ問題になる。

巡回シフトは「切る位置」を探す

$P_2$ では、元の文字列をどこで切るかを探す。$xx^Ryy^R$ の証明は、式変形だけでなく「回転の始点をどこに置くか」を答案に書くことが重要である。

道の数の証明は最後の1辺で分解する

隣接行列の累乗を道の数と読む問題では、「最後の中継点 $k$」で和を取る形に落とすと証明が自然になる。連結性の判定では長さを $n-1$ まで見れば十分である点を書き落とさない。

クイックソートの添字は1始まり

問題文の配列は1始まりで書かれている。実装経験から0始まりで答えると、PARTITION の返り値と再帰範囲がずれるので注意する。

NAND段は積和形に直す

NANDだけの回路は、そのまま追うよりド・モルガンで積和形へ直す方が速い。今回の後段は $\overline{\overline{u_1m}\,\overline{u_4m}}=m(u_1+u_4)$ と読める。

FIFOとLRUの差

FIFOは古く入ったブロックを追い出すため、途中で再利用されたブロックも順番が来れば捨てる。LRUは直近利用を反映するので、このアクセス列では後半の再利用を拾える。