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

ガウス積分の使い方

二重積分では平面全体を極座標で積分できるため、$\int e^{-x^2}dx$ を直接計算せずに、その二乗を先に求めるのが標準的である。ここでは $I=J^2$ とできること、さらに $J>0$ であることを明記して平方根の符号を決める。

ガンマ関数への接続

$\Gamma(1/2)$ は $t=u^2$ の置換でガウス積分そのものに帰着する。$t^{-1/2}$ と $dt=2u\,du$ が打ち消し合うため、特異性を気にせず積分できる。

行列冪の考え方

固有値が互いに異なるので行列は対角化可能である。固有ベクトルを列に並べた $P$ を作り、$A^n=PD^nP^{-1}$ とすれば、各成分は $1^n,2^n,3^n$ の線形結合として求まる。最後に $n=1$ を代入して元の $A$ に戻ることを確認すると、符号ミスを検出しやすい。

組合せ論理の最小化

最小積和形で「すべて求めよ」とある場合は、1つの式を出すだけでなく、同じコストの別解がないことにも触れると答案として強い。ここでは必須主項が3つあり、それらだけで全ミン項を覆うため一意性まで言える。

NAND 実現

NAND-NAND 形では、各積項の否定を1段目で作り、最後の NAND でド・モルガンにより和を作る。入力の否定が与えられているため、インバータ用の追加ゲートは不要である。

順序回路の状態数

この回路では「連続したか」を判定するために直前入力が必要であり、「反転後の現在出力」を保持する必要もある。したがって $(p,z)$ の4通りが自然な状態である。同じ出力を持つ状態同士も次入力で区別できるため、状態最小化で統合できない。

表の対数値の使い方

確率を分数に直すと、表にある $\log_2 3,\log_2 5,\log_2 7,\log_2 13$ だけで計算できる。たとえば $0.65=13/20$ なので $\log_2(1/0.65)=\log_2(20/13)$ と変形する。

適中率と相互情報量の違い

適中率は最も多い天気に寄せるだけでも高くなる場合がある。一方、相互情報量は $X$ と $Y$ の統計的依存を測る。今回の値は小さいが正なので、予報は完全に無意味ではない。ただし適中率という実用指標では常時晴予測を上回っていない。

マルコフ誤り源の容量

ビット誤り率だけから $1-\mathcal H(p_e)$ としてしまうと、誤りの時間相関を捨てることになる。マルコフ誤り源では状態ごとの遷移エントロピーを定常分布で平均したエントロピー率を使う。

2の補数の範囲

$n$ ビットの2の補数では最上位ビットの重みが $-2^{n-1}$ になる。5ビットなら範囲は $[-16,15]$ であり、正数同士の加算で符号ビットが1になる場合はオーバーフローを疑う。

分岐予測は周期列で考える

このコードでは各分岐の結果が $i\bmod 7$ だけで決まる。したがって、無限大に近い $N$ では初期状態の影響は無視でき、周期7の中で何回外れるかを数えればよい。共有カウンタでは、同じ $i$ の中でも $L2$ の結果が $L3$ に、$L3$ の結果が $L4$ に影響する点が重要である。

矩形関数と sinc 型積分

矩形関数のフーリエ変換は sinc 型になる。パーセバルの等式を使うと、直接扱いにくい $(\sin x/x)^2$ の広義積分を、時間領域の区間長から一気に求められる。

同次形微分方程式

$x^2$ と $y^2$ と $xy\,dy/dx$ が同じ次数で現れるため、$y=vx$ が自然な置換である。最後の $x^2+y^2=Cx$ は円族を表し、暗黙微分で元の方程式に戻ることを確認できる。

留数計算の符号

$\sin x$ を扱うときは、まず $e^{ix}$ の積分を計算し、最後に虚部を取ると極の選択が明確になる。上半平面を使うのは $e^{iz}=e^{ix-y}$ が減衰するからである。

等電位線は距離比で決まる

