阪大 情報科学研究科 専門科目（情報工学） 2025年度 院試 解答例・解説

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

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

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

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

なぜ 1-indexed か

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

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

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

典型ミス

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

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

(2-1) の最終配列が最小ヒープであることは, $i=1,\dots,5$ について $\mathtt{data}[i] \le \mathtt{data}[2i]$ と $\mathtt{data}[i] \le \mathtt{data}[2i+1]$ が成り立つかを確かめれば十分である. $$\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}$$ すべて $\mathtt{data}[i] \le \mathtt{data}[2i]$ かつ $\mathtt{data}[i] \le \mathtt{data}[2i+1]$ なので最小ヒープ.

オーダの直感

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

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

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

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

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

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

$T_{\text{avg}}$ の中で $n$ を含む項を整理すると $$\Bigl(\tfrac{900}{n}+40\Bigr)(0.1n+0.64) = 90 + \tfrac{576}{n} + 4n + 25.6$$ で, $n$ に依存する部分は $4n + 576/n$ のみ. AM-GM 不等式から $$4n + \frac{576}{n} \ge 2\sqrt{4n \cdot \tfrac{576}{n}} = 2\sqrt{2304} = 96,$$ 等号は $4n = 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\,m$ と書く. 単位が「ピコ秒/命令」になる量を $m$ 倍した「全 $m$ 命令の総時間」と取り違えやすい. 平均実行時間は $\mathrm{CPI}\times T_{\text{clk}}$ で十分.
• (1-4) で連続値の最小 $n=12$ をそのまま書く前に整数性を確認しないこと. 段数は整数なので, 隣の整数と値を比較して最終的に $n=12$ を選ぶ手続きが必要.
• (2-1)(2-2) で IF と ID の順番を入れ替える. ストール時にどのステージを再実行するかは設計に依存. 本問は「IF と ID をやり直す」と明示されているので, 後ろの命令の IF, 当該命令の ID をそれぞれ 2 サイクル分書くのが正しい.
• (2-3) 命令列 A で「lw と sw を入れ替える」と提案する. sw は lw のロード結果 r7 をアドレスに使うので, 入れ替えると意味が変わってしまう.

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

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

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

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

方針 — 「奇閉路の有無」と「最大クリーク」

彩色数の判定には次の二つが頻出.

• 奇閉路を含まない $\Leftrightarrow$ 二部グラフ $\Leftrightarrow$ $\chi\le 2$.
• クリーク数 $\omega(G)\le \chi(G)$. つまり $K_t$ を部分グラフに持てば $\chi\ge t$.

$G_4=K_4$ は $\chi=4$, $G_3=K_4-e$ は $\chi=3$ がこの二点から即決. $G_2=C_4$ は奇閉路無しで $\chi=2$.

$K_{3,3}$ になる理由を AM-GM で

二部グラフの最大辺数は $|A|\cdot|B|$ で $|A|+|B|=n$. 算術相乗平均不等式から $$|A|\cdot|B| \le \left(\frac{|A|+|B|}{2}\right)^{2} = \frac{n^{2}}{4},$$ 等号は $|A|=|B|=n/2$ のときに成立. $n=6$ で $9$ を達成し, 構成例が $K_{3,3}$.

削除・縮約公式の意味と汎用性

$\gamma(G,k)$ は彩色多項式と呼ばれる $k$ の整数係数多項式で, 削除・縮約公式は彩色多項式を再帰的に計算する基本ツール. 木で $\gamma(T,k)=k(k-1)^{n-1}$ が証明できたのは, 葉を持つ性質と組み合わせて再帰の段数を減らせるためである.

同じ削除・縮約公式は Tutte 多項式という一般化(全域木数, 信頼性多項式, ジョーンズ多項式の特殊化を含む)にもつながる, 組合せ論で重要な構造.

典型ミス

