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

端点の微分

通常の導関数の式は開区間 $(-1,1)$ で求める。端点 $x=1$ では両側微分は定義できないため、入試答案では「左微分係数」または「左極限」と明記するのが安全である。

重積分の領域

$y=x$ と $y=x^2$ の交点は $x=0,1$ であり、この範囲では $x^2\le y\le x$ である。領域の上下関係を逆にすると符号が変わるので、最初に区間を確認することが重要である。

対称行列の見方

対角成分が等しく非対角成分も等しい行列は、和方向 $(1,1)$ と差方向 $(1,-1)$ に分解すると一瞬で対角化できる。特性方程式を展開してもよいが、この形を覚えておくと計算量を減らせる。

余弦変換の正規化

この問題では余弦変換側に $2/\pi$ を付けず、逆変換側に $2/\pi$ を付ける定義である。標準公式を暗記している場合でも、係数の位置を必ず問題の定義に合わせる必要がある。

微分方程式の置換

$-2xy'$ と $(x^2-5)y$ が同時に現れる形から、$e^{x^2/2}$ を外に出す置換が自然である。この置換により一階微分項が消え、定数係数の方程式に落ちる。

留数計算の極

$a>1$ のため、$a-\sqrt{a^2-1}$ は $0$ と $1$ の間にある。したがって対応する極だけが単位円内に入り、もう一方の極は単位円外に出る。

接地導体の扱い

外側球殻を接地しているため、外側導体の電位は $0$ に固定される。内側の電荷 $Q$ により球殻内面には $-Q$ が誘導されるが、接地により外面に余分な電荷を残さないため、外部電界は消える。

ラプラス方程式の確認

電荷が存在しない領域の電位はラプラス方程式を満たす。導体表面では面電荷により電界の法線成分が不連続になり得るので、確認すべき領域は $a<r<b$ と $r>b$ の開領域である。

磁界の幾何

点 $P$ での2つの磁界はそれぞれ導線を中心とする円の接線方向である。合成磁界の大きさが簡単な形になるのは、距離 $a,b,d$ が作る三角形の余弦定理で角度依存性が整理されるためである。

相互誘導の符号

相互インダクタでは、電流が同名端子へ入るか出るかで $j\omega M$ の符号が変わる。この問題では両枝の電流が同名端子に入る向きなので、両方の回路方程式で相互項は正符号になる。

フィルタ出力の判定

$V_2/V_1$ は分子が $s^2$ なので低周波で消え高周波で通る。$V_4/V_1$ は分子が定数なので低周波で通り高周波で消える。$V_3/V_1$ は分子が $s$ なので中間周波数で最大となる。

ハフマン符号の非一意性

同じ確率の記号があるため、左右の割当てや同確率記号の順序を変えると別の符号表になる。しかし符号語長の組が同じなら平均符号長は同じであり、正答として扱える。

巡回符号の判定

巡回符号では、多項式が生成多項式で割り切れることが符号語であるための条件である。候補語判定、組織符号化、シンドローム計算はいずれもGF(2)上の多項式除算に帰着する。

冗長度と訂正能力

$C_1$ は高符号化率だが最小距離が小さい。$C_2$ は検査ビットを多く使うため符号化率は下がるが、最小距離が大きくなり、実際の通信路での誤り訂正に使いやすくなる。

接続行列から補グラフを作るとき

接続行列では、列が辺を表す。補グラフを直接「0と1の反転」で作ることはできないため、一度辺集合へ戻してから、存在しない頂点対を列に並べる必要がある。

再帰手続きの読み方

商を先に再帰処理して余りを後で出力するため、桁は上位から出る。これは10進数を筆算で読むときと同じ構造で、基数が3になっている。

クイックソートの計算量

平均 $O(n\log n)$ と最悪 $O(n^2)$ の差は、分割の偏りに由来する。答案では、単に計算量だけでなく、なぜその再帰木になるのかを一言添えると説得力が増す。

同じビット列でも表現体系で値が変わる

符号付き絶対値表現では，最上位ビットは符号だけを表し，残りのビットは通常の2進絶対値である。 一方，2の補数表現では最上位ビットの重みが $-2^{7}$ になり，残りのビットの正の重みと合わせて値を読む。 したがって同じ $10111000$ でも，符号付き絶対値なら $-56$，2の補数なら $-72$ になる。 この区別を書かずにビット列だけを足すと，小問(c)と(d)を取り違えやすい。

オーバーフローの見分け方

8ビット2の補数で表せる範囲は $-128\le x\le127$ である。 負数と負数の加算結果が正の符号ビットをもつ場合，真の和が下限を下回ったことを示す。 本問では $$-72+(-57)=-129$$ であり，範囲外なので，得られた下位8ビット $01111111$ をそのまま $+127$ と解釈してはいけない。 答案では「ビット列としての結果」と「算術結果としてはオーバーフロー」の両方を明示するのが安全である。

符号拡張の根拠

2の補数の符号拡張で1を埋める理由は，単に見た目をそろえるためではない。 8ビットの負数 $b$ を16ビットにするとき，上位8ビットを1で埋めることで， 追加された正の重みと新しい最上位ビットの負の重みが打ち消し合い，数値が保存される。 符号付き絶対値表現の拡張とは考え方が異なるので，ここも混同しない。

整列化制約の採点観点

整列化制約の説明では，境界アドレスに置くという定義だけでなく，なぜ必要かを書く。 語が境界をまたがなければ，メモリバスやキャッシュラインからの読み出しが単純になり，余分なアクセスを避けられる。 その反面，構造体メンバの間や末尾にパディングが入り得る。 高速化とメモリ増加のトレードオフまで書くと，単なる用語説明より強い答案になる。

