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

> 阪大 情報科学研究科 専門科目（情報工学） 2023年度の院試過去問、7項目の解説。テーマは群論・環論、オートマトン理論。大問1問の途中式・最終答を無料公開。解答PDFは7年分収録で3,200円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering/2023
- 解答・解説PDF: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering（税込3,200円、7年分を収録）
- 最終更新: 2026-11-19
- 公式の過去問: https://www.ist.osaka-u.ac.jp/japanese/examinees/admission/past-exam.php（専攻・科目別に掲載（情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など）、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — アルゴリズムとプログラミング

### 解説

**開番地法の停止条件**

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

**cuckoo hashing の見方**

方式2では，各キーの二つの候補セルへ辺を張って挿入先を考えられる。ただし，閉路が一つあるだけでは格納不能とはいえない。閉路上の辺を各セルへ一つずつ割り当てられる場合もある。原題の $28$ の追加では，$8,22,2,18,28$ の5キーの候補が第1表の添字2と8，第2表の添字1と7の4セルに限られる。5個を4箇所へ一つずつ置くことはできないので，原題の追い出し操作は空セルに到達しない。例えば $28$ が第1表の添字8で $8$ を追い出し，$8$ が第2表の添字 $8\oplus3=11\equiv1\pmod{10}$ で $2$ を追い出し，$2$ が第1表の添字2で $22$ を追い出す。候補セル数の不足と，実際に追い出す順序を合わせて確認する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

## 第2問 — 計算機システムとシステムプログラム

### 解説

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

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

**アドレス変換の確認**

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

### 解答

**(1) アドレス長とページ数**

仮想メモリは $1\,\mathrm{GB}=2^{30}$ byte なので, バイトアドレスを指定する仮想アドレス長は

$$
v=30
$$

ビットである. 物理メモリは $128\,\mathrm{MB}=2^{27}$ byte なので, 物理アドレス長は

$$
p=27
$$

ビットである. ページサイズは $4\,\mathrm{KB}=2^{12}$ byte だから, ページ内オフセットは

$$
f=12
$$

ビットである. よって仮想ページ番号は $30-12=18$ ビットで, 仮想ページ数は

$$
n=18,\qquad 2^{18}\text{ ページ}
$$

となる.

**(2-1) 物理ページ番号のビット数**

物理ページ数は

$$
\frac{2^{27}}{2^{12}}=2^{15}
$$

である. したがって物理ページ番号に必要なビット数は $15$ ビットである.

**(2-2) アドレス変換**

ページサイズが $2^{12}$ byte なので, 仮想アドレス $0\mathrm{xF009}$ は

$$
\text{仮想ページ番号}=0\mathrm{xF},\qquad
  \text{オフセット}=0\mathrm{x009}
$$

に分かれる. 表では仮想ページ番号 $0\mathrm{xF}$ に対応する物理ページ番号が $0\mathrm{x14}$ である. よって物理アドレスは

$$
(0\mathrm{x14}\ll 12)+0\mathrm{x009}
  =0\mathrm{x14009}.
$$

**(2-3) dirty bit の役割**

列 $Y$ は, ページが物理メモリ上で更新されたかどうかを表す dirty bit と解釈できる. ページ置換で物理ページを追い出すとき, $Y=0$ なら二次記憶上の内容と同じなので書き戻しを省略できる. $Y=1$ のときだけ書き戻せばよいため, 不要な入出力を避けられ, ページ置換処理が高速化される.

**(2-4) ページサイズ変更後の表サイズ**

ページサイズを $8\,\mathrm{KB}=2^{13}$ byte にすると,

$$
f=13,\qquad n=30-13=17.
$$

物理ページ番号は

$$
27-13=14
$$

ビットで表せる. 各エントリには $X,Y$ の2ビットと物理ページ番号14ビットが必要なので, 1エントリは16ビット, すなわち2 byte である. エントリ数は $2^{17}$ 個だから, 全体の容量は

$$
2^{17}\times 2=2^{18}\text{ byte}=256\,\mathrm{KB}.
$$

### 最終答

$v=30,\ p=27,\ f=12,\ n=18$. 物理ページ番号は15ビット. $0\mathrm{xF009}$ の変換後アドレスは $0\mathrm{x14009}$. ページサイズを8KBにすると表サイズは $256\,\mathrm{KB}$.

## 第3問 — 離散構造

### 解説

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

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

**三角形判定の要点**

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

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

## 第4問 — 計算理論

### 解説

**正則かどうかの判断**

スタックに積んだ個数を後から同じ個数だけ照合する言語は, 典型的に非正則である. 図(a)は全体の $a,b$ の個数が等しいことに加え，どの接頭辞でも $a$ の個数が $b$ 以上という条件を要求する。$a$ を読むとスタックへ0を積み，$b$ を読むと取り除くので，途中で不足せず最後に差が0になる条件である。$abab$ も受理され，$a^nb^n$ だけには限られない。図(d)は前半列全体を逆順に照合する。両者の非正則性を主張するには，有限個の例だけでなく反復補題などの証明を使う。

**演算子文法の作り方**

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

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

## 第5問 — ネットワーク

### 解説

**鋸歯状モデル**

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

**近似で落とさない点**

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

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

## 第6問 — 電子回路と論理設計

### 解説

**CMOS は双対性を見る**

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

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

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

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

## 第7問 — 数学解析と信号処理

### 解説

**線形位相の見方**

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

**移動平均の零点**

$N$ 点平均は長さ $N$ の矩形窓で平均するフィルタである. 周波数応答は正弦の比で表され，$N\ge2$ なら $\omega=2\pi k/N$（$k$ は $N$ の倍数でない整数）で零点を持つ。$2\pi$ の整数倍は分子と分母が同時に0となり，元の有限和からゲイン1へ連続に補う。$N=1$ には零点がない。 $N$ を大きくすると最初の零点が低周波側へ移り，平均する時間幅と遅れが増える。必要な信号成分まで弱めることもある。ただし，全周波数で振幅が $N$ とともに単調に減るという意味ではない。例えば $\omega=\pi$ で，2点平均の振幅は0だが3点平均は $1/3$ である。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering

---

出典: 院試hub（https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering/2023）。引用するときはWeb版のURLを示してください。
