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

方針 — 循環バッファとシフト計算

優先度キューを連続配列で実装する基本パターン. 挿入時のシフト数は「線形時間 in キュー長」が上限. 大量データでは二分ヒープ ($O(\log n)$) が標準だが, 本問は線形版.

典型ミス

• (2-1) で (A) と (B) を逆にする (条件 $\text{prev}<d$ で続行). 不等号方向に注意.
• (2-3) で「3 と 5 の比較」を省略. 各ステップを丁寧に.
• (2-5) で「全部挿入」と単純化すると $\mathtt{NMAX}-1$ 個で上限. それ以降の挿入と取出しの交互パターンを忘れる.

背景 — 二分ヒープと priority queue

実用の優先度キューは二分ヒープ (binary heap) で実装. 挿入 $O(\log n)$, 取出し $O(\log n)$. STL の std::priority\_queue, Python の heapq などが使う. 本問の線形版は教育的には基本だが大規模応用には不適.

方針 — 空き領域管理の 3 方式

ファイルシステムでの空き領域管理:

• 連結リスト: 各空きブロックに「次の空きブロック」のポインタを格納. 先頭から取得. 利点: 隣接性なくても OK. 欠点: 連続領域確保が困難.
• ビットマップ: 各ブロックに 1 ビット (空き/使用中). 利点: 連続領域検索が早い. 欠点: ブロック数が多いとマップサイズが嵩む.
• Extent (階層): 大きな連続領域を 1 つのレコードで管理. 現代の ext4, NTFS など.

典型ミス

• (1-1) (え) で「テラ = $10^{12}$」混同. 本問は $1$ TB $=10^{9}$ KB と明示. 計算結果は$0.25$ TB.
• (2-1) で「先頭から 4 つ」を取り違える. 連結リストの順序 ($3\to 6\to 4\to 7\to\cdots$) を忠実に.
• (2-2) でブロック番号順に並べたビットマップと「ファイル B のリンク」を混同しない.

背景 — トラック / シリンダ / セクタ

物理的な HDD は複数の同軸円盤 (プラッタ). プラッタの両面にヘッドがあり, 同心円状にデータが記録されたものがトラック. 各プラッタの同じ半径のトラックを束ねたものがシリンダ (ヘッド移動なしで読める単位). セクタは円弧上の最小単位 (通常 512 B 〜 4 KB).

近年は SSD への置き換えで物理機構は変わったが, ファイルシステムの抽象 (ブロック, 連結リスト/ビットマップ管理) は引き続き有効.

方針 — 床関数と整数解探索

$\lfloor\cdot\rfloor$ を含む方程式は $\lfloor x\rfloor=n$ と置いて整数 $n$ を場合分け. 制約 $n\le x<n+1$ を使う.

(5)(6) は連分数展開やEuclid のアルゴリズムに類似の繰り返し構造. 各レベルで $n=\lfloor f_{k}(x)\rfloor$ を考え, $f_{k+1}(x)=xn$ で次レベルへ.

典型ミス

• (3) で「全射でない」を示すには値域に穴があることを具体例で. 単に「値域が $[0,\infty)$ でない」では不十分.
• (4-2) 反対称性は$k\ne l$で双方向の関係が成り立たないこと. $k=l$ の自明ケースは反対称性に影響しない.
• (6) で複数の $n$ 候補を検討せず, $n=5$ にいきなり当てない. 不等式 $m^{2}\le 171n<m(m+1)$ から $n$ の範囲を絞る.

背景 — Beatty 数列と床関数の漸化式

$f_{n+1}(x)=x\lfloor f_{n}(x)\rfloor$ は階層的に増大する系列. $x>1$ では発散の速度が階乗的. これは無理数の連分数展開と関係し, 数論的解析が可能.

方針 — 文脈自由文法 vs 正則言語

CFG の表現力 $\supsetneq$ 正則言語 ($G_{1a}$ で示される). 一方, CFG の特殊形 (例: 線形 + 単一非終端再帰なし) は正則言語と一致 ($G_{1b}$).

あいまいさの解消は演算子優先順位と結合性の強制. 左再帰 ($S\to S+A$) で左結合, 階層化 ($S, A, F$) で優先順位を実装.

典型ミス