分岐ペナルティを追加サイクルとして数える

単一サイクル方式では，命令数 $N=10^7$ にサイクル時間 $2\,\mathrm{ns}$ を掛けるだけである。 パイプライン方式では，理想的な $N$ サイクルに，成立分岐回数 $$10^7\times0.10\times0.60=6.0\times10^5$$ に対応する停止サイクルを加える。 5段では $1$ サイクルずつ，8段では $2$ サイクルずつ増えるので， $$(10^7+6.0\times10^5)\times500\,\mathrm{ps}=5.3\,\mathrm{ms},$$ $$(10^7+1.2\times10^6)\times400\,\mathrm{ps}=4.48\,\mathrm{ms}$$ となる。 初期充填・排出を別途数える指定がない限り，命令数が大きいためこの数サイクル差は無視してよい。

BNFから優先順位を読む

非終端記号が $A,B,C,D,E$ と段階化されているとき、下位の非終端ほど強く結合する。右辺が $B\_C$ のように右側で同じ非終端を呼ぶと右結合、$D*C$ のように左側で同じ非終端を呼ぶと左結合になる。

関数オブジェクトとクロージャ

クロージャは「コード」と「自由変数を束縛した環境」の組である。オブジェクト表現では、コードがメソッド、環境がフィールドに対応する。この対応を書けると、高階関数の実装説明として十分に具体的になる。

二部グラフと奇閉路

二部グラフには奇数長閉路が存在しない。したがって、奇数頂点の二部グラフにハミルトン閉路がないことは、ハミルトン閉路の長さが頂点数に等しいことから直ちに従う。

Oreの定理の核心

極大反例を取ると「非辺を足せばハミルトン閉路ができる」ため、元のグラフにはハミルトンパスがある。最後は、パスの両端の次数和が大きいことを使い、途中で交差する2本の接続を見つけて閉路に組み替える。

OFDMの時間関係

全サブキャリアで並列化するため、有効シンボル長はサブキャリア数に比例して長くなる。ガードインターバルを遅延広がり以上にしつつ、全体に占める割合を抑えることが設計条件である。

損失系の特徴

$M/M/3/3$ では待ち行列がないため、満杯状態で到着した呼は失われる。状態確率はErlang B式そのもので、受理された呼の滞在時間はサービス時間だけになる。

DSB-SCとAMの違い

DSB-SCは搬送波そのものを送らないため電力効率は良いが、受信側で搬送波位相を同期させる必要がある。通常AMは搬送波を残すため包絡線検波が可能だが、搬送波電力が情報を運ばない。

ルートレイズドコサイン

送信側と受信側に同じルート特性を分けて持たせると、合成応答がレイズドコサインになる。これが整合フィルタ受信と符号間干渉ゼロ条件を同時に満たす理由である。

近傍界と遠方界

$1/r^3$、$1/r^2$、$1/r$ の項が現れるが、放射電力に寄与するのは遠方で残る $1/r$ の項である。放射抵抗や利得を求めるときは遠方界だけを用いる。

短いダイポールの係数

微小ダイポールでは電流分布を一様とみなすため、放射抵抗は $80\pi^2(l/\lambda)^2$ になる。半波長ダイポールの約73オームとは別の公式なので混同しない。

NAND実現

積和形 $f=P_1+P_2+P_3$ は、各積項の否定 $\bar P_i$ をNANDで作ると、最後のNANDで $\overline{\bar P_1\bar P_2\bar P_3}=P_1+P_2+P_3$ となる。入力の否定が与えられているため、インバータ用のNANDを追加しなくてよい。

状態最小化

Mealy型の状態最小化では、各入力に対する出力が一致し、かつ次状態が同じ同値類へ入る状態を併合できる。到達不能状態は、最小化の前に表から除いてよい。

外部記憶はCPUと独立

CPUが次のプロセスを実行している間にも外部記憶アクセスは進む。表を作るときは、CPUキューと外部記憶キューを別々に更新するのが安全である。

コンテキストスイッチ

クオンタムが切れて同じプロセスしか実行可能でない場合、本問ではコンテキストスイッチを入れない。最後の $P_1$ はこの条件により連続実行される。

和のNFA

「または」で定義された正規言語は、開始状態から $\varepsilon$ 遷移で各オートマトンへ分岐させればよい。NFAを使うと和集合の構成が簡潔になる。

文法の意味

$0S1$ と $1S0$ は両端に異なる記号を足し、$SS$ は均衡文字列を連結する。この2つで、0と1の個数が等しい全ての並びを生成できる。

破壊されるレジスタ

この言語には加算や乗算の基本命令がないため、ループカウンタは dec によって破壊される。乗算で $r_2$ を繰り返し使うには、毎回 $r_3$ にコピーしてから内側ループを回す必要がある。

returnの扱い

return は単なる命令列の終了ではなく、ネストの内側からでもプログラム全体を停止させる制御である。実装では例外や特別な戻り値で表すと明確になる。

反復子としてのI

規則 $I(SM)NP\to IMN(NP)$ は、第2引数 $N$ を第3引数 $P$ に1回適用し、自然数を1つ減らす規則である。したがって $I$ は自然数による反復を表す。

自然演繹の書き方

選言を仮定から使うときは、左右それぞれの場合で同じ結論を導き、選言除去でまとめる。含意を証明するときは、前件を仮定して後件を導き、最後に仮定を外す。