院試hub

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

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

解説は全問、途中式と最終答は大問1問を無料で公開しています。PDFの収録範囲は商品ページで確認できます。原題の条件だけでは答えが一つに決まらないため、確定答案を収録していない箇所が1項目あります。各項目に対象の小問と収録範囲を記載しています。問題本文は含みません。

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

¥3,200

原題の条件だけでは答えが一つに決まらないため、確定答案を収録していない箇所が1項目あります。各項目に対象の小問と収録範囲を記載しています。

商品内容・見本・購入へ

第1問 アルゴリズムとプログラミング(キュー)

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

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

典型ミス

  • (2-1) で (A) と (B) を逆にする (条件 prev<d\text{prev}<d で続行). 不等号方向に注意.

  • (2-3) の挿入では、その時点で残っている要素だけと比較する。既に取り出した 33 を、後の 55 の挿入の比較対象へ戻さない。

  • (2-5) で「全部挿入」と単純化すると NMAX−1\mathtt{NMAX}-1 個で上限. それ以降の挿入と取出しの交互パターンを忘れる.

背景 — 二分ヒープと priority queue

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

第2問 計算機システムとシステムプログラム(HDD/ファイルシステム)

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

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

  • 連結リスト: 各空きブロックに「次の空きブロック」のポインタを格納. 先頭から取得. 利点: 隣接性なくても OK. 欠点: 連続領域確保が困難.

  • ビットマップ: 各ブロックに 1 ビット (空き/使用中). 利点: 連続領域検索が早い. 欠点: ブロック数が多いとマップサイズが嵩む.

  • Extent (階層): 大きな連続領域を 1 つのレコードで管理. 現代の ext4, NTFS など.

典型ミス

  • (1-1) (え) で「テラ = 101210^{12}」混同. 本問は 11 TB =109=10^{9} KB と明示. 計算結果は0.250.25 TB.

  • (2-1) で「先頭から 4 つ」を取り違える. 連結リストの順序 (3→6→8→5→⋯3\to 6\to 8\to 5\to\cdots) を忠実に.

  • (2-2) でブロック番号順に並べたビットマップと「ファイル B のリンク」を混同しない.

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

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

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

解答

(1-1) 記録領域の呼び名と容量

同じ表面の同心円上の記録領域はトラック、同じ半径にある全表面のトラックの集まりはシリンダ、ディスク側で読み書きする最小単位はセクタである。したがって、選択肢は順にF、E、Bとなる。

本問では1シリンダに2トラック、1トラックに1000セクタ、1セクタに4キロバイトがある。容量は各段階の個数と最後の容量を掛けて C=31250×2×1000×4=250000000 キロバイト C=31250\times2\times1000\times4 =250000000\ \text{キロバイト} となる。原題の換算 1 テラバイト=109 キロバイト1\ \text{テラバイト}=10^9\ \text{キロバイト} を使うと C=250000000109=0.25 テラバイト C=\frac{250000000}{10^9}=0.25\ \text{テラバイト} である。

(1-2) 1回転の時間から平均待ち時間を求める

10000回転毎分なので、1回転の所要時間 TT は T=60 s10000=6.0×10−3 s T=\frac{60\ \mathrm{s}}{10000}=6.0\times10^{-3}\ \mathrm{s} である。ヘッドの移動が終わった時点から目的の位置までの回転角を一様とすると、待ち時間は0から TT まで一様に分布する。その平均は t‾=∫0Tt1T dt=T2=3.0×10−3 s \overline{t}=\int_0^T t\frac{1}{T}\,dt =\frac{T}{2} =3.0\times10^{-3}\ \mathrm{s} となる。

(2-1) 空き領域のリンクを4個分たどる

ブロックの大きさは4キロバイトなので、15キロバイトのファイルBに必要なブロック数は n=⌈154⌉=4 n=\left\lceil\frac{15}{4}\right\rceil=4 である。原題の表2を、空き領域の先頭3から「次のブロック番号」に従って読むと 3⟶6⟶8⟶5⟶4⟶7⟶9⟶10⟶11⟶end 3\longrightarrow6\longrightarrow8\longrightarrow5 \longrightarrow4\longrightarrow7\longrightarrow9 \longrightarrow10\longrightarrow11\longrightarrow\mathrm{end} となる。最初の4個 3,6,8,53,6,8,5 をBへ割り当て、4個目の5の次をendへ変える。残りの空き領域は4から始まる。ファイルAの 0→1→2→end0\to1\to2\to\mathrm{end} は変わらない。

