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

基準値の位置に注目する

この実装は降順整列であり, 条件が `>' である点が重要である. 基準値と等しい要素は左側へ移されないので, 同じキーを持つデータの相対順序が基準値交換で壊れ得る.

交換回数の数え方

自己交換も関数 `swap' の呼び出しであるため, 回数に含める. 最悪入力で長さ $m$ の分割ごとに $m$ 回呼ばれることを押さえると, 合計は等差数列の和として一気に求められる.

セマフォ値の符号

セマフォを整数として実装すると, 正の値はすぐ利用できる資源数を表し, 負の値はその絶対値だけ待ちプロセスがいることを表す. $P$ 操作で負になったプロセスは待ち, $V$ 操作で待ちプロセスが1つ起こされる.

競合による更新消失

$n=2n+3$ は1つの代入文に見えるが, 機械的には読み出し, 演算, 書き込みに分かれる. 排他制御がないと, 2つのプロセスが同じ値から同じ新値を作り, 片方の更新が結果に反映されない. これが $f_2$ で $n_1$ を超えない理由である.

グラフ化して考える

この問題では「共通約数を持つ」を辺に置き換えると見通しがよい. 偶数全体は必ず clique になるため下界に使いやすく, 共通約数ごとに倍数集合を数えると上界に使いやすい.

極限評価の勘所

$m(k)$ はおおよそ $k^2$ の量なので, $\sum_{k\le n}m(k)$ は $n^3$ の量になる. したがって, $m(k)$ の2次の係数だけを押さえれば, $a_n$ の極限の上下界が得られる.

スタックの意味を決める

PDAの遷移は暗記で埋めるより, スタックトップを「どちらの記号が何個余っているか」と読むと自然に決まる. 反対側の記号を読めば pop, 同じ側の記号を読めば push である.

空スタック受理と prefix-free

決定性PDAの空スタック受理では, ある語を受理した瞬間にスタックが空になる. その語を真の接頭辞として持つ語も受理しようとすると, 受理後にさらに計算を続ける必要があり, 決定性と空スタック受理の性質に反する. ここが問(4)の中心である.

距離ベクトルの伝播

距離ベクトル型では, 1ステップで1ホップ先の情報が伝わる. 5ノードリングではノード1から最遠のローカルネットワークまで2ホップなので, 時刻2で全宛先の最短経路がそろう.

prefix code と一意復号可能性

瞬時復号可能性は接頭辞関係だけで判定できる. 一意復号可能性はそれより弱い条件なので, prefix code でない符号も一意復号可能であり得る. $C_1$ はその例である.

相互インダクタンスはT型へ直す

結合インダクタをそのまま扱うと節点方程式が見えにくい. T型等価回路へ置き換えると, 今回は $L_1-M=0$ となり, 節点 $a$ 側と $b$ 側が独立な一次回路として読める.

位相条件の読み方

$a$ と $b$ の電位が等しくなる条件は, 2つの分圧比が等しいことに尽きる. その条件で入力電流をまとめると一次遅れの形になり, 45度条件は $\omega L=R_1$ とすぐ分かる.

部分分数分解の意味

各項 $\frac{1}{s-\lambda_k}$ は時間領域では $e^{\lambda_k t}$ に対応する. したがって, 部分分数分解はフィルタを一次モードの和に分けていると見ればよい.

IIR と FIR の違い

IIR は過去出力を再利用するので少ない次数で鋭い特性を出しやすい. 一方で, フィードバックがあるため安定性と量子化誤差が問題になる. FIR は次数が大きくなりがちだが, 実装上の頑健さを説明できる点が答案の要点である.