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

Kraft不等式は構成にも使える

和が1以下なら、2分木の葉として符号語を置ける。例を出すときは、短い語が他の語の接頭辞になっていないことを確認する。

KL最小化は積最大化に直す

一様分布からの $D(u\|q)$ では、$\prod_x q(x)$ を大きくする問題に変形できる。対数の中身を見てから微分すると計算が短い。

末尾条件は接頭辞ではなく接尾辞を見る

この型のDFAでは、読んだ全体ではなく「末尾がどの候補語の接頭辞になっているか」を覚える。状態最小化では同じ未来を持つ状態をまとめる。

往復性は単なる原点復帰ではない

原点へ戻るだけでは足りない。後進ステップが、対応する前進ステップを逆向きにたどることが条件である。

指数時間と対数時間の対比

同じフィボナッチでも、再帰木をそのまま展開すると指数時間、行列累乗を二分すると対数時間になる。計算量の理由まで書くことが重要である。

B木の最大値は子数から数える

深さごとのノード数を $(2d+1)^h$ と見れば、あとは各ノード最大 $2d$ レコードを掛けるだけである。

ゼロの行を見る

1が多い真理値表では、0の行を見て補関数を考えると早い。ただし最終的には積和形で答えるので、カルノー図で1のまとまりへ戻す。

AMATは単位を最後に変換する

まずサイクル数で $1+\text{miss rate}\times\text{penalty}$ を計算し、最後にクロック周期を掛けるとミスが少ない。