(2-2) ビットマップで小さい番号から割り当てる

必要な個数は前問と同じ4個である。ビット値1を空き、0を使用中とする。最初に0から2が使用中なので、番号の小さい順で最初に見つかる空き4個は 3,4,5,63,4,5,6 である。これらのビットを0へ変える。

ファイルBの先頭を3とし、データを読む順序は 3→4→5→6→end3\to4\to5\to6\to\mathrm{end} として表1の方式で記録する。

(2-3) 空きが減ると先頭からの探索はどう変わるか

空きブロックを見つけるまでに調べる使用中のビットが増えるため、探索時間は長くなる。この問題では毎回先頭から調べ、小さい番号の空きを使うので、ファイルの追加を続けるほど前方に使用中の0が連続して並ぶ。

最終答

(1-1) 記録領域の呼び名と容量

(あ) F:トラック、(い) E:シリンダ、(う) B:セクタ、(エ) 0.250.25。

(1-2) 1回転の時間から平均待ち時間を求める

3.0×10−3 s3.0\times10^{-3}\ \mathrm{s}。

(2-1) 空き領域のリンクを4個分たどる

ファイルAの先頭は0、ファイルBの先頭は3、空き領域の先頭は4。更新後の管理表は

ブロック

0

1

2

3

4

5

6

7

8

9

10

11

次

1

2

end

6

7

end

8

9

5

10

11

end

(2-2) ビットマップで小さい番号から割り当てる

ファイルAの先頭は0、ファイルBの先頭は3。ビットマップは

ブロック

0

1

2

3

4

5

6

7

8

9

10

11

空き状態

0

0

0

0

0

0

0

1

1

1

1

1

となる。ファイルを管理する次番号は、0→1→2→end0\to1\to2\to\mathrm{end} と 3→4→5→6→end3\to4\to5\to6\to\mathrm{end} である。

(2-3) 空きが減ると先頭からの探索はどう変わるか

先頭の空きビット1へ到達するまでの走査が長くなり、空き領域が多いときより探索時間が増える。

第3問 離散構造(床関数の漸化式)

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

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

(5)(6) でも、各段階の床値を整数 n=⌊fk(x)⌋n=\lfloor f_k(x)\rfloor と置き、n≤fk(x)<n+1n\le f_k(x)<n+1 と次段の fk+1(x)=xnf_{k+1}(x)=xn を同時に使う。候補の整数を選んだ後は、その候補を置いた区間へ戻して確かめる。

典型ミス

  • (3) で「全射でない」を示すには値域に穴があることを具体例で. 単に「値域が [0,∞)[0,\infty) でない」では不十分.

  • (4-2) 反対称性はk≠lk\ne lで双方向の関係が成り立たないこと. k=lk=l の自明ケースは反対称性に影響しない.

  • (6) で複数の nn 候補を検討せず, n=5n=5 にいきなり当てない. 不等式 m2≤171n<m(m+1)m^{2}\le 171n<m(m+1) から nn の範囲を絞る.

床関数を含む更新の増え方

x>1x>1 だけで発散や階乗的な増大は結論できない。例えば 1≤x<21\le x<2 では初項の床値が 11 となり、x⌊x⌋=xx\lfloor x\rfloor=x が繰り返される。特に x=3/2x=3/2 は何段進めても 3/23/2 のままである。床を取る前の値と整数部分を分けて追い、増え方を別の数列の名前から推測しない。

第4問 計算理論(文脈自由文法)

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

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

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

典型ミス

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

背景 — Chomsky 階層と式言語

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

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

第5問 ネットワーク(Ethernet と BSC)

方針 — CSMA/CD と BSC 直列

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

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

