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

停留点の分類

二変数関数では，停留点を求めただけでは極値とは限らない。 今回も $(0,\pm1)$ は勾配が消えるが，ヘッセ行列の行列式が負なので鞍点である。 極大・極小の値まで聞かれているため，点だけでなく $f(x,y)$ の値を最後に代入することが重要である。

積分順序の選び方

$e^{-y}$ は $x$ に依存しないため，幅 $y-y^2$ を先に出す順序が最短である。 領域を $y^2\le x\le y$ と読めるかどうかで計算量が大きく変わる。

固有ベクトルの注意

$ab<0$ では固有値が実数でなくなるので，実ベクトルの直交性を論じる設定から外れる。 また $ab=0$ では固有値が重なり，二つの独立な固有方向が常に得られるわけではない。 「直交する条件」は，通常は二つの異なる固有値に対応する固有ベクトルについて問われているので， 非退化な場合を明記して $a=b$ と結論するのが安全である。

フーリエ変換の正規化

この問題では逆変換に $1/(2\pi)$ が付く流儀である。 Parseval の係数もこの正規化に合わせて $\int |f|^2=(1/2\pi)\int |F|^2$ と書く必要がある。 係数を別流儀と混ぜると $\pi/3$ の係数がずれる。

Euler 型方程式

$x^2y''+xy'-4y=x^3$ と見れば，左辺は $x^m$ を保つ形である。 右辺 $x^3$ は同次解 $x^{\pm2}$ と重ならないため，特解 $Ax^3$ がそのまま使える。

留数の極の選択

$i(2+\sqrt5)$ の絶対値は $1$ より大きく， $i(2-\sqrt5)$ の絶対値は $\sqrt5-2<1$ である。 単位円上の積分ではこの判定を明示すると，どの留数を取るかが曖昧にならない。

影像法の理由

導体球の影像電荷は，球面上で実電荷と影像電荷の距離比が一定になるように置く。 接地条件は球面電位が $0$ であること，中性絶縁条件は導体に誘起される総電荷が $0$ であることである。 中心電荷は球面上で同じ距離 $a$ に見えるため，等電位性を壊さない。

双極子近似

双極子の式では $\delta/r$ の一次項だけを残す。 二つの磁荷の単独寄与は $1/r$ の項が打ち消し合い，最初に残るのが $M\cos\theta/r^2$ である。 伏角の関係式は，磁界そのものの大きさではなく，水平成分と鉛直成分の比から出す。

定抵抗回路

上側の枝は直列コンデンサと $R\parallel L$，下側の枝は直列インダクタと $R\parallel C$ からなる双対な形である。 $R^2=L/C$ はこの二つの枝の周波数依存性を相補的にし，並列合成を一定値 $R$ にする条件である。

ヒステリシスの向き

入力が反転端子に入るため，入力を上げたときの遷移は $+V_S$ から $-V_S$ である。 しきい値を $V_O/2$ として現在の出力状態ごとに考えると，符号を取り違えにくい。

周期の導出

発振周期は，コンデンサが $-V_S/2$ から $+V_S/2$ へ，またその逆へ移動する時間の和である。 等抵抗分圧によりしきい値が半分になるため，指数関数の比が $1/3$ となり $\ln3$ が現れる。

情報源符号化と通信路符号化

情報源符号化は冗長性を減らす処理であり，通信路符号化は誤りに備えて冗長性を加える処理である。 ブロック図ではこの順序を取り違えないことが重要である。

ハフマン符号の自由度

ハフマン木では左右の枝に付ける 0/1 を交換できるため，符号は一意ではない。 平均符号長と語長分布が同じなら正答として扱える。

BSC の容量

BSC は対称通信路なので一様入力が最適である。 縦続接続では「一度だけ反転する」場合が全体の反転になるため， 有効交差確率 $p+q-2pq$ を先に求めてから同じ容量公式を適用する。

ハッシュ表の評価

外部ハッシュ法の本質は，衝突を同じバケットのリスト長として受けることである。 平均時間は表サイズそのものではなく，負荷率 $M/B$ で決まる。

連結リストでの挿入ソート

配列版と違って要素の移動コストは小さいが，挿入位置を探す比較回数は残る。 そのため時間計算量の主項はやはり $\sum i$ であり，最悪 $O(n^2)$ になる。

再帰の境界条件

while 条件が $i\le n-1$ なので，$n=0$ や負の $n$ でも再帰は起きない。 ここを $2^{n-1}$ に無理に当てはめると $n=0,-1$ の答えを誤る。

符号表現の切り替え

同じビット列 $11110000$ でも，符号付き絶対値では $-112$，2 の補数では $-16$ である。 設問ごとに解釈が変わるため，最初にどちらの体系で読むかを書いてから演算する。

半精度の非正規化数

指数部がすべて 0 の場合，仮数の先頭に隠れた 1 は付かない。 そのため $1000\,0001\,0101\,0101$ は通常の $-1.xxx\times2^e$ ではなく， $-0.xxx\times2^{-14}$ として読む。

パイプライン時間

停止サイクルは命令種別の出現回数に，実際に停止する割合と 1 サイクルを掛けて足す。 命令数が大きいので 5 段パイプラインの立ち上がり 4 サイクルは実質的には無視できるが， 厳密に書くと導出が明確になる。

BNF から読む優先順位

