院試hub

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

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

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

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

¥3,200

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

商品内容・見本・購入へ

第1問 アルゴリズムとプログラミング(挿入ソート)

挿入ソートで見るべき場所

本問では, 探索方法を線形探索から二分探索に変えても, 配列で挿入ソートを実装している限り要素移動のコストが残る点が重要である. 探索だけを見ると O(nlog⁡n)O(n\log n) に見えやすいが, 代入によるシフトの総数は逆順入力で Θ(n2)\Theta(n^2) になる.

二分探索の終了位置

プログラム2は「同じ値があれば後ろに入れる」形の上側挿入位置を返す. 本問では整列対象がすべて異なる場合を考えるので, leftleft は単に keykey より小さい要素の個数と一致する. ループ終了後に rightright ではなく leftleft を使う理由は, leftleft が未確定区間の左端として挿入位置を表すからである.

解答

(1-1) 3回目の挿入後の配列

20行目は、取り出した値を挿入位置へ書き戻す命令であり、外側の反復ごとに1回実行される。先頭の1要素を整列済みとして、次の3個を順に挿入する。 i取り出す値挿入位置挿入後の配列140(4,8,5,1,2)251(4,5,8,1,2)310(1,4,5,8,2) \begin{array}{c|c|c|l} i&\text{取り出す値}&\text{挿入位置}&\text{挿入後の配列}\\\hline 1&4&0&(4,8,5,1,2)\\ 2&5&1&(4,5,8,1,2)\\ 3&1&0&(1,4,5,8,2) \end{array} 3回目には、既整列区間の 8,5,48,5,4 を右から順に1つずつ右へ移し、先頭へ1を入れる。

(1-2) 移動回数を最大にする入力

第 ii 回には、整列済みの ii 個のうち挿入する値より大きい要素だけを移す。したがって移動回数は高々 ii であり、取り出す値がそれ以前の全要素より小さいときに ii 回となる。各回でこの条件を満たす降順を選ぶ。

(1-3) 線形探索を使う場合の時間計算量

第 ii 回の探索と移動はそれぞれ高々 ii 回であり、定数時間の処理を除く総時間は ∑i=1n−1O(i)=O(n2) \sum_{i=1}^{n-1}O(i)=O(n^2) で抑えられる。降順入力では移動だけで n(n−1)/2n(n-1)/2 回必要なので、この上限と同じ次数の下限もある。

(2-1) 二分探索の更新式

探索開始時の区間は [left,right]=[0,i−1][left,right]=[0,i-1] である。中央で array[mid]>keyarray[mid]>key なら、初めて keykey を超える要素は midmid 以下にある。midmid は今回調べ終えたので、次はその左側を調べる。逆なら midmid 以下の値はすべて keykey 以下であり、右側へ進む。終了時には leftleft が挿入位置となる。

(2-2) 二分探索へ変更した全体の計算量

長さ ii の区間の二分探索には O(log⁡(i+1))O(\log(i+1)) 回の比較を要する。一方、配列の移動は変更されておらず、降順では依然として ii 回必要である。したがって T(n)=O ⁣(∑i=1n−1log⁡(i+1)+∑i=1n−1i)=O(n2). T(n)=O\!\left(\sum_{i=1}^{n-1}\log(i+1)+\sum_{i=1}^{n-1}i\right)=O(n^2).

(2-3) 比較回数を最小にする並び順

求めるのは図3の10行目の比較回数である。長さ ii の区間で中央を除いた左右の長さは ⌊i−12⌋,⌈i−12⌉ \left\lfloor\frac{i-1}{2}\right\rfloor,\qquad \left\lceil\frac{i-1}{2}\right\rceil となる。左側を選び続ければ、毎回、短い側または同じ長さの側へ進み、最少の比較回数で終了する。互いに異なる値を降順で与えれば、各回の keykey が整列済みの全要素より小さく、常に左側を選ぶ。

(2-4) 最小比較回数の閉じた式

各挿入で i=1,…,n−1i=1,\ldots,n-1 なので、(2-3)より cmin⁡=∑i=1n−1⌊log⁡2(i+1)⌋=∑j=2n⌊log⁡2j⌋. c_{\min}=\sum_{i=1}^{n-1}\lfloor\log_2(i+1)\rfloor =\sum_{j=2}^{n}\lfloor\log_2j\rfloor. k=⌊log⁡2n⌋k=\lfloor\log_2n\rfloor とおく。整数 jj について、⌊log⁡2j⌋\lfloor\log_2j\rfloor は、条件 2r≤j2^r\le j を満たす r≥1r\ge1 の個数である。和の順序を入れ替えると cmin⁡=∑r=1k∑j=2rn1=∑r=1k(n−2r+1)=k(n+1)−(2k+1−2). c_{\min}=\sum_{r=1}^{k}\sum_{j=2^r}^{n}1 =\sum_{r=1}^{k}(n-2^r+1) =k(n+1)-(2^{k+1}-2).

