京大 情報学研究科 通信情報システムコース 2023年度 院試 解答例・解説

極座標の公式を覚えるだけにしない

勾配の式は、$(z_r,z_\theta/r)$ が $(z_x,z_y)$ を回転したものだと見ると一行で示せる。 ラプラシアンは係数 $1/r$ が出る点が落とし穴である。これは基底ベクトルの長さが $\theta$ 方向で $r$ 倍になることに対応している。

ベータ関数の条件

恒等式の証明で $q>1$ が必要なのは、$x=1$ における $(1-x)^{q-1}$ の境界項を 0 にするためである。単に部分積分するだけでなく、境界項の消滅を 明記すると答案として安定する。

固有空間の確認

$A$ は対称行列なので異なる固有値の固有空間は直交する。 $\lambda=3$ の二次元空間 $x=y+z$ と、$\lambda=-3$ の方向 $(1,-1,-1)^T$ は実際に直交しており、 計算結果の検算になる。

NAND 実現の見方

積和形を NAND--NAND 形に直すときは、各積項の否定を先に作り、最後の NAND で $\overline{\overline{P_1}\,\overline{P_2}\,\overline{P_3}}=P_1+P_2+P_3$ を使う。3 入力 NAND で 2 入力積項を扱う場合は、同じ入力を 2 本に複製してよい。

Mealy 型が状態を減らせる理由

Moore 型は出力を状態に持たせるため、認識直後の出力状態が必要になる。Mealy 型は遷移に出力を 持たせられるので、接頭辞 $1,11,111$ を覚える状態だけで済む。今回の符号は prefix-free なので、 認識後は必ず初期状態へ戻せる。

2 次拡大情報源の平均符号長

ハフマン符号の平均長は、2 記号を 1 ブロックとして計算した後、最後に 2 で割る。 この割り算を忘れると、情報源記号 1 個あたりの平均符号長ではなくブロックあたりの値になる。

状態付き情報源のエントロピー

状態遷移が出力記号に依存していても、状態が分かれば出力分布は $S_A$ または $S_B$ の どちらかである。したがってエントロピー率は、定常分布で重み付けした条件付きエントロピーに なる。

巡回符号の検算

$\deg G=4$ なので次元は $7-4=3$、符号語数は $2^3=8$ 個である。表に 8 個ちょうど並んで いること、各多項式の次数が 6 以下であることが基本的な検算になる。

非正規化数の指数

非正規化数では仮数の暗黙の 1 が消える一方、指数は $1-\text{bias}$ を使う。 今回なら $2^{-2}$ に仮数 $F/16$ を掛けるため、最小刻みは $2^{-6}$ である。

分岐予測の比較

ループ分岐は最後だけ不成立になることが多い。常に成立と予測する方式は最後に 3 サイクル払う だけなので、反復回数が多い場合に強い。一方、反復回数が少ない場合は、成立を外すたびに 1 サイクルだけ払う常に不成立方式が有利になる。

偶関数の利用

どちらのフーリエ変換も偶関数なので、虚部は消え、$\cos$ 積分だけで計算できる。 $\omega=0$ は式に代入せず、面積または極限で扱う。

留数計算の符号

$\cosh z$ の零点は $i\pi/2$ から $i\pi$ 間隔で並ぶ。 分母の微分が $\sinh z$ であること、上半平面では $e^{iz}=e^{ix-y}$ が減衰することを 押さえると、閉路積分の向きと符号を誤りにくい。

ブリッジ平衡の立て方

中央枝に電流が流れないとき、中央上下の節点は同電位である。したがって左右それぞれの分圧比が 一致する。抵抗だけのホイートストンブリッジと同じ考え方を、複素インピーダンスに拡張すればよい。

有限入力抵抗の影響

増幅器の入力抵抗 $r_i$ が有限だと、帰還分圧点 $V_b$ から入力側へ電流が流れる。 そのため単純な $V_b=R_1V_2/(R_1+R_F)$ にはならない。理想利得の極限を取ると 非反転増幅器の標準利得 $1+R_F/R_1$ に戻る。

CP 比率の扱い

CP 長が最大遅延以上であることから $T_{\mathrm{CP}}\ge1\,\mu\mathrm{s}$ が先に決まる。 比率が $1:9$ なので有効シンボル長はその 9 倍であり、総シンボル長は 10 倍になる。 伝送速度の計算では CP を含む総時間で割る点が重要である。

有限容量待ち行列

状態 3 にいるときの到着はシステムに入らない。滞在時間に Little の法則を使うときは、 外部到着率 $\lambda$ ではなく、受理された実効到着率 $\lambda(1-P_{\mathrm{B}})$ を使う。

分岐即値

分岐先オフセットはバイト差ではなく、左 2 ビットシフト前の word 単位の即値で指定する。 今回の戻り先は $PC+4$ から 12 byte 戻るため、即値は $-12/4=-3$ である。

列優先アクセスの衝突

ダイレクトマップでは「容量が足りそうか」だけでなく「同じ index に写るか」が重要である。 今回の 8 KiB キャッシュでは列方向ストライドが 16 ブロックで、32 行離れたブロックが同じ index に写るため、同じブロックの隣接列を読む前に追い出される。

NFA の読み取り

開始状態に $a,b$ の自己ループがあるため、受理に使う分岐を任意の位置まで遅らせられる。 その後に上側の $aa$ または下側の $bab$ を読み切って終わる必要があるので、言語は 「末尾条件」として表せる。

NP と co-NP の関係

$P$ は補集合で閉じている。したがって $P=NP$ が成り立つ世界では、NP も補集合で閉じて $NP=co\text{-}NP$ になる。これと矛盾する $NP\ne co\text{-}NP$ が分かれば、$P=NP$ は否定される。

具象構文と抽象構文

具象構文では括弧や優先順位が問題になるが、抽象構文では演算子の木構造だけを保存する。 そのため NNF 変換のような意味を保つ変換は、文字列ではなく AST 上で実装すると単純になる。

NNF 変換の不変条件

`nnf(e, neg)` は、`neg=False` なら $e$ と同値な NNF、`neg=True` なら $\neg e$ と同値な NNF を 返す関数である。この不変条件を置くと、二重否定、ド・モルガン律、原子命題への否定の停止条件が 自然に整理される。