院試hub

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

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

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

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

¥3,200

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

商品内容・見本・購入へ

第1問 アルゴリズムとプログラミング(二分ヒープ)

方針 — 二分ヒープのインバリアントを言葉と式で押さえる

二分ヒープでは「形(complete に近い形)」と「順序(親が子以下/以上)」の二つの不変条件を分けて考えるとミスが激減する. 本問では特性2 が形, 特性1 が順序であり,

  • 値追加 (add, up): 形を崩さずに葉の位置に値を加え, 後から up-heap で順序を整える.
  • 値削除 (del, down): 根を末尾葉と入れ替えて取り除き, 形を保ったまま down-heap で順序を整える.

の二つで実装される. replace はこの中間で, 値を上書きしてから up か down を 1 度だけ走らせる.

なぜ 1-indexed か

このコードのように data[0] を要素数の格納に使い, 1 から始める実装は, 親 =⌊i/2⌋=\lfloor i/2\rfloor, 左子 =2i=2i, 右子 =2i+1=2i+1 という整数演算が破綻なく成立する点で都合がよい. 0-indexed だと根の親が −1/2=0-1/2 = 0 になり混乱しやすい. このコード上での「インデックス境界条件」は 1 <= index <= data[0] と覚えておく.

下方ヒープ化での子選択ロジック

down の核は「より小さい(交換すべき)子を選ぶ」処理である. 右子が無いとき(深さ hh の左寄せの境界)はもちろん左子と比較しなければならず, さらに左子と右子を比較して小さい方を選ぶ. 本問では右子の不在判定 z > data[0] を OR で結んだうえで, 通常の比較 data[y]<data[z] を行うことで両ケースを統一している. この書き方は実装でよく使われるイディオムである.

典型ミス

  • (2-1) で順序を取り違える. add は data[0]++ した後に data[data[0]] に値を入れる(末尾追加)→ up. 「インデックスを増やしてから格納する」順序を必ず守ること.
  • 88 の挿入で根まで上がるのを止めてしまう. 親 9>89 > 8 なので, 根 99 と入れ替えて根が 88 になる. ここで止めずに i=1 に達したかでループ終了を判定する.
  • 特性2 の最小数を 2h−12^{h-1} や 2h−12^{h}-1 と書く. 高さ hh の最小は「深さ h−1h-1 までの完全二分木+深さ hh に 1 節点」であり 2h2^{h}. 高さ 1 の特殊例(節点 2 個)もこの式に整合する.
  • replace で up と down を両方呼ぶ. 値が変わった節点は「親より小さくなる」か「子より大きくなる」かのどちらか一方しか起こり得ない. 同時に呼ぶ必要は無いし, 同時に呼ぶと無駄な比較が発生する.

検算 — 最終ヒープの妥当性チェック

(2-1) の最終配列が最小ヒープであることは, i=1,…,5i=1,\dots,5 について data[i]≤data[2i]\mathtt{data}[i] \le \mathtt{data}[2i] と data[i]≤data[2i+1]\mathtt{data}[i] \le \mathtt{data}[2i+1] が成り立つかを確かめれば十分である. i12345data[i]89361639data[2i]916656064data[2i+1]36393917— \begin{array}{c|cccccc} i & 1 & 2 & 3 & 4 & 5 \\\hline \mathtt{data}[i] & 8 & 9 & 36 & 16 & 39 \\ \mathtt{data}[2i] & 9 & 16 & 65 & 60 & 64 \\ \mathtt{data}[2i+1] & 36 & 39 & 39 & 17 & \text{---} \end{array} すべて data[i]≤data[2i]\mathtt{data}[i] \le \mathtt{data}[2i] かつ data[i]≤data[2i+1]\mathtt{data}[i] \le \mathtt{data}[2i+1] なので最小ヒープ.

オーダの直感

二分ヒープの高さは Θ(log⁡n)\Theta(\log n). 1 回の up/down で訪れる節点はせいぜい根から葉までの 1 経路であるため, 比較・交換とも O(log⁡n)O(\log n). これが「優先度付きキューに対する対数時間操作」という二分ヒープの主張の根拠である.

第2問 計算機システムとシステムプログラム(パイプライン)

方針 — 「クロック時間 ×\times CPI」を分けて考える