最終答

(1-1) 3回目の挿入後の配列

(array[0],array[1],array[2],array[3],array[4])=(1,4,5,8,2)(array[0],array[1],array[2],array[3],array[4])=(1,4,5,8,2)。

(1-2) 移動回数を最大にする入力

入力の1行目を5とし、続く5行を順に 8,5,4,2,18,5,4,2,1 とする。18行目の実行回数は 1+2+3+4=101+2+3+4=10 回。

(1-3) 線形探索を使う場合の時間計算量

選択肢は O(n2)O(n^2)。最悪時間は Θ(n2)\Theta(n^2) である。

(2-1) 二分探索の更新式

(A)=mid−1,(B)=mid+1,(C)=left(A)=mid-1,\quad(B)=mid+1,\quad(C)=left。

(2-2) 二分探索へ変更した全体の計算量

O(n2)O(n^2)。比較の総数は O(nlog⁡n)O(n\log n) だが、最悪時の移動が Θ(n2)\Theta(n^2) となる。

(2-3) 比較回数を最小にする並び順

元の入力を狭義降順にすることが、cc を最小にする十分条件の一つである。

(2-4) 最小比較回数の閉じた式

cmin⁡=k(n+1)−2k+1+2,k=⌊log⁡2n⌋(n>1)c_{\min}=k(n+1)-2^{k+1}+2,\quad k=\lfloor\log_2n\rfloor\quad(n>1)。

第2問 計算機システムとシステムプログラム(メモリ管理)

オーバーレイは最大同時使用量を見る

オーバーレイでは, 全モジュールを常駐させる必要はない. ただし, 実行のある時点で同時に必要になるモジュール群は同時に主記憶上へ置けなければならない. そのため, 各組合せの合計の最大値が最低必要容量になる.

Beladyの異常の判定

Beladyの異常は「ページ枠を増やしたのにページフォールトが増える」現象である. 本問のFIFOでは, 2枠から3枠で 10→910\to9, 3枠から4枠で 9→99\to9, 4枠から5枠で 9→59\to5 であり, 増加がない. したがって, 選択肢は「確認できなかった」と判断する.

第3問 離散構造

同型判定では不変量で候補を減らす

グラフ同型を調べるときは, いきなり全単射を探すより, 次数列, 辺数, 三角形数, 連結成分, 補グラフなどの同型不変量で候補を絞るのが確実である. 不変量が違えば同型ではない. 一方で, 不変量が同じだけでは同型とは限らないため, 最後に具体的な対応を示す必要がある.

ラベル付きと非同型代表元の違い

Gn\mathcal{G}_n は頂点ラベルを固定したグラフ全体なので, 辺の有無を選ぶだけで 2(n2)2^{\binom{n}{2}} 個になる. これに対して In\mathcal{I}_n は同型なものを1つにまとめた代表元集合である. 同じ形のグラフでもラベルの付け替えによって高々 n!n! 個のラベル付きグラフができる, という見方が(2-4)の下界証明の中心である.

下界の意味

(2-4)の不等式は, 非同型な単純無向グラフの種類数が非常に大きいことを示している. 代表元数を正確に数えるにはBurnsideの補題などが有効だが, 本問では「各同型類の大きさは高々 n!n!」という粗い上界だけで十分な指数的下界が得られる.

第4問 計算理論

Chomsky標準形へ直すときの注意

本問では, 元の文法に空語生成と無用記号が混ざっている. そのまま機械的に規則を書き換えると, BB のように終端記号列を一切生成できない変数や, ε\varepsilon を経由する規則が残りやすい. 最初に言語の形を読み取り, 空語だけを除いてから, 必要な非空の基底を別規則で用意すると見通しがよい.

CYK表の読み方

Q[i][j]Q[i][j] は「部分列 ai⋯aja_i\cdots a_j を生成できる変数の集合」である. 長さ1は終端規則 X→aiX\to a_i だけで埋まり, 長さ2以上は分割位置 kk をすべて試して, 左半分を作る変数と右半分を作る変数を組み合わせる. そのため, 表を作るときは対角線から右上へ, 短い区間から長い区間へ埋めるのが基本である.

正当性証明の核

CYK法の正当性は, Chomsky標準形の「最初の一手」が必ず X→YZX\to YZ または X→aX\to a であることに依存している. 長さ1なら終端規則を見るだけでよい. 長さ2以上なら, 構文木の根の直下で文字列が左右2つの連続区間に分かれるので, その分割位置を全探索すればよい. これが(2)の同値性の理由であり, (3)の判定条件にも直結する.