• (1-3) で $\mathcal{T}\subset\mathcal{C}$ と書く. 木は閉路を含まないので $\mathcal{T}\cap\mathcal{C}=\varnothing$. $\mathcal{T}\subset \mathcal{G}_2$ と混同しないこと.
• (2-1) で縮約後の自己ループを残す. $a$ と $c$ を縮約した際, $a$ と $c$ の双方に隣接していた頂点(ここでは $b$ や $d$)に対して 2 本の辺ができるが, 問題が「多重辺・自己ループを持たない」と仮定しているので集合として 1 本にまとめる. 縮約された辺 $e$ 自体は「$x$ と $y$ の間の辺」だったので, $v_e$ から $v_e$ への自己ループは作られない(集合の定義から $\{v,w\}$ で $v=w$ は除外).
• (2-3) で $\gamma(G,k)=\gamma(G-e,k)+\gamma(G/e,k)$ と符号を間違える. 「$G-e$ の彩色を $c(x)=c(y)$ かどうかで分ける」ことから $\gamma(G-e)=\gamma(G)+\gamma(G/e)$. 引き算で $G$ を孤立させる.
• (2-4) で帰納の仮定を「$n-1$ 頂点の木」に限定する. 削除・縮約公式の右辺で出てくるグラフが必ずしも単純な「$n-1$ 頂点の木」とは限らないので, 「$n$ 未満の頂点を持つ 任意の 木」に対する強い仮定が必要. 本問では $T-e$ が連結ではない 2 成分(木+孤立点)になる扱いに注意.

検算 — 小さい木で式を確かめる

$n=2$ の木(辺 1 本): $\gamma=k(k-1)$. 直接数えても「片端に $k$ 通り, もう片端に $k-1$ 通り」で一致.

$n=3$ のパス $P_3$: $\gamma=k(k-1)^{2}$. 中央頂点 $k$ 通り, 両端それぞれ $k-1$ 通り. 一致.

$n=3$ のスター(中心 1, 葉 2 — これも木): 同じく $\gamma=k(k-1)^{2}$. 中心 $k$, 葉 2 個それぞれ $k-1$ 通りで $k(k-1)^{2}$. 一致.

公式は木の 形によらず 頂点数だけで決まる. 木のすべての辺は橋(削除すると非連結になる辺)であり, この性質が公式の特徴的な形を生んでいる.

別解 — 直接数え上げで木の彩色数

「根を選んで深さ優先で塗る」という直接的な数え上げでも示せる. 木 $T$ の任意の頂点 $r$ を根とすると, 根を塗る方法が $k$ 通り. 根以外の頂点は親が一意に決まり, 親の色と異なる色を選べばよく $k-1$ 通り. 全体で $k(k-1)^{n-1}$. これは構成的でわかりやすいが, 削除・縮約公式の応用例として帰納法での示し方は他の問題でも使える点で価値がある.

方針 — DFA は「必要十分な記憶」を最小化する

DFA 設計の要は「将来の入力で受理判定に必要な情報だけを状態に持つ」こと.

• (1-1) 受理判定に必要なのは「$a$ の偶奇」と「$b$ の個数(0, 1, $\ge 2$)」の 2 軸. これらの直積から $2\times 3 = 6$ 状態にも見えるが, $b\ge 2$ の場合は将来も拒否確定なので吸収状態 1 つに潰せて 5 状態.
• (1-2) パターンマッチング系では, 「直近に読んだ文字が hah の接頭辞のうち最長どれか」を記憶すれば良く, KMP の失敗関数と本質的に同じ.

PDA 設計の鉄則 — スタックの「意味」を 1 行で書ける形に

(2-1) で「スタック内容 $=$ 残り不均衡を $A$/$B$ で表したもの」と定義したように, スタックの抽象的な意味(invariant)をはっきり言語化してから設計するとミスが減る. 状態は invariant 自体を変えずに「処理の途中段階」を捉える.

(2-2) のような対称性を要する言語では「スタックに入れる順序」と「出す順序」が逆転する点を意識し, $w$ を素直に push, $w'$ で逆順にマッチさせると自然に逆順比較ができる.

典型ミス

• (1-1) で $b$ が 2 個以上の場合の状態を作り忘れる. $b$ がもう一回出たら拒否, は明示的に吸収状態 $T$ で示す必要がある(DFA は完全関数なので).
• (1-2) で $q_2$ から a を読んだとき $q_1$ に戻してしまう. 直近 2 文字が aa になっており, 「h$\to$」の接頭辞すら持たないので $q_0$ に戻すのが正しい.
• (2-1) で $b$ を読んだ際の「2 文字分」をスタック push と pop で実装し忘れる. 1 個の $b$ で $a$-単位を 2 引く必要がある. 「中継状態」を介して 2 段階で行うのが定石.
• (2-2) で長さ不一致のケースを捉え忘れる. 「$w'$ の方が短い」「$w'$ の方が長い」両方を別の遷移として用意しないと, 例えば $w=ab,w'=ab$ のような palindrome 以外でも「同じ長さで全文字一致」しか拒否できなくなり, 入力 ab\#abab のような非回文を受理できない.
• (3-2) で $L_{1}\cap L_{2}=\{a^{n}b^{n}c^{m}\}$ などと書く. 二つの条件「$a$=$b$」「$b$=$c$」が両方同時に効くので $a=b=c$.

