阪大 情報科学研究科 専門科目（情報工学） 2024年度 院試 解答例・解説

挿入ソートで見るべき場所

本問では, 探索方法を線形探索から二分探索に変えても, 配列で挿入ソートを実装している限り要素移動のコストが残る点が重要である. 探索だけを見ると $O(n\log n)$ に見えやすいが, 代入によるシフトの総数は逆順入力で $\Theta(n^2)$ になる.

二分探索の終了位置

プログラム2は「同じ値があれば後ろに入れる」形の上側挿入位置を返す. 本問では整列対象がすべて異なる場合を考えるので, $left$ は単に $key$ より小さい要素の個数と一致する. ループ終了後に $right$ ではなく $left$ を使う理由は, $left$ が未確定区間の左端として挿入位置を表すからである.

オーバーレイは最大同時使用量を見る

オーバーレイでは, 全モジュールを常駐させる必要はない. ただし, 実行のある時点で同時に必要になるモジュール群は同時に主記憶上へ置けなければならない. そのため, 各組合せの合計の最大値が最低必要容量になる.

Beladyの異常の判定

Beladyの異常は「ページ枠を増やしたのにページフォールトが増える」現象である. 本問のFIFOでは, 2枠から3枠で $10\to9$, 3枠から4枠で $9\to9$, 4枠から5枠で $9\to5$ であり, 増加がない. したがって, 選択肢は「確認できなかった」と判断する.

同型判定では不変量で候補を減らす

グラフ同型を調べるときは, いきなり全単射を探すより, 次数列, 辺数, 三角形数, 連結成分, 補グラフなどの同型不変量で候補を絞るのが確実である. 不変量が違えば同型ではない. 一方で, 不変量が同じだけでは同型とは限らないため, 最後に具体的な対応を示す必要がある.

ラベル付きと非同型代表元の違い

$\mathcal{G}_n$ は頂点ラベルを固定したグラフ全体なので, 辺の有無を選ぶだけで $2^{\binom{n}{2}}$ 個になる. これに対して $\mathcal{I}_n$ は同型なものを1つにまとめた代表元集合である. 同じ形のグラフでもラベルの付け替えによって高々 $n!$ 個のラベル付きグラフができる, という見方が(2-4)の下界証明の中心である.

下界の意味

(2-4)の不等式は, 非同型な単純無向グラフの種類数が非常に大きいことを示している. 代表元数を正確に数えるにはBurnsideの補題などが有効だが, 本問では「各同型類の大きさは高々 $n!$」という粗い上界だけで十分な指数的下界が得られる.

Chomsky標準形へ直すときの注意

本問では, 元の文法に空語生成と無用記号が混ざっている. そのまま機械的に規則を書き換えると, $B$ のように終端記号列を一切生成できない変数や, $\varepsilon$ を経由する規則が残りやすい. 最初に言語の形を読み取り, 空語だけを除いてから, 必要な非空の基底を別規則で用意すると見通しがよい.

CYK表の読み方

$Q[i][j]$ は「部分列 $a_i\cdots a_j$ を生成できる変数の集合」である. 長さ1は終端規則 $X\to a_i$ だけで埋まり, 長さ2以上は分割位置 $k$ をすべて試して, 左半分を作る変数と右半分を作る変数を組み合わせる. そのため, 表を作るときは対角線から右上へ, 短い区間から長い区間へ埋めるのが基本である.

正当性証明の核

CYK法の正当性は, Chomsky標準形の「最初の一手」が必ず $X\to YZ$ または $X\to a$ であることに依存している. 長さ1なら終端規則を見るだけでよい. 長さ2以上なら, 構文木の根の直下で文字列が左右2つの連続区間に分かれるので, その分割位置を全探索すればよい. これが(2)の同値性の理由であり, (3)の判定条件にも直結する.

節点数は終端葉も数える

(4)で $3n-1$ になるのは, 終端記号の葉だけでなく, その直上の変数節点も別に数えるからである. 変数だけを数えると $2n-1$ 個であり, 終端記号の葉 $n$ 個を足して $3n-1$ 個になる. $n=1$ の場合も, 開始変数と終端葉の2個なので $3\cdot1-1=2$ と一致する.

CSMA の要点

CSMA は「送る前に聞く」方式である. ただし, 聞いているのは自分の位置で観測できる媒体状態であって, ネットワーク全体の真の状態ではない. 有線でも信号の伝搬には時間がかかるので, 伝搬遅延が大きいほど「相手の送信開始がまだ届いていない」時間が長くなる. この時間幅を衝突が起こりやすい脆弱期間として理解すると, (2) の説明を書きやすい.

CSMA/CD と無線の違い

CSMA/CD は Ethernet の古典的な共有媒体で重要な考え方であり, 衝突を検出したら送信を止めて再送へ回る. 一方, 無線では送信しながら同時に弱い受信信号を正確に検出することが難しく, さらに隠れ端末のように送信側では衝突原因を観測できない場合がある. そのため無線 LAN では衝突検出ではなく, 衝突回避(CSMA/CA)や RTS/CTS による予約が重要になる.

隠れ端末問題の答案で落としやすい点