節点数は終端葉も数える

(4)で 3n−13n-1 になるのは, 終端記号の葉だけでなく, その直上の変数節点も別に数えるからである. 変数だけを数えると 2n−12n-1 個であり, 終端記号の葉 nn 個を足して 3n−13n-1 個になる. n=1n=1 の場合も, 開始変数と終端葉の2個なので 3⋅1−1=23\cdot1-1=2 と一致する.

第5問 ネットワーク

一部の確定答案なし

原題にCSMAの持続方式の指定がなく,空欄Bは1持続型なら(ア),非持続型なら(イ)です。方式を定めた条件付きの解答と,他の設問の解答を収録しています。

CSMA の要点

CSMA は「送る前に聞く」方式である. ただし, 聞いているのは自分の位置で観測できる媒体状態であって, ネットワーク全体の真の状態ではない. 有線でも信号の伝搬には時間がかかるので, 伝搬遅延が大きいほど「相手の送信開始がまだ届いていない」時間が長くなる. この時間幅を衝突が起こりやすい脆弱期間として理解すると, (2) の説明を書きやすい.

CSMA/CD と無線の違い

CSMA/CD は Ethernet の古典的な共有媒体で重要な考え方であり, 衝突を検出したら送信を止めて再送へ回る. 一方, 無線では送信しながら同時に弱い受信信号を正確に検出することが難しく, さらに隠れ端末のように送信側では衝突原因を観測できない場合がある. そのため無線 LAN では衝突検出ではなく, 衝突回避(CSMA/CA)や RTS/CTS による予約が重要になる.

隠れ端末問題の答案で落としやすい点

(3-1) では「端末1と端末2が遠い」だけでは不十分である. 採点上は, キャリアセンスでは互いの送信を検出できない ことと, 共通の受信先である端末3ではフレーム衝突が起こる ことを両方書く必要がある. 問題文が指定している二つの語句をただ並べるのではなく, 送信開始から衝突までの因果を一文ずつ追うと答案が安定する.

RTS/CTS の効き方

RTS/CTS は送信者どうしが互いを聞けない状況で, 受信者の応答を周囲に聞かせる仕組みである. この問題の配置では, 端末1と端末2は互いを受信できないが, 中央の端末3には双方が届く. したがって端末3が送る CTS を端末2が聞き, 「いま端末3は端末1との通信を予約している」と判断して送信を控える. この説明まで書けると, 単に用語名を答えるより強い答案になる.

検算的な見方

RTS/CTS が常に性能を上げるわけではない. 制御フレームの交換自体がオーバーヘッドになるため, 短いデータフレームや隠れ端末が少ない環境では不利になることもある. しかし本問では隠れ端末によるデータフレーム衝突を避ける目的なので, 大きなデータフレームの衝突を短い制御フレームの予約で防ぐ, という利点を中心に述べればよい.

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

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

二端子対回路の符号規約

縦続行列では電流の向きの規約で符号が変わることがある. 本問の図では I1,I2I_1,I_2 がどちらも左から右向きに描かれているため, [V1I1]=F[V2I2] \begin{bmatrix}V_1\\ I_1\end{bmatrix} = F \begin{bmatrix}V_2\\ I_2\end{bmatrix} と読むと, 直列素子は [1Z01]\begin{bmatrix}1&Z\\0&1\end{bmatrix}, 並列素子は [10Y1]\begin{bmatrix}1&0\\Y&1\end{bmatrix} になる. 出力ポート電流を「回路へ流れ込む向き」に取る別流儀とは B,CB,C などの符号が変わり得るので, 図の矢印を先に確認するのが安全である.

平均電力式の見通し

(1-2) は全回路の入力インピーダンスを一気に出してもよいが, 右端の抵抗電圧 VV を基準にして左へ戻ると計算が短い. 抵抗の平均電力は P=∣V∣2/RP=|V|^2/R なので, 最終的に E/VE/V の絶対値二乗を求めればよい. 実部が 1−3ω2LC+ω4L2C21-3\omega^2LC+\omega^4L^2C^2, 虚部が (ωL/R)(2−ω2LC)(\omega L/R)(2-\omega^2LC) になるため, 問題の形 E2P=(1+x)2R+ω2L2(2−y)2R \frac{E^2}{P} = (1+x)^2R+\frac{\omega^2L^2(2-y)^2}{R} と係数を比較すれば空欄が決まる.

カルノー図のまとめ方