検算 — DFA の最小性

(1-1) は「$2\times 3$ から吸収状態を 1 つに潰した」最小 DFA. ミルナー(Myhill–Nerode)同値類で言うと, 同値類の個数は $\{E_0,O_0,E_1,O_1,T\}$ の 5 個と一致する. (1-2) も同様に, 同値類「直近のパターン接頭辞」が 4 種類で最小.

反復補題の使い方

CFL 反復補題の検証では, $vxy$ の長さ制約($|vxy|\le p$)から「$vxy$ が同時に含めるブロック」を絞り, 「同じ位置の文字を pump で増減させる」のがコツ. $\{a^{n}b^{n}c^{n}\}$ のように 3 種類の出現数の等式が要求される言語は, 必ず $vxy$ が高々 2 種類のブロックしか触れないことを利用して矛盾を作る.

背景 — CFL の閉包性質

文脈自由言語は和, 連結, 星, 準同型像については閉じているが, 補集合, 積集合では閉じていない. 本問の証明はその「積集合について閉じない」具体例を与えるもので, $L_{1}, L_{2}$ がそれぞれ CFL であること(自明な文法を構成して示せる)と, $L_{1}\cap L_{2}$ が CFL でないこと(反復補題で示す)から従う論法.

方針 — 「層をまたぐ動作」を順序立てて言語化する

(1) のような問題はアプリケーション層(HTTP)とトランスポート層(TCP)の挙動を時間順に並べることが本質. 「先頭のビットを受信するまで」と言われたら, 物理的にビットがクライアントに到着する条件を逆算する: そのビットは HTTP Response の一部 → HTTP Response が送信されている必要 → HTTP Request がサーバに届いている必要 → TCP コネクションが確立済み, という連鎖.

タイマ問題の場合分け — 「初回」と「定常」を分けて評価

(3-1) は以下の二つの区間を別々に最大値評価するのが鉄則.

• 初回: ファイル送信完了から最初の制御メッセージ受信までの時間 $2R+S$.
• 定常: 制御メッセージ間隔 $S$ ごとにリセットされるため $S$.

タイマの最大値は両者の最大であり, $R>0$ なので初回区間の制約 $2R + S \le T$ がきつい. 「$T$ と $R$ を用いて表せ」という指示の意図はこの初回区間を含めて立式することにある.

HTTP/TCP の関係を「持続」と「即時切断」で比較

(3-3) は HTTP/1.1 で導入された keep-alive(persistent connection)の存在意義を確認する設問. 接続を持続させるとハンドシェイク回数が減り, 複数ファイル(画像, CSS, JS, …)の取得時に大幅な高速化が実現できる. 現代の Web では HTTP/2, HTTP/3 でさらに多重化やヘッダ圧縮を行い, ハンドシェイクと往復遅延の影響をさらに削減している.

典型ミス

• (1) で「ACK フラグ」を一つしか使わない. SYN+ACK の応答(2 ステップ目)とクライアントの ACK(3 ステップ目)で 2 回登場するのが正確.
• (2) で www.ist.osaka-u.ac.jp を「URL」と書く. これはホスト名(FQDN)であり, URL の 一部分 である. 「URL とは何か」と「URL のホスト部とは何か」を取り違えない.
• (3-1) で $S \le T$ と書く. 「$T$ と $R$ を用いて」という条件を満たさないし, 初回区間の遅延 $2R$ を見落としている.
• (3-3) で「サーバの負荷が増えるから」と漠然と書く. 増加の主因は ハンドシェイクのための RTT 1 回分の時間 という具体的な遅延要因. 「コネクション再確立に必要な往復遅延」を明示する.
• (4) で「TCP は信頼性が低いから途切れる」と書く. 因果が逆で, TCP は 信頼性確保 のための再送がリアルタイム性と衝突するために途切れる.

検算 — タイマ条件を具体値で

例えば $T=10$ s, $R=1$ s なら $S\le 8$ s. 仮に $S=8$ ちょうどで送ると, 初回到達は $t=10$ s でタイマがちょうど $T$ に達する瞬間で間に合う. $S=9$ にすると $t=11$ s で先に切断されてしまう, と整合する.

背景 — keep-alive と HOL ブロッキング

(3-3) と (4) はそれぞれ HTTP の keep-alive(コネクション持続)と TCP のヘッドオブラインブロッキング(損失再送中の後続パケット保留)という, トランスポート層・アプリケーション層の代表的な性能問題に触れている. これらを解決するために HTTP/2 では多重化(stream concept), HTTP/3 では QUIC(UDP ベースで HOL ブロッキングを軽減)が採用されており, 本問の知識はこうした最新プロトコル設計の背景理解にも繋がる.