パイプライン化はクロック周波数の向上と引き換えに CPI\mathrm{CPI} を悪化させる. 平均命令時間 Tavg=Tclk⋅CPIT_{\text{avg}} = T_{\text{clk}}\cdot \mathrm{CPI} を 2 つの要因の積として捉えると, 段数 nn を増やしすぎたときに何が起こるかが見えやすい.

  • Tclk(n)=900/n+40T_{\text{clk}}(n)=900/n+40: 段数を増やすほどクロック周期は短くなるが, 40 ps のレジスタ遅延が下限を作る.
  • CPI(n)=0.1 n+0.64\mathrm{CPI}(n)=0.1\,n + 0.64: 段数増でハザードペナルティが線形に増える.

Tclk⋅CPIT_{\text{clk}}\cdot \mathrm{CPI} は nn について凸であり, 中間に最小がある((1-4) で n=12n=12).

なぜ 4n+576/n4n + 576/n の形になるか

TavgT_{\text{avg}} の中で nn を含む項を整理すると (900n+40)(0.1n+0.64)=90+576n+4n+25.6 \Bigl(\tfrac{900}{n}+40\Bigr)(0.1n+0.64) = 90 + \tfrac{576}{n} + 4n + 25.6 で, nn に依存する部分は 4n+576/n4n + 576/n のみ. AM-GM 不等式から 4n+576n≥24n⋅576n=22304=96, 4n + \frac{576}{n} \ge 2\sqrt{4n \cdot \tfrac{576}{n}} = 2\sqrt{2304} = 96, 等号は 4n=576/n⇔n=124n = 576/n \Leftrightarrow n=12 で成立. 同じ答えが導けるので検算に使える.

ロードユースの直感

lw は EX(アドレス計算)→\to MA(メモリアクセス)の流れで, 値が確定するのは MA 終了時点. 直後の命令(間隔 1)の EX とロードの MA は同じサイクルになるため, 「同じクロックサイクルで EX 入力に渡す」フォワーディング(MA 入力 →\to EX 入力)では間に合わない. 1 サイクル後に値は WB 入力として保持されているので, そこからのフォワーディングで間に合う. 結局 lw の直後にレジスタ依存があると 1 ストール必要, というのが固定の知識として使える.

典型ミス

  • (1-3) で総時間 250.8 m250.8\,m と書く. 単位が「ピコ秒/命令」になる量を mm 倍した「全 mm 命令の総時間」と取り違えやすい. 平均実行時間は CPI×Tclk\mathrm{CPI}\times T_{\text{clk}} で十分.
  • (1-4) で連続値の最小 n=12n=12 をそのまま書く前に整数性を確認しないこと. 段数は整数なので, 隣の整数と値を比較して最終的に n=12n=12 を選ぶ手続きが必要.
  • (2-1)(2-2) で IF と ID の順番を入れ替える. ストール時にどのステージを再実行するかは設計に依存. 本問は「IF と ID をやり直す」と明示されているので, 後ろの命令の IF, 当該命令の ID をそれぞれ 2 サイクル分書くのが正しい.
  • (2-3) 命令列 A で「lw と sw を入れ替える」と提案する. sw は lw のロード結果 r7 をアドレスに使うので, 入れ替えると意味が変わってしまう.

検算 — クロック数の数え方

ステージ表の総クロック数は「最初の命令の IF 開始から最後の命令の WB 終了までのサイクル数」. パイプライン段数 KK ステージ, ストール総数 ss, 命令数 mm のとき 総サイクル数=(K−1)+m+s. \text{総サイクル数} = (K-1) + m + s. 本問は K=5K=5, m=4m=4. 命令列 A: 4+4+1=94 + 4 + 1 = 9. 命令列 B: 同じく 9. リオーダ後の B: 4+4+0=84+4+0 = 8. 上の表と整合.

別解 — AM-GM での (1-4)

微分が苦手なら AM-GM が早い. 4n4n と 576/n576/n の積は nn に依らず 4⋅576=23044 \cdot 576 = 2304 なので和の最小は両者が等しいときに達成され, n=12n=12. 解析的最適化を整数に丸める処理は同じ.

第3問 離散構造(グラフ彩色と削除・縮約)

彩色の下限と実際の塗り分け