5変数のカルノー図は2枚の4変数カルノー図として扱う. ドントケアを使えるため, x1=x0=0x_1=x_0=0 の列を x4x_4 側も含めて大きくまとめられる. これが x1‾x0‾\overline{x_1}\overline{x_0} であり, 本問の簡単化で最も大きなまとまりである. 残る 30,3130,31 の1は x0x_0 だけが違う隣接2マスとしてまとめ, x4x3x2x1x_4x_3x_2x_1 を得る.

NAND 実装での採点ポイント

積和形をそのまま AND/OR/NOT で描くと, 2入力 NAND のみという条件を満たさない. NAND だけで OR を作る基本は A+B=NAND⁡(A‾,B‾) A+B=\operatorname{NAND}(\overline{A},\overline{B}) である. したがって, A=x4x3x2x1A=x_4x_3x_2x_1 については A‾\overline{A} を NAND で作り, B=x1‾x0‾B=\overline{x_1}\overline{x_0} については B‾=x1+x0\overline{B}=x_1+x_0 を NAND で作って, 最後にもう一度 NAND に入れる. 上の構成はゲート数が9個なので, 指定された上限内に収まる.

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

正則関数の線積分

f(z)=z2f(z)=z^2 は原始関数 z3/3z^3/3 を持つ. したがって, 始点と終点が同じなら経路の形に依存しない. (1-1) で直接計算を求められている場合でも, 計算結果が端点だけで決まることを知っていると符号確認が楽になる. 本問では C1C_1 と C2C_2 の向きが逆向きに対応しているので, I1=−I2I_1=-I_2 になる.

コーシーの積分定理と留数定理の使い分け

コーシーの積分定理を使える条件は, 被積分関数が閉曲線の内部と境界で正則であることだ. z2z^2 では問題ないが, 1/(z4+1)1/(z^4+1) では囲まれた領域内に極がある. この場合は積分が0になるのではなく, 内部の極の留数が積分値を決める. 極がどの領域に入るかを図で確認してから定理を選ぶのが重要である.

逆フィルタの安定性

伝送路 SS は2タップ遅延を含む FIR フィルタであり, それ自体は安定である. しかし逆フィルタ T=1/HST=1/H_S は一般に IIR になる. 逆フィルタが安定かどうかは, HSH_S の零点, すなわち HTH_T の極が単位円内にあるかで判定する. 本問では極の半径が 1/21/2 なので, 因果的に実装しても単位円が収束領域に入り, BIBO 安定となる.

振幅特性の読み方

HS(eiω)=1+12e−iω+14e−2iωH_S(e^{\mathrm{i}\omega})=1+\frac12e^{-\mathrm{i}\omega}+\frac14e^{-2\mathrm{i}\omega} は, 近傍サンプルを正の重みで足すので平滑化の性質を持つ. その逆 HTH_T は平滑化で弱められた成分を戻すため, 相対的には高域を持ち上げる. 極の角度 ±2π/3\pm2\pi/3 と振幅の厳密な最大位置は異なる。c=cos⁡ωc=\cos\omega とおくと ∣HS(eiω)∣2=c2+54c+1316=(c+58)2+2764 |H_S(e^{\mathrm{i}\omega})|^2 =c^2+\frac54c+\frac{13}{16} =\left(c+\frac58\right)^2+\frac{27}{64} なので,∣HT∣=1/∣HS∣|H_T|=1/|H_S| が最大になるのは ω=±arccos⁡(−5/8)\omega=\pm\arccos(-5/8) である。原題の用語集にこの厳密値はなく,±2π/3\pm2\pi/3 は極の角度を使う近似として区別する。

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

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

解答PDFの商品ページへ

年度別の解答例

  • 2025年度

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

  • 2024年度(このページ)

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

  • 2023年度

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

  • 2022年度

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

  • 2021年度

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

  • 2020年度

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

2024年度の出題内容

大問分野主題解説の小見出し最終答
第1問情報アルゴリズムとプログラミング(挿入ソート)挿入ソートで見るべき場所 / 二分探索の終了位置あり
第2問情報計算機システムとシステムプログラム(メモリ管理)オーバーレイは最大同時使用量を見る / Beladyの異常の判定あり
第3問—離散構造同型判定では不変量で候補を減らす / ラベル付きと非同型代表元の違いあり
第4問—計算理論Chomsky標準形へ直すときの注意 / CYK表の読み方あり
第5問—ネットワークCSMA の要点 / CSMA/CD と無線の違い一部の確定答案なし
第6問電磁気学・回路電子回路と論理設計二端子対回路の符号規約 / 平均電力式の見通しあり
第7問数学数学解析と信号処理正則関数の線積分 / コーシーの積分定理と留数定理の使い分けあり

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

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

大問数
2023年度 7問 → 2024年度 7問

2023年度の解答例

大阪大学の他の解答PDF

院試対策ガイド

大阪大学の公式過去問

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

大阪大学の公式過去問PDF