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

基準値の位置に注目する

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

交換回数の数え方

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

セマフォ値の符号

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

競合による更新消失

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

グラフ化して考える

この問題では「2以上の共通約数を持つ」を辺に置き換える。共通約数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ノードリングでは、2リンク先のノードが接続するLANまでの情報が時刻2でそろう。ただし、ノード1からそのLANまでの実際の到達コストは、原表で1と指定されたLAN接続も加えて3である。情報の交換回数2と、パケットが通るリンク数3を区別する。

語頭符号と一意復号可能性

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

経路表の容量に関する条件

第5問(1-3)は、複数LANの宛先をどの範囲まで一行に集約できるかが明示されていない。収録PDFでは、個別LANとデフォルトを使う場合と、任意集合を一行に指定できる場合を分けて導出し、原題だけから一意の最適値を確定していない。

相互インダクタンスは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 は過去出力を再利用するので少ない次数で鋭い特性を出しやすい. 一方で, フィードバックがあるため安定性と量子化誤差が問題になる. 原題(2-3)が求めるのはIIRの利点である。各枝の過去出力を1個ずつ保存して再帰計算するため、無限に続く応答を有限個の状態と演算で表せる。同程度の振幅特性をFIRで近似する場合より、演算量と記憶量を抑えられることが多い。FIRの安定性や線形位相は別の利点であり、この設問への答えと取り違えない。