(3-1) では「端末1と端末2が遠い」だけでは不十分である. 採点上は, キャリアセンスでは互いの送信を検出できない ことと, 共通の受信先である端末3ではフレーム衝突が起こる ことを両方書く必要がある. 問題文が指定している二つの語句をただ並べるのではなく, 送信開始から衝突までの因果を一文ずつ追うと答案が安定する.

RTS/CTS の効き方

RTS/CTS は送信者どうしが互いを聞けない状況で, 受信者の応答を周囲に聞かせる仕組みである. この問題の配置では, 端末1と端末2は互いを受信できないが, 中央の端末3には双方が届く. したがって端末3が送る CTS を端末2が聞き, 「いま端末3は端末1との通信を予約している」と判断して送信を控える. この説明まで書けると, 単に用語名を答えるより強い答案になる.

検算的な見方

RTS/CTS が常に性能を上げるわけではない. 制御フレームの交換自体がオーバーヘッドになるため, 短いデータフレームや隠れ端末が少ない環境では不利になることもある. しかし本問では隠れ端末によるデータフレーム衝突を避ける目的なので, 大きなデータフレームの衝突を短い制御フレームの予約で防ぐ, という利点を中心に述べればよい.

二端子対回路の符号規約

縦続行列では電流の向きの規約で符号が変わることがある. 本問の図では $I_1,I_2$ がどちらも左から右向きに描かれているため, $$\begin{bmatrix}V_1\\ I_1\end{bmatrix} = F \begin{bmatrix}V_2\\ I_2\end{bmatrix}$$ と読むと, 直列素子は $\begin{bmatrix}1&Z\\0&1\end{bmatrix}$, 並列素子は $\begin{bmatrix}1&0\\Y&1\end{bmatrix}$ になる. 出力ポート電流を「回路へ流れ込む向き」に取る別流儀とは $B,C$ などの符号が変わり得るので, 図の矢印を先に確認するのが安全である.

平均電力式の見通し

(1-2) は全回路の入力インピーダンスを一気に出してもよいが, 右端の抵抗電圧 $V$ を基準にして左へ戻ると計算が短い. 抵抗の平均電力は $P=|V|^2/R$ なので, 最終的に $E/V$ の絶対値二乗を求めればよい. 実部が $1-3\omega^2LC+\omega^4L^2C^2$, 虚部が $(\omega L/R)(2-\omega^2LC)$ になるため, 問題の形 $$\frac{E^2}{P} = (1+x)^2R+\frac{\omega^2L^2(2-y)^2}{R}$$ と係数を比較すれば空欄が決まる.

カルノー図のまとめ方

5変数のカルノー図は2枚の4変数カルノー図として扱う. ドントケアを使えるため, $x_1=x_0=0$ の列を $x_4$ 側も含めて大きくまとめられる. これが $\overline{x_1}\overline{x_0}$ であり, 本問の簡単化で最も大きなまとまりである. 残る $30,31$ の1は $x_0$ だけが違う隣接2マスとしてまとめ, $x_4x_3x_2x_1$ を得る.

NAND 実装での採点ポイント

積和形をそのまま AND/OR/NOT で描くと, 2入力 NAND のみという条件を満たさない. NAND だけで OR を作る基本は $$A+B=\operatorname{NAND}(\overline{A},\overline{B})$$ である. したがって, $A=x_4x_3x_2x_1$ については $\overline{A}$ を NAND で作り, $B=\overline{x_1}\overline{x_0}$ については $\overline{B}=x_1+x_0$ を NAND で作って, 最後にもう一度 NAND に入れる. 上の構成はゲート数が9個なので, 指定された上限内に収まる.

正則関数の線積分

$f(z)=z^2$ は原始関数 $z^3/3$ を持つ. したがって, 始点と終点が同じなら経路の形に依存しない. (1-1) で直接計算を求められている場合でも, 計算結果が端点だけで決まることを知っていると符号確認が楽になる. 本問では $C_1$ と $C_2$ の向きが逆向きに対応しているので, $I_1=-I_2$ になる.

コーシーの積分定理と留数定理の使い分け

コーシーの積分定理を使える条件は, 被積分関数が閉曲線の内部と境界で正則であることだ. $z^2$ では問題ないが, $1/(z^4+1)$ では囲まれた領域内に極がある. この場合は積分が0になるのではなく, 内部の極の留数が積分値を決める. 極がどの領域に入るかを図で確認してから定理を選ぶのが重要である.

逆フィルタの安定性

伝送路 $S$ は2タップ遅延を含む FIR フィルタであり, それ自体は安定である. しかし逆フィルタ $T=1/H_S$ は一般に IIR になる. 逆フィルタが安定かどうかは, $H_S$ の零点, すなわち $H_T$ の極が単位円内にあるかで判定する. 本問では極の半径が $1/2$ なので, 因果的に実装しても単位円が収束領域に入り, BIBO 安定となる.

振幅特性の読み方

$H_S(e^{\mathrm{i}\omega})=1+\frac12e^{-\mathrm{i}\omega}+\frac14e^{-2\mathrm{i}\omega}$ は, 近傍サンプルを正の重みで足すので平滑化の性質を持つ. その逆 $H_T$ は平滑化で弱められた成分を戻すため, 相対的には高域を持ち上げる. 極の角度 $\pm 2\pi/3$ は振幅が大きくなる方向を示しており, 用語選択ではここをピーク位置として答えればよい.