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

斉次方程式の判定

未知数の個数と方程式の個数が等しい斉次一次方程式では、非自明解の有無は係数行列が正則でないこと、すなわち行列式が 0 であることに帰着する。根 $a=-2$ は重根であるが、問われているのは $a$ の値なので重複度を答える必要はない。

極限の取り方

$\tan x$ の第3次項まで見れば、発散する $1/x^2$ が打ち消された後の定数項が決まる。ロピタルの定理を繰り返してもよいが、展開の方が誤符号を避けやすい。

球面領域の対称性

円柱は $xy$ 平面で $(x-a/2)^2+y^2\le (a/2)^2$ という円柱である。球面上では上半球側と下半球側に同じ面積の領域が現れるため、$\theta$ の積分範囲が二つに分かれる。この二つを落とすと面積が半分になってしまう。

論理関数の扱い

$f=(g\oplus h)r$ では、$g\oplus h=0$ の場所で $f=1$ になっていると、どのような $r$ を選んでも実現できない。最初にこの矛盾の有無を調べ、その後で $r$ のドントケアを使って最小化するのが安全である。

状態最小化

順序回路の状態最小化では、まず同じ入力に対して同じ出力を返す状態だけを候補にする。次に、それらの次状態が同じ同値類へ入るかを反復的に確認する。出力だけで判断すると、遷移先の違いを見落とす。

完全グラフのランダムウォーク

完全グラフでは現在いる頂点以外の3頂点へ等確率で移る。定常分布が一様になるため、相互情報量は「次の頂点が全体として持つ2ビット」から「現在頂点を知った上でも残る $\log3$ ビット」を引けばよい。

巡回符号の判定

巡回符号では、符号語であることは生成多項式で割り切れることと同値である。ハミング符号であるという指定から、最小距離は符号理論の標準結果 $3$ を使える。ただし、重み3の具体例を出すと最小距離の上界も確認できる。

制御信号の読み方

命令ごとの本質は、add が「Accに加算結果、PCに $PC+1$」、mov が「Accに即値、PCに $PC+1$」、jmp が「Acc保持、PCに即値」である。データパス上のMUXがこの三つを選べるように制御表を作ればよい。

Booth再符号化

通常の繰り返し乗算では1の立っている桁ごとに部分積を作る。一方、Booth 法では連続する1を差で表すため、正の部分積と負の部分積が混じる。負の部分積は必ず指定ビット幅の2の補数で書くことが重要である。

フーリエ変換の微分性質

時間領域で $t$ を掛ける操作は、周波数領域では $\omega$ 微分に対応する。符号は定義の指数 $e^{-i\omega t}$ に依存するので、$-i$ の位置を丁寧に追う必要がある。

留数計算の収束条件

$-1<\alpha<1$ は、原点近くで $x^\alpha$ が可積分であり、無限遠で $x^{\alpha-2}$ が可積分であるための条件である。この条件がそのまま鍵穴型経路で小円・大円の寄与を消せる条件にもなっている。

磁界と磁束密度の区別

真空中では $B=\mu_0H$ である。ここでは磁界 $H$ を問う形なので、ビオ・サバールの係数は $\mu_0/(4\pi)$ ではなく $1/(4\pi)$ になる。

発振回路の見方

この回路は、積分器が三角波を作り、ヒステリシスを持つコンパレータが閾値で方形波を反転させる構造である。周期は、三角波が二つの閾値間を一定傾きで移動する時間から直接求められる。

OFDMの時間設計

総ビットレートが固定されると、サブキャリア数を増やすほど各サブキャリアのシンボル時間は長くなる。遅延広がりを吸収するためのガードインターバルを相対的に短くしたい場合、十分長い有効シンボル時間が必要になる。

有限容量待ち行列

M/M/2/4 は出生死滅過程として扱うと最も簡単である。サーバ数が2なので、システム内呼数が2以上のときのサービス完了率は常に $2\mu$ になる点が計算の分岐である。

ヒープ配列表現

1始まりの配列では、親と子の添字公式が特に簡単になる。0始まり配列とは公式が異なるため、添字が $A[1]$ から始まる指定であることを確認してから答える。

再帰関数の端点

この関数は通常の二分探索に近いが、左側を探索するときに $c-1$ ではなく $c$ を含める。したがって停止条件や呼び出し回数を数えるときは、実際の区間列を書き出すとミスを避けられる。

NFAからDFAへの変換

NFAでは同じ入力文字で複数の遷移を同時に追う。部分集合構成で到達可能集合を状態にし、その後で等価状態をまとめると、数え上げや正規表現の導出が安定する。

文法の見かけに惑わされない

$T$ は $b$ の個数に合同条件を作るが、$S\to Sb$ が右側に任意個の $b$ を追加できるため、最終的な言語ではその合同条件が消える。生成規則を局所的に見るだけで非正規と判断しないことが大切である。

空リストとLR(0)

空列生成がある文法でも LR(1) なら先読みで還元タイミングを決められる場合がある。しかし LR(0) は先読みを使わないため、次のトークンを見ずに空列へ還元してよいかを決めなければならない。この文法ではそこが衝突になる。

状態を明示する理由

インタプリタでは「式の評価」と「命令の実行」が状態を介してつながる。代入は状態を更新し、条件分岐とループは式を現在状態で評価して実行する命令を選ぶ。この対応を書けていれば、構文解析器を実装しなくても意味論の要点を示せる。