典型ミス

  • (1-2-2) で「往復時間 2L/V2L/V」と書いてしまう. 本問はB が検出するだけなので片道.

  • (2-1) で和の対称性 p(0∣0)=p(1∣1)p(0|0)=p(1|1) を見落とすと項数が増える.

  • (2-2) は他方の誤り率を固定した一変数の単調性でも証明できる。∂ε/∂ε1=1−2ε2≥0\partial\varepsilon/\partial\varepsilon_1=1-2\varepsilon_2\ge0 であり、ε1=1/2\varepsilon_1=1/2 の値は他方の値によらず 1/21/2 となる。両方の偏微分が必要という制限はない。

背景 — Shannon の通信路容量

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

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

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

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

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

典型ミス

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

背景 — Karnaugh マップと最小化

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

第7問 数学解析と信号処理(Laplace 変換と畳み込み)

一部の確定答案なし

原題の因果的な畳み込みと厳密なラプラス変換だけでは、二つの方法に同じ雑音項が残るため、一方が雑音に強いという確定答案を収録していません。加法雑音の反例と、相関法に必要な追加条件を説明しています。(1)・(2)の証明と計算は収録しています。

畳み込みと相関を区別する

原題の演算は因果的な畳み込み (f∗g)(t)=∫0tf(τ)g(t−τ) dτ(f*g)(t)=\int_0^t f(\tau)g(t-\tau)\,d\tau であり、相関関数そのものではない。ラプラス変換が収束し、積分順序を交換できる範囲では L[f∗g]=FG\mathcal L[f*g]=FG、L[f∗f]=F2\mathcal L[f*f]=F^2 となる。従って分母が零でない点では、式[2]の比も式[1]と同じ G/FG/F になる。

出力に雑音 nn が加われば、どちらの比にも同じ N/FN/F が残る。畳み込みを挟んだだけで雑音が小さくなる、あるいは分母零の問題を避けられるとはいえない。

積分順序と変換の条件

畳み込み定理の証明では、0≤τ≤t0\le\tau\le t の領域を 0≤τ<∞, τ≤t<∞0\le\tau<\infty,\ \tau\le t<\infty として積分順序を替える。絶対収束など、交換を許す条件を先に確かめる。時間を掛けた関数の変換には L[tf(t)]=−dF/ds\mathcal L[tf(t)]=-dF/ds を使えるが、この微分も積分内へ移せる収束範囲で行う。

雑音を抑える相関法の追加条件

実用の相関法は、定常性や雑音と入力が無相関である条件を加え、相互相関を期待値として定義して使う。その場合でも入力スペクトルが零の周波数を無条件に同定できるわけではない。原題の片側畳み込みを、そのまま Wiener 型の相関フィルタと呼んで雑音抑制を説明してはいけない。これらの追加条件を置く議論と、原題の式そのものから導けることを分ける。

PDFの収録範囲と資料制約を確認する

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

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

解答PDFの商品ページへ

年度別の解答例

  • 2025年度

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

  • 2024年度

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

  • 2023年度

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

  • 2022年度

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

  • 2021年度(このページ)

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

  • 2020年度

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

2021年度の出題内容

大問分野主題解説の小見出し最終答
第1問情報アルゴリズムとプログラミング(キュー)方針 — 循環バッファとシフト計算 / 背景 — 二分ヒープと priority queueあり
第2問情報計算機システムとシステムプログラム(HDD/ファイルシステム)方針 — 空き領域管理の 3 方式 / 背景 — トラック / シリンダ / セクタあり
第3問微分積分・解析離散構造(床関数の漸化式)方針 — 床関数と整数解探索 / 床関数を含む更新の増え方あり
第4問—計算理論(文脈自由文法)方針 — 文脈自由文法 vs 正則言語 / 背景 — Chomsky 階層と式言語—
第5問—ネットワーク(Ethernet と BSC)方針 — CSMA/CD と BSC 直列 / 背景 — Shannon の通信路容量あり
第6問電磁気学・回路電子回路と論理設計方針 — RL 過渡応答とバイナリカウンタ / 背景 — Karnaugh マップと最小化—
第7問数学数学解析と信号処理(Laplace 変換と畳み込み)畳み込みと相関を区別する / 積分順序と変換の条件一部の確定答案なし

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

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

大問数
2020年度 7問 → 2021年度 7問

2020年度の解答例

大阪大学の他の解答PDF

院試対策ガイド

大阪大学の公式過去問

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

大阪大学の公式過去問PDF