• (1) で長さ 5 の文字列を網羅的に列挙し損なう. $((a))$ を忘れがち.
• (4) で「規則数 6 以下」制約を超える. 階層 3 段にすると $\ge 7$ 規則になり, 階層 2 段で工夫.
• (5) $G_{1a}$ の Pumping 補題証明: $a$ を 1 つだけ含む文字列 $(^{n}a)^{n}$ を取って, $|xy|\le N$ で $y$ は左の括弧のみで, $xy^{2}z$ は左括弧過剰でバランス崩れる.

背景 — Chomsky 階層と式言語

• Type 3 (正則): DFA, 正則表現. $L(G_{1b})$.
• Type 2 (CFG): PDA, BNF. $L(G_{1a}), L(G_{1})$.
• Type 1 (文脈依存), Type 0 (チューリング機械).

四則演算式の文法は典型的な Type 2 で, 括弧バランスのために PDA (スタック) が必要.

方針 — CSMA/CD と BSC 直列

イーサネットの CSMA/CD は衝突検出のための時間予算を最小フレーム長で確保. 距離は信号往復時間と帯域から決定 (信号速度 $V$, 帯域 $C$, 最小フレーム $F_{\min}$).

BSC 直列はマルコフ連鎖の合成. 誤り率は $\varepsilon=\varepsilon_{1}+\varepsilon_{2}-2\varepsilon_{1}\varepsilon_{2}$ (XOR 確率).

典型ミス

• (1-2-2) で「往復時間 $2L/V$」と書いてしまう. 本問はB が検出するだけなので片道.
• (2-1) で和の対称性 $p(0|0)=p(1|1)$ を見落とすと項数が増える.
• (2-2) で「両方の偏微分」を取って最大化する必要. 一方だけだと不十分.

背景 — Shannon の通信路容量

BSC の通信路容量 $C=1-h(\varepsilon)$, $h(\varepsilon)=-\varepsilon\log_{2}\varepsilon-(1-\varepsilon)\log_{2}(1-\varepsilon)$ (Shannon). 直列 BSC では $\varepsilon$ が増加し $C$ が減少. 中継ホップ数が増えると容量が削られるため, 中継器でのエラー訂正が重要.

方針 — RL 過渡応答とバイナリカウンタ

(1) は1 階 RL 過渡応答. 初期値 + 終値 + 時定数で完結.

(2) はD-FF 同期式カウンタ. 状態遷移表から最小積和形を Karnaugh マップ等で導出.

典型ミス

• (1-1) で $i$ の符号. 図の矢印方向を確認.
• (1-3) で $\tau$ 計算. 等価抵抗は EMF を短絡 (内部抵抗 0) して $L$ 端から見る.
• (2-2) で「$Q_{2}$ も使う」と思って 3 変数 SOP を書く. 必要最小限で 2 変数に絞る.

背景 — Karnaugh マップと最小化

$K_{1}=Q_{1}\oplus Q_{0}$ は SOP 標準形だと 2 項. XOR は SOP の最小化形ではないが ((0,1) と (1,0) は隣接でないので括れない), 工学的にはこの 2 項形が最簡.

方針 — 畳み込み定理と相関フィルタ

LTI システムの伝達関数推定:

• 直接法 [1]: $H=\mathcal G/\mathcal F$. ノイズに弱い.
• 相関法 [2]: $H=\mathcal L[f*g]/\mathcal L[f*f]=R_{fg}/R_{ff}$. Wiener 最適フィルタの基礎.

これはシステム同定の標準手法. 入力 $f$ がホワイトノイズなら $R_{ff}\propto\delta$ で $H$ がインパルス応答に直結.

典型ミス

• (1) Fubini で積分順序交換するときの領域記述. $0\le\tau\le t$ から $0\le\tau<\infty,\tau\le t<\infty$.
• (2-1) で余分な三角関数項を消し損ねる. $\sin^{2}t\cos t$ の項が打ち消し合うことを丁寧に確認する.
• (2-2) で $\mathcal L[t\cdot\text{周期関数}]$ を $-d/ds$ で求める標準テクニック.

背景 — システム同定とパワースペクトル密度

実用システム同定では: $$H(\omega) = \frac{S_{fg}(\omega)}{S_{ff}(\omega)}\quad(\text{パワースペクトル密度の比})$$ が周波数領域 Wiener フィルタ. 本問の式 [2] は時間領域で書いたもの. $S_{fg}=\mathcal F\{R_{fg}\}$ (Wiener-Khinchin 定理).