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

微分エントロピーの底

底が自然対数の場合、問1(1)は $\ln a$、問1(2)は $\ln a-\ln 2+1/2$ になる。ビット単位の答とは定数倍だけが異なるので、答案では底を明記しておくと安全である。

容量の達成部分

加法的2元通信路では、入力を一様にすると任意の誤り列に対して出力が一様になる。この点を書けば、単に上界を示すだけでなく、$1-H(S_E)$ が実際に達成可能であることまで説明できる。

DFAの状態の意味を明記する

状態遷移図を完全に描く代わりに、状態の意味、初期状態、受理状態、遷移規則を明示すれば、図と同等の情報になる。特に $P_{3,3}$ は同じ報酬が白を取った場合と赤を取った場合の両方から生じるため、残り個数の候補集合を状態にするのが自然である。

補言語の文法

$\{a^i b^i\}$ の補集合は、$a^\ast b^\ast$ の中で個数が合わない文字列と、そもそも $a^\ast b^\ast$ の形でない文字列に分けると作りやすい。規則 $S\to aSb$ は、悪い中心部分を同じ個数の $a,b$ で包んでも、なお補集合に残ることを使っている。

KMPの戻り先

一致を検出した直後に $q$ は $m$ になるが、そのまま表示されるのではなく、次の探索のために $\pi[m-1]$ へ戻されてから表示される。この順序を見落とすと、出力列の一致位置付近だけがずれやすい。

第3正規形の分解

変更後は教員名から所属が決まるため、教員所属を履修表の各行に重複して置くと更新異常が残る。$R_3(\text{Instructor},\text{Faculty})$ を分けると、教員の異動は1箇所の更新で済む。

Hの最小化

前段回路から実際に現れない $(s,t,u,v)$ は、$H$ の設計では don't care として扱える。これを使わずに全16通りを無理に決めると、最小積和形が必要以上に複雑になる。

ミス分類

初期参照ミスは「そのブロックを初めて参照したこと」が原因のミスであり、既存ラインと衝突していても初回参照なら初期参照ミスに分類する。5番目の $1111$ は以前に参照済みなので、これは初期参照ミスではなく競合ミスである。