奇閉路を含まないことと二部グラフであることは同値である。辺を一つでも持つ二部グラフは、両端で異なる二色を必要とし、二部の各側を同色にすれば二色で足りる。クリーク数は彩色数の下限になり、KtK_t を部分グラフに持てば少なくとも tt 色が要る。

原図の G1G_1 は中心から三つの葉へ辺が伸びる木で、葉同士の辺はない。三角形を補って三色とすることはできない。G2G_2 は四角形で二色、G3=K4−eG_3=K_4-e は三角形を含むので三色以上で、隣接しない二頂点を同色にすれば三色で足りる。G4=K4G_4=K_4 は四色を要する。この下限と具体的な塗り分けを組み合わせて判定する。

二部の大きさと最大辺数

二部を A,BA,B とすると辺は両側の組にしか作れないので、辺数は高々 ∣A∣∣B∣|A||B|。∣A∣+∣B∣=n|A|+|B|=n に対して ∣A∣∣B∣=n2−(∣A∣−∣B∣)24≤n24. |A||B|=\frac{n^2-(|A|-|B|)^2}{4}\le\frac{n^2}{4}. 従って頂点数6では9本が上限となり、両側三頂点を全て結ぶ K3,3K_{3,3} が達成する。片側を2、他方を4にすると8本となる。上限だけでなく達成例を示して最大値を確かめる。

縮約で頂点を落とさない

原図の HH は中央を含む五頂点、七辺である。辺の縮約はその両端を一頂点へ同一視し、残る各辺の端をその対応で置き換える操作である。縮約した辺自体は消し、同じ二頂点間に重なった辺は本問の単純グラフとして一本にまとめる。中央頂点を初めから省いて四頂点の図として扱うことはできない。

一つずつ端点を対応させると、e1e_1 の縮約は四頂点六辺の K4K_4、e2e_2 の縮約は四頂点四辺の C4C_4 になる。図の見た目だけで三角形や三頂点パスと判断せず、縮約前後の頂点数が一つだけ減ることと、全ての辺を確かめる。

削除・縮約の符号と葉の削除

G−eG-e の正しい彩色を、ee の両端が異色か同色かで分ける。異色なら GG の彩色、同色なら二端を一つにした G/eG/e の彩色と一対一に対応する。従って γ(G−e,k)=γ(G,k)+γ(G/e,k),γ(G,k)=γ(G−e,k)−γ(G/e,k). \gamma(G-e,k)=\gamma(G,k)+\gamma(G/e,k),\qquad \gamma(G,k)=\gamma(G-e,k)-\gamma(G/e,k). 後者を加算とする誤りは、両端が同色の彩色を除外せず数え直してしまう。

木は閉路を持たず、閉路グラフとの共通部分はない。木の葉の辺を削ると、n−1n-1 頂点の木と孤立点になる。n−1n-1 頂点の木を k(k−1)n−2k(k-1)^{n-2} 通りとする通常の帰納仮定で十分であり、孤立点の色の kk 通りを掛ける。縮約側は n−1n-1 頂点の木なので、差は k(k−1)n−1k(k-1)^{n-1} となる。強い帰納法でなければ証明できないわけではない。

小例として二頂点の辺は k(k−1)k(k-1)、三頂点のパスは k(k−1)2k(k-1)^2。根を一つ選び、根を kk 通り、他の各頂点を親と異なる k−1k-1 通りに塗る直接の数え方でも同じ式になる。木の形に依存しない理由は、根以外の各頂点が一つの親を持ち、別の閉路による追加制約を受けないことにある。

第4問 計算理論(オートマトンと文脈自由文法)

有限オートマトンに保存する情報

aa の偶奇と bb の個数0、1を区別し、二個目の bb が現れた後は拒否の吸収状態へまとめる。aa を読むたび偶奇を反転し、bb を読むたび個数側だけを進めれば、現在の状態が表す条件を一文字ごとに保てる。bb が二個の状態を初期状態へ戻すと、例えば bbabba を誤って受理する。

禁止語の原題の指定は babbab、アルファベットは {a,b}\{a,b\} である。まだ禁止語が出ていない間、読んだ部分の最長接尾辞が ε,b,ba\varepsilon,b,ba のどれかを記憶する。bb の状態でさらに bb を読めば末尾の bb が候補として残り、baba の状態で aa を読めば末尾が baabaa になるので候補は空へ戻る。旧版の hahhah と {a,h}\{a,h\} の記述を原題の文字へ訂正した。