方針 — 「データパスの抽象化」と「制御回路の真理値表」を分けて考える

(1) はデータパスを観察して「何が R0 に, 何が R1 に書かれるか」を式で抽象化することが第一歩. その上で各クロックで $R_{1}=y$ が望ましい $F_{n}$ になるための条件から $s$ を決定する.

• クリアが立っていない時の更新則: $R_{0}^{\text{next}}=R_{1}^{\text{cur}}$, $R_{1}^{\text{next}}=R_{0}^{\text{cur}}+ \mathrm{MUX}(s)$.
• $s=0$ なら MUX$=1$, $s=1$ なら MUX$=R_{1}^{\text{cur}}$.
• 初期 $R_{0}=R_{1}=0$ から $F_{1}=1$ を作るには $\mathrm{ADD}=R_{0}+1=1$ が必要なので $s=0$.
• $S_{1}$ 以降は漸化式 $F_{n+1}=F_{n-1}+F_{n}$ そのものなので $s=1$($\mathrm{ADD}=R_{0}+R_{1}$).

なぜ $S_{4}$ で $s$ がドントケア

$c_{0}=c_{1}=1$ ということは, R0, R1 共に次クロックで強制 0 に上書きされる. ADD 出力は捨てられるので, ADD への入力に関与する $s$ も結果に影響しない. ハードウェア合成の段階でドントケアを使えば論理が小さくなる((1-3) で $s=k_{1}+k_{2}$ が選べたのもこの恩恵).

(1-3) のカルノー図解釈

各出力をカルノー図で塗ると次のようになる(灰色: ドントケア).

• $d_{2}$ のみ少し技巧的. $S_{4}=100$ では $d_{2}=0$ が必須なので「$\overline{k_{2}}$ 単独」ではない. $\overline{k_{2}}$ を $\overline{k_{0}}$ と $k_{1}$ で限定して 2 項に分ける.
• $s$ はドントケア $101,110,111$ をすべて $1$ 側に取り込めるので, $k_{1}\lor k_{2}$ という単純な OR で済む.

典型ミス

• (1-1) で $F_{2}=2$ と書く. $F_{0}+F_{1}=0+1=1$ なので $F_{2}=1$. 漸化式の境界値で間違えやすい.
• (1-2) で $S_{0}$ の $s$ を 1 とする. $R_{0}=R_{1}=0$ で $s=1$ にすると $\mathrm{ADD}=0+0=0$ となり, 次状態で $R_{1}=0=F_{1}$ にならない. 初期値が同じだから「初回だけ $s=0$」という特殊扱いが必要.
• (1-3) で $d_{2}=\overline{k_{2}}$ と書く. 100 のセルを忘れている. $S_{4}$ の次状態は 000 で $d_{2}=0$ なので $\overline{k_{2}}(100)=1$ にできない.
• (2-1) で $F_{16}$ や $F_{15}$ と答える. 4 ビット範囲を超える最初は $F_{8}=21$. $F_{7}=13$ までは 4 ビットで表現可能.
• (2-2) でビット幅を 8 や 9 と書く. $F_{15}=610$ で, $2^{9}=512<610\le 1023=2^{10}-1$. ちょうど 10 ビット必要. ビット幅は単に「$F_{15}$ 以下の最大値」ではなく「$F_{15}$ も収まる最小ビット幅」で決まる.

検算 — シミュレーションで $F_{4}$ まで再現

クロックごとに $(R_{0},R_{1})$ を追跡: $$(0,0) \xrightarrow{s=0}(0,1) \xrightarrow{s=1}(1,1) \xrightarrow{s=1}(1,2) \xrightarrow{s=1}(2,3).$$ 出力 $y=R_{1}$ は $0,1,1,2,3$ となり $F_{0},\dots,F_{4}$ と一致. $S_{4}$ で $c_{0}=c_{1}=1$ により $(0,0)$ に戻り, $S_{0}$ から再開.

背景 — 桁上げを出さない加算器の意味

「桁上げを出さない加算器」とは, 桁上げ出力ピンが無く $\bmod 2^{b}$ の和だけを出力する素朴な加算器のこと. 一般には桁上げ出力 $C_{\text{out}}$ を取って次段やフラグレジスタに繋ぐが, 本問のような専用ハードウェアでは省略されることがある. これにより「設計の単純化と引き換えにオーバーフロー検出ができない」という典型的なトレードオフが生じる.

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

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

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

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

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

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

典型ミス

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

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

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

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

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