電位0の条件では、電荷量の比 $1:3$ が距離の比に変換される。すなわち $3/\rho_2=1/\rho_1$ なので、強い正電荷からの距離が負電荷からの距離の3倍になる点の軌跡である。これはアポロニウスの円である。

演算増幅器回路の見方

理想演算増幅器では入力電流が0、負帰還時に $V_+=V_-$ とみなせる。したがって、まず受動RC網だけで $V_+$ を $V_1,V_2$ の関数として求め、最後に $V_+=V_2$ を代入するのが最短である。

アレーの位相差

アレーファクタは、観測方向に対する素子間の経路差を位相差に直したものを足し合わせるだけで得られる。等振幅・同位相・等間隔アレーでは等比数列の和になるため、主ローブとサイドローブの形が $\sin N\psi/2$ と $\sin\psi/2$ の比で表される。

搬送波の有無

AMとDSB-SCの違いは、式では定数項1があるかどうか、スペクトルでは $\pm f_c$ の線スペクトルがあるかどうかに現れる。情報を運ぶのは側波帯であり、搬送波成分自体はベースバンド信号を含まない。

同期検波で残る雑音

同相成分 $n_I(t)$ は信号と同じ $\cos2\pi f_ct$ に乗っているため、同期検波後にベースバンドへ落ちる。一方、直交成分 $n_Q(t)$ は $\sin2\pi f_ct$ に乗っており、理想的な同相検波では低域成分として残らない。

ポアソン過程の基本性質

到着回数の平均は $\lambda t$、到着間隔は指数分布で平均 $1/\lambda$ である。独立なポアソン過程の和が再びポアソン過程になることは、二項定理で確率を畳み込むとすぐに分かる。

完全マッチングを否定する方法

二部グラフで完全マッチングがないことを示すには、Hall条件を破る部分集合を1つ示せばよい。$G_b$ では右側の $\{6,7,8\}$ が左側の $\{1,2\}$ だけにしか接続しないため、3個の頂点を2個の頂点でしか受けられない。

増大道の役割

マッチングの大きさを増やす操作は、増大道に沿って辺の採否を反転することに尽きる。未飽和頂点から未飽和頂点へ、非マッチング辺とマッチング辺を交互にたどる道を見つけるのがアルゴリズムの中心である。

最大独立集合の対称差

$A\triangle B$ による誘導部分グラフでHall条件を証明するときは、近傍が足りないと仮定して、$B$ の一部を $A$ 側の頂点で置き換える。この置き換えでより大きい独立集合が作れてしまう、という矛盾が本質である。

NFAとDFAの違い

NFAでは遷移が存在しない入力があってもよく、最後の $a$ を非決定的に選ぶような簡潔な設計ができる。DFAではすべての入力に対して次状態が一意に決まる必要があるため、沈み状態や「最後の文字」を覚える状態が必要になる。

言語クラスの見分け方

有限長制限や偶奇だけの条件は正規言語で扱える。回文は中央を境に左右を照合するためスタックで扱え、文脈自由である。平方数長やコピー言語は、有限オートマトンや1本のスタックでは必要な情報を保持できない典型例である。

時間と空間の関係

時間制限は空間制限より強い条件である。多項式時間で止まる計算は、多項式個を超えるセルを訪問する前に時間切れになるため、多項式空間にも収まる。

曖昧性の示し方

曖昧性は、同じ終端記号列に対して異なる構文木を2つ示せば十分である。優先順位のない式文法では、$+$ と $*$ のどちらを根にするかが選べてしまうため、典型的に曖昧になる。

優先順位と結合性

非曖昧文法では、加算を扱う非終端 $E$、乗算を扱う非終端 $T$、原子式 $F$ に層を分ける。上位の $E$ から下位の $T$ を呼ぶ構造にすると、$*$ が $+$ より先にまとまる。

環境つき評価

変数を持つ式では、変数名を値へ対応させる環境が必要である。let は環境を拡張して本体を評価する構文であり、束縛の有効範囲を明確に扱える。