スタックの不変条件と底記号

個数差 D=Na−2NbD=N_a-2N_b を、正なら ADZA^D Z、負なら B−DZB^{-D}Z、0なら ZZ と表せる。aa は差を1増やし、bb は2減らす。bb の処理を二回の減算に分ければ、正から負にまたぐ場面も同じ規則で扱える。スタックの意味を通常状態へ戻った時点で保ち、入力が全て終わって差0のときにだけ受理へ移る。

底記号を置換する際にも ZZ を残す。例えば abaaba は aa が二個、bb が一個なので受理されるべきである。bb の途中処理で頂上の ZZ を単に BB に変えると底が消え、その後の aa で空になり受理できない。BZBZ として不足と底を別に表す必要がある。

非回文PDAは、区切り前を積み、区切り後と逆順に比較する。文字が違う場合、比較側が長い場合、短い場合を別々に捉える。原図の①は保存の自己ループ、②は区切りでの段階切替、③は一致文字を消す自己ループである。①へ既に記入済みの不一致辺のラベルを書いても空欄の答えにならない。ab#baab\#ba と ab#abab\#ab、a#a\# と #a\#a を使うと、一致・不一致・長さの両方向を確認できる。

文法が生成する集合を両方向から確かめる

L1L_1 は aa と bb が同数で、cc の個数は自由である。AA が anbna^n b^n、BB が cmc^m を作るなら、開始規則で両者を連結すればよい。二者択一を縦線でまとめても生成規則の個数はそれぞれを数え、空規則も一規則に含める。望む形が全て出ることに加え、それ以外の語が出ないことも示す。

反復補題で全分解を覆う

共通部分は anbncna^n b^n c^n である。反復補題の長さ pp に対して apbpcpa^p b^p c^p を選ぶと、長さ pp 以下の連続部分 vxyvxy は aa と cc を同時に含めない。間の bb 全てと両端の二文字だけで p+2p+2 文字になるためである。

従って vxyvxy が cc を含まない場合と aa を含まない場合で全分解を覆う。∣vy∣>0|vy|>0 なので i=0i=0 で削ると、触れない第三の記号の個数は pp のまま、他の少なくとも一種類が減る。三個数は等しくならない。都合のよい分解だけを一つ壊す説明では、ある分解が反復に耐えるという補題の主張を否定できない。二場合が bb だけの部分で重なっても、全てを覆うという証明には差し支えない。

第5問 ネットワーク(HTTP と TCP)

一部の確定答案なし

第5問(3-1)は送信完了時のタイマー値が明示されず、無条件の一意な範囲は確定できません。初期値0を補う0<S≤T−2Rと、定常区間0<S≤Tの条件付き解答を収録しています。

接続と要求、応答の本文を区別する

TCPのスリーウェイハンドシェイクではSYN、SYNとACK、ACKの順で接続の開始を確認する。その接続の上でHTTP Requestを送り、HTTP Responseを受け取る。HTTP/1.1の応答はステータス行、ヘッダー、空行、本文の順であり、HTMLファイルの先頭は本文の先頭である。旧版のようにHTTP Responseの先頭の管理情報をHTMLの一部として数えてはいけない。

例えば応答の先頭が HTTP/1.1 200 OK でも、そのHはHTMLファイルの最初の文字ではない。接続確立、ファイルの指定、応答の管理情報と本文という層と順序をそろえて説明する。要求を最後のACKと同時に送れる場合もあり、必ず別の往復を要するという説明もしない。

URL中の http はスキーム、ホスト名は接続先、パスはその接続先の中の情報資源を指す。ホスト名だけをURL全体と呼ばず、パスを実ファイルシステム上の絶対位置と無条件に同一視しない。

初回と定常のタイマーは同じ値ではない

サーバの送信完了を0とすると、受信完了は RR、第一制御メッセージ送信は R+SR+S、サーバへの到着は 2R+S2R+S。以後は到着時刻 tj=2R+jSt_j=2R+jS の差から tj+1−tj=St_{j+1}-t_j=S となる。一定の伝搬遅延は初回の到着には残るが、定常の到着間隔では相殺する。

