早稲田大学 基幹理工学研究科 情報理工・情報通信専攻 専門科目 2026年度 院試 過去問 解答例・解説（全4問）

有限オートマトンで見るべき情報

偶奇だけで決まる言語は，過去の入力列全体ではなく偶奇の組だけを状態にすればよい。一方，$a$ と $b$ の個数比較は差がいくらでも大きくなり得るため，有限個の状態に押し込められない。

最小と極小の違い

集合被覆の手続きは「これ以上1個も削れない」状態を作るだけである。これは包含に関する極小性であり，集合数が最小であることとは異なる。反例を1つ出せることが答案上の決め手になる。

採点の置き所

正則性の判定では、$L_1,L_2$ は偶奇の組を4状態で記憶できること、$L_3$ は個数差を無限に記憶する必要があることを対比させる。論理式では、反例の構造、存在量化の証人、前件が偽のときの含意をそれぞれ明示する。集合被覆では、被覆性の不変条件、最小でない反例、$\Theta(n^2)$ の回数評価を分けて書く。

典型ミスと検算

$L_2$ は「または」なので、受理しない状態は $a$ が偶数かつ $b$ が奇数の場合だけである。$L_3$ の非正則性は、単にDFAを思いつかないことではなく、$a^n$ たちが異なる右合同類に分かれることで示す。集合被覆の反例は、残った集合族が極小であるが最小でないことを確認しておく。

スタックフレームの読み方

`addi sp,sp,-48' は領域確保，`sw fp,44(sp)' は呼出元のフレームポインタ保存，`addi fp,sp,48' は固定基準の設定である。 以後の $-36(fp)$ のような負のオフセットは，そのフレーム内の保存済み引数や局所変数を指す。

最適化の効果

最適化前のコードはデバッグしやすい形で全変数をフレームに置く。最適化後は，外部から観測されない局所変数を消去し，呼出規約で定められた返値レジスタだけを使う。

採点の置き所

記憶階層では、容量、速度、局所性の役割をレジスタ、キャッシュ、主記憶の順に比較する。RISC-Vのレジスタ指定は32本から5ビットを計算する。スタックフレームでは、$sp$ の減算、旧 $fp$ の保存、新 $fp$ の設定、各変数の負オフセット、返値レジスタ $x10$ を順に読み取る。

典型ミスと検算

非葉関数になったときに必要なのは、別関数呼び出しで $ra$ が上書きされることへの対策である。$fp$ と $sp$ の役割を混同すると、$fp-36$ や $fp-40$ の保存位置を逆に読みやすい。最適化後にメモリアクセスが消えるのは、局所変数の値がレジスタだけで保持でき、外部からその格納番地が観測されないためである。

電源変換

並列接続された同一の電圧源は，ノートン形に直すと理解しやすい。Aは $5\mathrm{A}$ の電流源と $1\Omega$ の並列，2台並列なら $10\mathrm{A}$ と $0.5\Omega$，これを戻すと $5\mathrm{V}$ と $0.5\Omega$ である。

最大電力条件

負荷で消費される電力が最大になるのは，負荷抵抗が負荷端子から見たテブナン抵抗に等しいときである。回路中に電流源がある場合でも，テブナン抵抗を求めるときは独立電流源を開放する。

採点の置き所

電源Aの等価回路は、2つの負荷条件から $E$ と $r$ の連立方程式を立てるところが得点の中心である。並列化したBは、開放電圧が同じで内部抵抗が半分になることを説明する。2の補数回路では、入力表から下位桁の規則を読み、$Y_1$ をXOR、$Y_2$ を $X_2\oplus(X_1\lor X_0)$ へ簡単化する過程を残す。

典型ミスと検算

同じ電圧源を並列にしても電圧は2倍にならない。ノートン形に直せば、電流源が足されて内部抵抗が並列合成されるだけで、テブナン電圧は $5\mathrm{V}$ のままである。最大電力の検算では、$V_{\mathrm{th}}=3\mathrm{V}$、$R_{\mathrm{th}}=3\Omega$ なので $P_{\max}=9/12=0.75\mathrm{W}$ とすぐ確認できる。

ヘッダ読解

TCPの最初の16ビットが送信元ポート，次の16ビットが宛先ポートである。データオフセットが5ならオプションなしの20バイトヘッダで，制御ビット $0x18$ はPSHとACKの組合せになる。

最長プレフィックス一致

ルーティング表は「先に載っているもの」ではなく，宛先アドレスに一致するもののうちプレフィックス長が最も長いものを選ぶ。どれにも一致しない場合だけデフォルト経路を使う。

採点の置き所

回線交換とパケット交換は、資源予約、帯域安定性、統計多重、遅延変動を対比する。レイヤ構成では、交換可能性と障害切り分けの2面を書く。TCPヘッダは16ビット、32ビット単位で区切って、ポート、シーケンス番号、データオフセット、フラグ、ウィンドウを順に読む。FIBは各宛先について一致候補を列挙し、最長のものを選ぶ。

典型ミスと検算

$0x18$ はACKとPSHであり、SYNではない。データオフセット5なら20バイトヘッダなので、オプションを仮定しない。最長プレフィックス一致では、より一般的な /22 より、該当すれば /24 や /26 が優先される。どの個別経路にも当たらない宛先だけが $0.0.0.0/0$ のデフォルト経路へ行く。