第3回 解答（FA年・プロセッサ年の再来）
📄 解答PDF版をダウンロード対応する問題：第3回 予想問題。記述式の小問（「〜行で説明せよ」）は解答例であり、同じ内容が伝わる表現なら形は問わない。誤りを見つけたら作成者（Claude）に報告してほしい。
問題1 二分探索木 解答
(1) ①30 ②40 ③10。（各キーは根から比較しながら降りて空いた位置に付く。40 は 50→左、30→右で ② の位置。10 は 50→30→20→左で ③。）
(2) 出力：
10 20 30 40 50 60 70 1 3
理由：二分探索木では全節点で「左部分木の全キー ＜ 自身のキー ＜ 右部分木の全キー」が成り立つ。中間順巡回は「左 → 自身 → 右」の順に出力するため、常に小さいものから出力される。
(3) 50 → 30 → 40 の 3個（count = 3）。40<50 で左へ、40>30 で右へ、40=40 で発見。
(4) 昇順挿入では $k$ 番目のキーが常に最大なので、根から右端の葉まで既存の $k-1$ 個の節点をすべて通過し、各節点で13行目が1回ずつ評価される（いずれも偽）→ $k-1$ 回。総和は $$\sum_{k=1}^{n}(k-1)=\frac{n(n-1)}{2}.$$ 完成する木は右に一直線で、根から最深節点までの経路上の節点数は $n$。
(5) 木の高さが $O(\log n)$ に保たれる平衡性（AVL木・赤黒木などが挿入時に回転で維持する性質）。探索は根から葉への1本の経路しか辿らず、比較回数は高々「高さ＋1」なので、高さが $O(\log n)$ なら比較も $O(\log n)$ で抑えられる。
問題2 パイプライン処理 解答
(1) クロックサイクル時間は $T/5$。各サイクルに1命令が完了する（理想時）ので、スループットは非パイプライン比で5倍。
(2-1) r1 は I1 の WB（第5サイクル）で書かれ、I2 は同サイクルの ID で読める（書き込み先行の仮定）：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | ||||||
| I2 | IF | — | — | ID | EX | MEM | WB | ||||
| I3 | IF | — | — | — | — | ID | EX | MEM | WB |
総サイクル数 11。
(2-2) フォワーディングありでは、I2 は MEM/WB→EX 転送を使うが、lw の結果は MEM 終了（第4サイクル末）まで得られないため1サイクルのストールが残る（load-use ハザード）。I3 は I2 の EX 結果を EX/MEM→EX 転送で受け取れるのでストール不要：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | |||
| I2 | IF | ID | — | EX | MEM | WB | ||
| I3 | IF | — | ID | EX | MEM | WB |
総サイクル数 8。理由：加算命令が必要とする r1 の値は、lw ではメモリアクセス（MEM）が終わるまで存在しないため、EX 段への転送では1サイクル分間に合わない。
(3) 最初の命令の完了に $k$ サイクル、以後1サイクルに1命令なので $k+N-1$ サイクル。速度向上率は $$\frac{Nk}{k+N-1}\ \xrightarrow{N\to\infty}\ k.$$
(4) 制御ハザード（分岐ハザード）。対策例：分岐予測——分岐の成立/不成立を予測して後続命令を投機的にフェッチ・実行し、予測が外れた場合はパイプライン内の命令を破棄してやり直す。（遅延分岐でも可。）
問題4 DFA最小化＋閉包性 解答
(1-1) 初期分割：受理 $\{q_5\}$／非受理 $\{q_0,\dots,q_4\}$。
第1回細分：$q_3,q_4$ は両入力で受理クラスへ遷移、$q_0,q_1,q_2$ は非受理クラスへ → $\{q_3,q_4\}$、$\{q_0,q_1,q_2\}$ に分裂。
第2回細分：$q_1,q_2$ は両入力で $\{q_3,q_4\}$ へ、$q_0$ は $\{q_1,q_2\}$ へ → $\{q_0\}$、$\{q_1,q_2\}$ に分裂。
以後変化なし。最小DFAは 4状態：$[q_0]\xrightarrow{a,b}[q_1q_2]\xrightarrow{a,b}[q_3q_4]\xrightarrow{a,b}[q_5]$（$[q_5]$ は自己ループ、受理）。
(1-2) $L(M)=$ 長さ3以上のすべての語。
(2) $Q=Q_1\times Q_2$、$\delta([r_1,r_2],a)=[\delta_1(r_1,a),\ \delta_2(r_2,a)]$、$q=[q_1,q_2]$、そして共通部分では $$F=F_1\times F_2$$ （両方が受理状態のときのみ受理）。和集合の場合は $F=(F_1\times Q_2)\cup(Q_1\times F_2)$ で、受理集合の定義だけが異なる。
(3) $L$ が正則と仮定する。$0^*1^*$ は正則であり、正則言語は共通部分について閉じているので $L\cap L(0^*1^*)$ も正則となる。ところが $$L\cap 0^*1^* = \{0^n1^n \mid n\ge 0\}$$ （0がすべて1より前に並び、かつ個数が等しい語）であり、これは正則でないことが証明済み。矛盾。よって $L$ は正則でない。
問題6 CMOS・加算器・カウンタ 解答
(1-1) pMOS 2個を並列に電源（$V_{DD}$）側へ、nMOS 2個を直列にGND側へ接続する（計4個）。どちらかの入力が0ならpMOSのどれかが導通して出力H、両方1のときだけnMOS直列路が導通して出力L → NAND。
(1-2) nMOSはソース側にLを劣化なく通せるが、Hを通すとしきい値電圧分低下する。pMOSはその逆でHを劣化なく通せる。よって出力をHに引き上げるプルアップ網にはpMOS、Lに引き下げるプルダウン網にはnMOSを使うと、常にフルスイングの論理レベルが得られる。
(2-1) $s=a\oplus b\oplus c_{\mathrm{in}}$、$c_{\mathrm{out}}=ab+bc_{\mathrm{in}}+ac_{\mathrm{in}}$（$=ab+c_{\mathrm{in}}(a\oplus b)$ でも可）。
(2-2) HA1 に $a,b$ を入力（和 $s_1$、桁上げ $c_1$）→ HA2 に $s_1, c_{\mathrm{in}}$ を入力（和 $s$、桁上げ $c_2$）→ $c_{\mathrm{out}}=c_1\ \mathrm{OR}\ c_2$。
(3) 桁上げが4段の全加算器を順に伝搬するので最悪 $4\tau$。改善方式：桁上げ先見加算器（キャリールックアヘッド）。
(4-1)
| $u$ | $y_1y_0$ | $D_1D_0$ | $u$ | $y_1y_0$ | $D_1D_0$ |
|---|---|---|---|---|---|
| 1 | 00 | 01 | 0 | 00 | 11 |
| 1 | 01 | 10 | 0 | 01 | 00 |
| 1 | 10 | 11 | 0 | 10 | 01 |
| 1 | 11 | 00 | 0 | 11 | 10 |
(4-2) $D_0=\bar{y_0}$（上下どちらでも下位ビットは毎回反転）。$D_1$ の1になるマスは $(u,y_1,y_0)=(1,0,1),(1,1,0),(0,0,0),(0,1,1)$ でK-map上は市松模様となり、隣接するマスの組がない → 簡単化できず、最簡積和形は $$D_1=\bar u\,\bar{y_1}\,\bar{y_0}+\bar u\,y_1y_0+u\,\bar{y_1}\,y_0+u\,y_1\bar{y_0}.$$ 排他的論理和では $D_1=\overline{u\oplus y_1\oplus y_0}$ と書ける。
問題7 移動平均フィルタとDTFT 解答
(1) $y[n]=\dfrac{1}{N}\bigl(x[n]+x[n-1]+\cdots+x[n-N+1]\bigr)$。インパルス応答が有限個（$N$ 点）で打ち切られているのでFIRフィルタ。
(2) 等比級数の和より $$H(e^{j\omega})=\frac{1}{N}\sum_{n=0}^{N-1}e^{-j\omega n}=\frac{1}{N}\cdot\frac{1-e^{-j\omega N}}{1-e^{-j\omega}} =\frac{1}{N}\cdot\frac{e^{-j\omega N/2}\bigl(e^{j\omega N/2}-e^{-j\omega N/2}\bigr)}{e^{-j\omega/2}\bigl(e^{j\omega/2}-e^{-j\omega/2}\bigr)} =\frac{1}{N}e^{-j\omega(N-1)/2}\,\frac{\sin(N\omega/2)}{\sin(\omega/2)}.$$
(3) $\sin(N\omega/2)=0$ かつ $\sin(\omega/2)\neq0$ となる $$\omega=\frac{2\pi k}{N}\quad(k=1,2,\dots,\lfloor N/2\rfloor)$$ で0になる。$\omega\to0$ では $|H|\to1$（直流利得1）。$\omega=0$ 付近で最大値をとり高周波側で減衰・振動するので、ローパス特性を持つ。
(4) (2)より位相は $-\omega(N-1)/2$（$\sin$比の符号反転による $\pm\pi$ の跳びを除く）で $\omega$ の一次式＝線形位相。線形位相では通過帯域内のすべての周波数成分が同一の群遅延 $(N-1)/2$ サンプルだけ遅れるため、成分間の相対位相が保たれ、波形が歪まない。
(5) $y[n]=\dfrac{1}{4}\sum_{k=0}^{3}x[n-k]$ に $x=\delta[n]+\delta[n-1]$ を代入して： $$y[0]=\tfrac14,\quad y[1]=y[2]=y[3]=\tfrac12,\quad y[4]=\tfrac14,\quad \text{他は }0.$$