送信完了時にタイマーを0と補う場合は 0<S≤T−2R0<S\le T-2R、従って T>2RT>2R が必要である。定常区間だけなら 0<S≤T0<S\le T。ただし原題には送信完了時のタイマー値が明示されていない。初期値を a≥0a\ge0 とすれば初回条件は 0<S≤T−a−2R0<S\le T-a-2R なので、無条件の一意な範囲は確定できない。本書はこの部分を限定事項とし、上の条件付き解答を収録する。

例えば T=10,R=1T=10,R=1 なら、a=0a=0 の上限は8、a=2a=2 では6である。前者で S=8S=8 なら初回到着が10で間に合い、S=9S=9 なら11で遅い。等号を含むのは、原題が TT を「超えない」間と指定するからである。初回の仮定を隠して定常の条件を一律に誤答と扱わない。

持続接続と処理負荷

周期を短くすると、NN 接続の制御メッセージ到着率は N/SN/S 件毎秒へ増える。距離や一件の伝搬時間が短くなるのではない。実装での受信処理やタイマー更新が増えるため、サーバの処理能力を圧迫する。遅延計算で置いた処理時間0という理想化を、実装の負荷が常に0という主張へ広げない。

毎回接続を解放すれば、次のファイルの要求の前に新しい接続の往復を要する。片道 RR の逐次取得の簡略モデルで、NN ファイルを毎回新規接続で取る確立の累計は N⋅2RN\cdot2R、一本を維持する場合との差は (N−1)2R(N-1)2R である。最初の接続はどちらにも要る。並列化を用いる別条件では、この単純な足し算を改める。

順序保証が再生期限へ及ぼす影響

TCPは失われた部分を再送し、アプリケーションへ順序のそろったバイト列を渡す。不足部分を待っている間に再生バッファが尽きれば、後続が届いていても再生が途切れる。再送が一回起きるたび必ず停止するのではなく、先読み量と待ち時間に左右される。

再生可能な量 BB、消費速度 vv なら、追加データなしで持つのは B/vB/v 秒である。この猶予より長く使えるデータが届かない場合に尽きる。TCPの信頼性が低いからという説明は因果が逆である。一方HTTPには既存のWebサーバやキャッシュ、配信網を使える利点がある。全ての通信機器を無条件に通れると断定せず、再生期限と設備利用の利点を別々に述べる。

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

第6問 電子回路と論理設計(フィボナッチ数列の専用ハードウェア)

配線から同時更新の式を作る

MUXはADDの出力側にあり、定数1と二レジスタの和を選んでR1へ渡す。クリアが0のとき、クロック直前の値を使って R0+=R1R_0^{+}=R_1、s=0s=0 なら R1+=1R_1^{+}=1、s=1s=1 なら R1+=R0+R1R_1^{+}=R_0+R_1 となる。両レジスタは同じ端で更新され、先にR0を新値へ代入してから和を作るのではない。

初期値が両方0のときは定数1を選ぶ必要がある。S1S_1 では定数入力も和 0+10+1 も1なので、ss は0でも1でもよく、空欄②は XX になる。S4S_4 の XX は、クリアが入力に優先して0を書き込むためである。同じドントケアでも、二入力の一致と書込み結果の上書きを区別する。

例えば R0=2,R1=3,s=0R_0=2,R_1=3,s=0 では実回路はR1へ1を渡す。MUXをADDの前に置く旧式 R0+MUX(s)R_0+\mathrm{MUX}(s) では3になり、配線と合わない。初期の数状態でたまたま値が一致しても、回路のモデルが正しい証拠にはならない。

論理をまとめる際の0とドントケア

積和形はAND項をORで結んだ式で、隣接セルを合わせる操作は xy+xy‾=xxy+x\overline y=x に対応する。未使用の三状態と、動作に影響しない制御出力だけを自由に選べる。実際に使う状態の0を覆ってはいけない。

d2d_2 が1の000と010は k1k_1 だけが異なるから、d2=k0‾ k2‾d_2=\overline{k_0}\,\overline{k_2} の一項でよい。旧版が加えていた k1k2‾k_1\overline{k_2} は有効五状態では不要である。また ss は010、011で1、000で0、001と100で XX。未使用110、111を使えば s=k1s=k_1 で足り、旧版の k1+k2k_1+k_2 より簡単になる。