非終端記号の階層がそのまま優先順位になる。 $A$ が最も小さい部品で，$C$，$P$，$E$ の順に大きな式を作るため， $\#$，$@$，$\&$ の順に結合が弱くなる。

構文エラーと実行時エラー

構文エラーは，評価に入る前に BNF で式を作れない場合である。 一方，$(v)$ は文法的には式だが，評価結果の型が $\&$ の要求に合わないため実行時エラーである。 この二つを区別して答えることが大切である。

次数和の検算

次数列を読む問題では，次数和が偶数で辺数の 2 倍になることを確認すると数え間違いに気づきやすい。 今回の図では次数和 $26$ なので辺数は $13$ である。

存在例の示し方

図を描かなくても，標準的なグラフ名や構成法を明示すれば存在例になる。 立方体グラフや二つの三角形を橋でつなぐ構成は，次数と連結性を確認しやすい。

次数列で決まる性質

完全性は全頂点次数が $n-1$ かどうかで決まる。 連結性を仮定した木性は辺数 $n-1$ で決まる。 しかし連結性そのものは次数列に保存される情報だけでは決まらない。

OFDM の時間長

ガードインターバルは遅延広がり以上にする必要がある一方，長すぎると有効データ伝送時間の割合が下がる。 ここでは OFDM シンボル全体を $T_u+T_g$ と読み，$T_g\le0.1(T_u+T_g)$ から $T_u\ge180\,\mu\mathrm{s}$ を得る。

待ち行列の滞在時間

M/M/1 のシステム内滞在時間は平均だけでなく分布も指数分布になる。 ただしサービス時間そのものの率 $\mu$ ではなく，混雑を反映した $\mu-\lambda$ が率になる点が重要である。

電力信号の判定

有限区間平均を出してから極限を取ると，周期に依存しない平均電力 $A^2/2$ が得られる。 正弦波はエネルギー信号ではなく電力信号であるため，PSD はデルタ関数の線スペクトルになる。

直交検波

$\cos$ と $\sin$ は同じ周波数で直交している。 乗算後にはベースバンド項と $2f_c$ の高周波項が生じるので，低域通過フィルタが I/Q 分離の最後の鍵になる。

近傍項と遠方項

磁界には $1/r^2$ の誘導項と $1/r$ の放射項が現れる。 遠方界では $1/r$ 項だけが支配的で，電界と磁界は平面波と同じ比 $\eta$ を持つ。

鏡像の符号

完全導体平面に垂直な電気双極子では，鏡像電流は同相になる。 水平双極子では逆相になるため，導体面に対する向きで配列因子が変わる点に注意する。

NOR 実現

積和形から NOR 回路を作るより，和積形を使って「各和項の否定を NOR で作り，最後に NOR でまとめる」方が自然である。 入力の否定が与えられているため，反転用ゲートは数えなくてよい。

D 入力の考え方

D フリップフロップでは，次クロック後の $q_i$ がそのまま現在の $d_i$ である。 したがって，まず状態遷移表を作り，次状態の各ビットを $q_2,q_1,q_0,u$ の論理関数として最小化すればよい。

セット番号の見方

セット番号は $$\left\lfloor\frac{\text{address}}{\text{block size}}\right\rfloor \bmod(\text{set count})$$ で決まる。 表(b)のように 4096 バイト間隔の参照が並ぶと，32 バイトブロックかつ 32 セットでは同じセットに集中する。

ヒット率の逆算

表(a)は空間局所性の影響が大きく，ブロックサイズを大きくするとヒットが増える。 表(b)は同一セット内の競合が支配的で，ウェイ数を増やすと LRU で残るブロックが増える。 この二つを同時に満たす組合せとして 16 バイト・8 ウェイが残る。

接尾辞言語の状態

接尾辞 $bc$ の認識では、現在の入力末尾が目標語の接頭辞 $b$ に一致しているか、完全に $bc$ に一致しているかだけを記憶すれば十分である。この「目標語の最長接頭辞と一致する接尾辞」 を状態にする考え方は、文字列照合オートマトンの基本である。

文法から正規表現へ

$S\to Saa$ は右端に $aa$ を繰り返し追加し、$T\to bTbb$ は $b$ の個数を3ずつ増やす。 個数条件が合同条件だけに落ちるため、正規表現で表せる。

whileposの読み方

whilepos は、通常の命令型言語の while と違い、2つの式を評価して2変数を 同時に更新する式である。和の式では、減少カウンタ $y$ と累積値 $s$ を同時に更新するため、 最後に $y=0$ になった時点でちょうど総和が返る。

環境の扱い

let と whilepos はどちらも局所的な束縛を作る。外側環境を書き換える実装にすると、 スコープ規則が崩れるので、辞書をコピーして拡張する実装にしている。

和型の除去

$(M?(x)N:(y)P)$ は和型の値 $M$ を場合分けする構文である。左注入なら $x$ に中身を束縛して $N$ を、右注入なら $y$ に中身を束縛して $P$ を評価する。型は両枝の結果型が一致するときに 決まる。

型代入の選び方

$(M_1M_2)M_2$ の型付けでは、同じ $M_2$ を2つの異なる型で使う。単純型付きラムダ計算では 項が複数の型を持つことがあり、与えられた補題(A)(B)はその多相的な使い分けを許している。

自然演繹の導出

含意は「前件を仮定して後件を導く」、選言は「左右の各場合で同じ結論を導く」が基本形である。 最後の小問は古典性を表す公理的規則を一度使い、そこから目標の選言へ変換する。