院試hub

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

大学
大阪大学
研究科・専攻
情報科学研究科
科目
専門科目(情報工学)
年度
2023年度

解説は全問、途中式と最終答は大問1問を無料で公開しています。PDFの収録範囲は商品ページで確認できます。問題本文は含みません。

大阪大学 情報科学研究科 専門科目(情報工学)の解答PDF2020〜2026年度(7年度)

¥3,200

商品内容・見本・購入へ

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

開番地法の停止条件

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

cuckoo hashing の見方

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

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

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

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

アドレス変換の確認

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

解答

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

仮想メモリは 1 GB=2301\,\mathrm{GB}=2^{30} byte なので, バイトアドレスを指定する仮想アドレス長は v=30 v=30 ビットである. 物理メモリは 128 MB=227128\,\mathrm{MB}=2^{27} byte なので, 物理アドレス長は p=27 p=27 ビットである. ページサイズは 4 KB=2124\,\mathrm{KB}=2^{12} byte だから, ページ内オフセットは f=12 f=12 ビットである. よって仮想ページ番号は 30−12=1830-12=18 ビットで, 仮想ページ数は n=18,218 ページ n=18,\qquad 2^{18}\text{ ページ} となる.

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

物理ページ数は 227212=215 \frac{2^{27}}{2^{12}}=2^{15} である. したがって物理ページ番号に必要なビット数は 1515 ビットである.

(2-2) アドレス変換

ページサイズが 2122^{12} byte なので, 仮想アドレス 0xF0090\mathrm{xF009} は 仮想ページ番号=0xF,オフセット=0x009 \text{仮想ページ番号}=0\mathrm{xF},\qquad \text{オフセット}=0\mathrm{x009} に分かれる. 表では仮想ページ番号 0xF0\mathrm{xF} に対応する物理ページ番号が 0x140\mathrm{x14} である. よって物理アドレスは (0x14≪12)+0x009=0x14009. (0\mathrm{x14}\ll 12)+0\mathrm{x009} =0\mathrm{x14009}.

(2-3) dirty bit の役割

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

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

ページサイズを 8 KB=2138\,\mathrm{KB}=2^{13} byte にすると, f=13,n=30−13=17. f=13,\qquad n=30-13=17. 物理ページ番号は 27−13=14 27-13=14 ビットで表せる. 各エントリには X,YX,Y の2ビットと物理ページ番号14ビットが必要なので, 1エントリは16ビット, すなわち2 byte である. エントリ数は 2172^{17} 個だから, 全体の容量は 217×2=218 byte=256 KB. 2^{17}\times 2=2^{18}\text{ byte}=256\,\mathrm{KB}.

最終答

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

第3問 離散構造

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

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

三角形判定の要点

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

第4問 計算理論

正則かどうかの判断

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

演算子文法の作り方

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

第5問 ネットワーク

鋸歯状モデル

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

近似で落とさない点

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

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

CMOS は双対性を見る

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

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

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

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

線形位相の見方

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

移動平均の零点

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

専門科目(情報工学)の解答・解説PDF

2020〜2026年度(7年度) · ¥3,200

解答PDFの商品ページへ

年度別の解答例

  • 2025年度

    アルゴリズムとプログラミング(二分ヒープ) / 計算機システムとシステムプログラム(パイプライン) / 離散構造(グラフ彩色と削除・縮約)

  • 2024年度

    アルゴリズムとプログラミング(挿入ソート) / 計算機システムとシステムプログラム(メモリ管理) / 離散構造

  • 2023年度(このページ)

    アルゴリズムとプログラミング / 計算機システムとシステムプログラム / 離散構造

  • 2022年度

    アルゴリズムとプログラミング / 計算機システムとシステムプログラム / 離散構造

  • 2021年度

    アルゴリズムとプログラミング(キュー) / 計算機システムとシステムプログラム(HDD/ファイルシステム) / 離散構造(床関数の漸化式)

  • 2020年度

    アルゴリズムとプログラミング / 計算機システムとシステムプログラム / 離散構造

2023年度の出題内容

大問分野主題解説の小見出し最終答
第1問情報アルゴリズムとプログラミング開番地法の停止条件 / cuckoo hashing の見方あり
第2問情報計算機システムとシステムプログラム単位換算を先に指数へ直す / アドレス変換の確認あり
第3問—離散構造行列の冪が歩道を数える理由 / 三角形判定の要点あり
第4問—計算理論正則かどうかの判断 / 演算子文法の作り方あり
第5問—ネットワーク鋸歯状モデル / 近似で落とさない点あり
第6問電磁気学・回路電子回路と論理設計CMOS は双対性を見る / 交流回路は実効値フェーザで統一するあり
第7問数学数学解析と信号処理線形位相の見方 / 移動平均の零点あり

同じテーマを出した他大学・他年度

前年度(2022年度)との違い

大問数
2022年度 7問 → 2023年度 7問
2023年度で新しく出たテーマ
群論・環論・オートマトン理論

2022年度の解答例

大阪大学の他の解答PDF

院試対策ガイド

大阪大学の公式過去問

公開年度範囲
専攻・科目別に掲載(情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など)
公式の解答例
解答例の掲載なし
英語の扱い
2027年4月一般は情報基礎数学のみ90分の独自英語。情報科学専攻は2024年7月以降のTOEIC公開スコア、提出困難ならTOEFL。IP・ITP不可。

大阪大学の公式過去問PDF