d2=k2‾d_2=\overline{k_2} とすると100で1になり、次状態000を満たさない。反対に必要以上の項を残しても、動くという検算だけでは最簡性を示せない。各出力について真理値表を満たすことと、これ以上項や変数を減らせないことを分けて確かめる。

数列と同期の検算

旧値で同時更新すると (0,0)→(0,1)→(1,1)→(1,2)→(2,3)(0,0)\to(0,1)\to(1,1)\to(1,2)\to(2,3) となる。出力は0、1、1、2、3で、最後に両方をクリアすれば繰返しを再現する。F2=2F_2=2 と書くと初期条件から外れ、後の数列もずれる。

桁上げを出さない bb ビット加算器の和は 2b2^b で割った余りになる。4ビットでは15が最大で、F7=13F_7=13 までは入るが F8=21F_8=21 では 21 mod 16=521\bmod16=5 になる。最大値15へ固定される飽和ではない。

格納幅と途中経路の幅

最大必要値 VV を収める条件は 2b−1≥V2^b-1\ge V、すなわち b≥⌈log⁡2(V+1)⌉b\ge\lceil\log_2(V+1)\rceil。F15=610F_{15}=610 では9ビットの最大511では足りず、10ビットの最大1023なら収まる。出力とR1だけでなく、ADD、MUX、途中のデータ線、定数1とクリア値も対応する幅へそろえる案なら全項を失わず生成できる。

R1だけを拡げても4ビットADDが21を5へ切った後なので、失った桁は復元できない。この一様10ビット化は十分な構成であり、R0も個別の最小幅が必ず10だと断定する必要はない。最後に保存する前項は377なので、幅の異なる経路を適切に接続する別案もある。格納可能性と加算・選択・配線の通り道を合わせて検証する。

第7問 数学解析と信号処理(理想低域通過フィルタの設計)

方針 — 「時間領域の理想 IR を窓で打ち切る」FIR 設計の基本パイプライン

理想 LPF の設計は次の流れで進む.

  1. 周波数領域で理想応答 H(ω)H(\omega) を指定する.
  2. 逆 DTFT でインパルス応答 h[n]h[n] を得る(本問 (1)).
  3. h[n]h[n] は両側無限長で因果でない. そこで時間領域で窓 w[n]w[n] を掛けて h′[n]=h[n]w[n]h'[n]=h[n]w[n] という有限長 FIR にし((2)→\to(3)), さらに必要な遅延を加えて因果化する(本問では遅延の話題は明示されていないが, 実装では h′[n−(M−1)/2]h'[n-(M-1)/2] などとシフトする).
  4. 周波数領域では H′(ω)=(W∗H)(ω)/(2π)H'(\omega) = (W*H)(\omega)/(2\pi) になり, 窓関数の特性がフィルタ特性に影響する((3-1)(3-2)(4)).

窓関数の二大スペック「メインローブ幅」「サイドローブ高さ」が, それぞれフィルタの「遷移帯域幅」「リップル/阻止域減衰」を支配する.

逆 DTFT を行うときの定数の追跡

(1) で重要なのは 1/2π1/2\pi の定数因子と ∫ejωndω=ejωn/(jn)\int e^{j\omega n}d\omega = e^{j\omega n}/(jn) の積分後因子. 結果に π\pi が残る形 sin⁡(ωcn)/(πn)\sin(\omega_{c}n)/(\pi n) になることはこの 2 つの 1/2π1/2\pi と 1/(jn)1/(jn) の組み合わせからの自然な帰結である. n=0n=0 では極限ではなく直接定数積分を評価して ωc/π\omega_{c}/\pi を出すのが安全.

