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

開番地法の停止条件

$h\mapsto h+\delta \pmod{20}$ で到達できる添字数は $20/\gcd(\delta,20)$ 個である. したがって $\gcd(\delta,20)>1$ なら, 空きが別の剰余類にあってもそこへ到達できず, ループが終わらない可能性がある. 逆に互いに素なら20箇所をすべて調べるので, 20個以下の相異なるキーの挿入では必ず空きに到達する.

cuckoo hashing の見方

方式2の無限ループは, 「追い出されたキーが次に入る場所」を有向辺と見たときの閉路で起こる. $28$ の場合, 第1表の添字8で $8$ を追い出し, 第2表の添字 $8\oplus3=11\equiv1$ で $2$ を追い出し, 第1表の添字2で $22$ を追い出す, という巡回の中に入る. この閉路構造を言葉で説明できると, 単なるシミュレーション表より答案の説得力が増す.

単位換算を先に指数へ直す

この問題は $1\,\mathrm{GB}=2^{30}$ byte, $1\,\mathrm{MB}=2^{20}$ byte, $1\,\mathrm{KB}=2^{10}$ byte として扱う. 先にすべて $2$ の指数で書くと, アドレス長・オフセット長・ページ番号長は引き算だけで求まる.

アドレス変換の確認

ページ内オフセットは変換前後で変わらない. 変わるのは上位のページ番号だけである. したがって, 16進アドレスをページサイズ $0\mathrm{x1000}$ で区切り, 上位部分を表の物理ページ番号に置き換えればよい.

行列の冪が歩道を数える理由

隣接行列の積では, 中間頂点をすべて足し合わせる. これは「最後から一つ前の頂点をどこにするか」で場合分けしていることに対応する. 歩道では同じ頂点を何度通ってもよいので, 行列積の和とぴったり一致する.

三角形判定の要点

$A^2$ の非対角成分は共通隣接頂点の数である. ただし共通隣接頂点がいても, $v_i$ と $v_j$ の間に辺がなければ三角形にはならない. そのため $a_{ij}=1$ と $b_{ij}\ge1$ の両方を見る必要がある.

正則かどうかの判断

スタックに積んだ個数を後から同じ個数だけ照合する言語は, 典型的に非正則である. 図(a)は $a$ の個数と $b$ の個数の一致を要求し, 図(d)は前半列全体を逆順に照合するため, 有限オートマトンだけでは一般には記憶できない.

演算子文法の作り方

優先順位を持つ式の文法では, 低い優先順位の非終端記号から高い優先順位の非終端記号へ降りる. ここでは $S$ が加算, $X$ が乗算, $Y$ が原子を担当する. 左再帰にしておくと, 同じ優先順位の演算子を左結合として読める.

鋸歯状モデル

輻輳回避では, ウィンドウサイズは損失で半減し, 損失がなければ RTT ごとに線形に増える. したがって時間変化は鋸歯状になる. TCP throughput の近似式は, この鋸歯の面積を「次の損失までに送れるセグメント数」と結びつけることで得られる.

近似で落とさない点

$N=\frac{3}{8}W_m^2-\frac{1}{4}W_m$ の一次項を無視するのは, $W_m$ が大きいという近似である. 導出過程では一度正確な和を書いてから近似に移ると, 採点上も根拠が明確になる.

CMOS は双対性を見る

NAND では「全入力1のときだけ下へ落ちる」ので nMOS は直列になる. pMOS 側はその双対で, どれか1入力が0なら上へつながるため並列になる. NOR はこれと逆で, pMOS が直列, nMOS が並列である.

交流回路は実効値フェーザで統一する

問題文の電源は振幅ではなく実効値 $E_0$ を使える形で与えられている. フェーザで $V_1=E_0$, $V_2=-\mathrm{j}E_0$ と置けば, 位相条件は複素数の偏角の比較に落ちる. 最後に正の角周波数だけを採用する点も忘れてはならない.

線形位相の見方

3点平均ではインパルス応答が中央を軸に対称である. そのため $e^{-\mathrm{j}\omega}$ という1サンプル遅延の位相因子が外へ出て, 残りが実関数になる. これが線形位相フィルタとして扱える理由である.

移動平均の零点

$N$ 点平均は長さ $N$ の矩形窓で平均するフィルタである. 周波数応答は Dirichlet kernel 型になり, $2\pi/N$ 間隔で零点を持つ. $N$ を大きくすると零点が密になり, 平滑化は強くなるが, 必要な信号成分まで削る危険も増える.