典型ミス

  • (1) で sinc\mathrm{sinc} の定義を取り違える. 信号処理では sinc(x)=sin⁡(πx)/(πx)\mathrm{sinc}(x)=\sin(\pi x)/(\pi x) と定義することが多い. 「指数関数を用いない」と指定されているので, sin⁡\sin をそのまま書くのが安全.
  • (2) で「因果性が無いから」だけで終える. 「未来サンプル不要」「タップ数有限」の二重の要件があり, 因果性違反と有限性違反の二点に分けて述べると点が固い.
  • (3-1) で σ=2π/M\sigma=2\pi/M と書く. ゼロ点は ±2π/M\pm 2\pi/M の 2 点で, 距離(幅)は二倍の 4π/M4\pi/M.
  • (3-2) で τ\tau の計算で第 2 項 W(ω+ωc)W(\omega+\omega_{c}) を無視する根拠を書かない. 「ω≈ωc\omega\approx\omega_{c} では ω+ωc≈2ωc\omega+\omega_{c}\approx 2\omega_{c} で WW がサイドローブの底まで小さい」ことを一言述べると論理がしっかりする(本問は「導出は記述しなくてもよい」とあるので, 本番ではこの正当化は省略してよい).
  • (4-1) で「MM を大きくすると阻止域減衰が増える」と書く. MM は 遷移帯域 を狭めるが, 阻止域減衰自体は 窓のサイドローブ が支配する. 矩形窓ならどんな MM でも阻止域減衰は ∼\sim13 dB 程度で頭打ち.
  • (4-2) でリップルとメインローブを混同する. 「窓のサイドローブ高さ」 →\to 「フィルタのリップル振幅・阻止域減衰量」, 「窓のメインローブ幅」 →\to 「フィルタの遷移帯域幅」と完全に対応する.

検算 — 矩形窓のメインローブ幅とギブス現象

矩形窓を掛けた LPF は阻止域減衰が約 21 dB(ピークサイドローブ≈\approx −13-13 dB)に留まることが知られている. これは窓長 MM をいくら大きくしても改善せず, 窓関数の 形 に依存する現象(ギブス現象). 高減衰が必要なら Hamming(約 −43-43 dB), Blackman(約 −58-58 dB)など, サイドローブを潰した窓を選ぶのが定石.

背景 — Kaiser 窓と仕様駆動設計

実用的なフィルタ設計では, 通過域・阻止域の許容リップル(δp,δs\delta_{p},\delta_{s})と遷移帯域幅 Δω\Delta\omega から必要な窓長 MM と窓パラメータを決めるアプローチが取られる(Kaiser 窓 + 経験式が代表). 本問の (4-1)(4-2) はこの設計プロセスの基本となる「メインローブ vs サイドローブ」のトレードオフを問う設問.

解答

(1) 逆変換で零番目のサンプルを分ける

0<ωc<π0<\omega_c<\pi では、逆DTFTの積分が通過域だけに限られる。n≠0n\ne0 に対して h[n]=12π∫−ωcωcejωn dω=ejωcn−e−jωcn2πjn=sin⁡(ωcn)πn. h[n]=\frac1{2\pi}\int_{-\omega_c}^{\omega_c}e^{j\omega n}\,d\omega =\frac{e^{j\omega_cn}-e^{-j\omega_cn}}{2\pi jn} =\frac{\sin(\omega_cn)}{\pi n}. n=0n=0 は積分内が1なので h[0]=2ωc/(2π)=ωc/πh[0]=2\omega_c/(2\pi)=\omega_c/\pi。

(2) 未来の入力と無限のサンプルが必要になる

0<ωc<π0<\omega_c<\pi の理想応答は負の nn にも非零の値を持つため、畳込み y[n]=∑kh[k]x[n−k]y[n]=\sum_kh[k]x[n-k] で未来の入力を使う。また、非零の応答が無限に続き、有限の遅延と有限個の係数で理想応答そのものを実装できない。

(3-1) 矩形窓の最初の二つの零点を使う

奇数の M≥3M\ge3 に対し、分母が0でない最初の分子の零点は sin⁡Mω2=0,ω=±2πM. \sin\frac{M\omega}{2}=0, \qquad \omega=\pm\frac{2\pi}{M}. したがって、その間の幅は

(3-2) 極値で定義した幅と、長い窓での近似を区別する

長い窓で二つのカットオフの干渉を無視する通常の近似では ωl≃ωc−2πM,ωu≃ωc+2πM,τ≃4πM. \omega_l\simeq\omega_c-\frac{2\pi}{M},\qquad \omega_u\simeq\omega_c+\frac{2\pi}{M},\qquad \tau\simeq\frac{4\pi}{M}. 原題の極大・極小の定義を厳密に使う場合は、二つの窓応答の差を残す必要がある。 dH′dω=W(ω+ωc)−W(ω−ωc)2π. \frac{dH'}{d\omega} =\frac{W(\omega+\omega_c)-W(\omega-\omega_c)}{2\pi}. この式が0となる点から、ωc\omega_c に最も近い極大・極小を選び、差を取る。

(4-1) 窓を長くすると、遷移は狭まり計算と遅延は増える

矩形窓の主峰幅は σ=4π/M\sigma=4\pi/M なので、窓長 MM を増やすほど狭くなる。十分長い窓ではフィルタの遷移域もこれに応じて狭まり、近い周波数を通過域と阻止域へ分けやすくなる。一方、必要な係数・演算・記憶量と、因果化の遅延 (M−1)/2(M-1)/2 サンプルが増える。

(4-2) サイドローブによる回り込みと窓の形の選択

主峰に対する相対的なサイドローブが小さい窓は、周波数の畳込みで離れた領域から回り込む寄与を抑え、通過域・阻止域のリップルを小さくする。不要な周波数成分を減らしやすくなる一方、同じ窓長なら主峰が広がり、遷移域が広くなる傾向がある。

最終答

(1) 逆変換で零番目のサンプルを分ける

h[n]={ωc/πn=0,sin⁡(ωcn)/(πn)n≠0.\displaystyle h[n]=\begin{cases}\omega_c/\pi&n=0,\\ \sin(\omega_cn)/(\pi n)&n\ne0.\end{cases}(0<ωc<π0<\omega_c<\pi)。ωc≥π\omega_c\ge\pi では基本区間を全て通し、h[n]=δ[n]h[n]=\delta[n]。

(2) 未来の入力と無限のサンプルが必要になる

非因果な両側無限長の応答なので、実時間処理にはそのまま使えない。有限長へ切り詰めて遅延を加えると実装できるが、周波数応答は近似となる。

(3-1) 矩形窓の最初の二つの零点を使う

σ=4πM\displaystyle\sigma=\frac{4\pi}{M}(奇数 M≥3M\ge3)。M=1M=1 は W(ω)=1W(\omega)=1 で零点がなく、この定義の幅は存在しない。

(3-2) 極値で定義した幅と、長い窓での近似を区別する

長い窓の近似値は τ≃4π/M\tau\simeq4\pi/M。一般の厳密値を 4π/M4\pi/M とする等式は成り立たず、W(ω+ωc)=W(ω−ωc)W(\omega+\omega_c)=W(\omega-\omega_c) の極値から決まる。例えば M=21, ωc=π/2M=21,\ \omega_c=\pi/2 では厳密に τ=π/5\tau=\pi/5。

(4-1) 窓を長くすると、遷移は狭まり計算と遅延は増える

窓長を増すと周波数選択性を高められるが、実装する長さと遅延が増す。厳密な極値幅と主峰幅の一致を仮定しない。

(4-2) サイドローブによる回り込みと窓の形の選択

小さいサイドローブはリップルや漏れの抑制へ役立つ。窓長を固定したときの主峰の幅との両立を確認して窓を選ぶ。

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

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

解答PDFの商品ページへ

年度別の解答例

  • 2025年度(このページ)

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

  • 2024年度

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

  • 2023年度

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

  • 2022年度

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

  • 2021年度

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

  • 2020年度

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

2025年度の出題内容

大問分野主題解説の小見出し最終答
第1問情報アルゴリズムとプログラミング(二分ヒープ)方針 — 二分ヒープのインバリアントを言葉と式で押さえる / なぜ 1-indexed かあり
第2問情報計算機システムとシステムプログラム(パイプライン)方針 — 「クロック時間 × CPI」を分けて考える / なぜ 4n + 576/n の形になるかあり
第3問—離散構造(グラフ彩色と削除・縮約)—あり
第4問情報計算理論(オートマトンと文脈自由文法)—あり
第5問—ネットワーク(HTTP と TCP)—一部の確定答案なし
第6問電磁気学・回路電子回路と論理設計(フィボナッチ数列の専用ハードウェア)—あり
第7問数学数学解析と信号処理(理想低域通過フィルタの設計)方針 — 「時間領域の理想 IR を窓で打ち切る」FIR 設計の基本パイプライン / 逆 DTFT を行うときの定数の追跡あり

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

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

大問数
2024年度 7問 → 2025年度 7問
2025年度で新しく出たテーマ
フーリエ変換・正規表現・形式言語

2024年度の解答例

大阪大学の他の解答PDF

院試対策ガイド

大阪大学の公式過去問

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

大阪大学の公式過去問PDF