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

番兵付き挿入整列

行14--18は単なる前処理ではなく，最小値を左端に置くことで内側ループの停止を保証している。行24の回数を数えるときは，元の反転数ではなく，この前処理で消えた反転を差し引く。

データ構造の前提

配列キューを素朴に先頭詰めで実装すると dequeue が $O(N)$ になるが，問題文は最も効率のよい実現を仮定している。循環バッファを使うため $O(1)$ と判断する。

採点の置き所

オートマトンでは、受理言語、同値なNFA、正規文法、$A^*$、交差の空性を順に対応させる。データ構造の計算量は、スタックとキューをどの端で操作するかを明示して $O(1)$ と答える。挿入整列では、番兵処理後に残る反転数を数えること、特に降順とブロック条件の差を説明することが採点対象である。

典型ミスと検算

$A^*$ は奇数個の0の連結だけでなく、空語と偶数個の0も作れるので $0^*$ 全体になる。$A\cap0^*1$ は末尾が1である時点で空である。降順24要素の行24回数は $\binom{23}{2}$ ではなく、番兵処理で最小値が左端に移った後の残り23要素の反転数 $\binom{23}{2}=253$ と見ると検算しやすい。

プロセスごとのアドレス空間

ページテーブルは仮想アドレスから物理アドレスへの対応表である。プロセスごとに仮想アドレス空間が独立しているので，同じ仮想アドレスでもプロセスが違えば別の変換表を使う。

copy-on-write

COWの狙いは，fork直後に大量の物理ページをコピーしないことである。ただし仮想アドレス空間を表すためのページテーブルまで不要になるわけではない。

採点の置き所

再帰呼び出しでは、呼び出しごとに別フレームが作られること、戻り番地と局所変数がフレームごとに管理されることを書く。ページテーブルでは、仮想アドレス空間サイズをページサイズで割ってエントリ数を出す。2段ページテーブルでは、オフセット、2段目インデックス、1段目インデックスのビット分割を明示する。

典型ミスと検算

5プロセスでページテーブルを共有できるとすると、独立した仮想アドレス空間という前提を落としている。$2^{32}/2^{11}=2^{21}$、$32-12-10=10$ のように指数で計算すると、桁ずれを見つけやすい。COWは実データページのコピーを遅らせる仕組みであり、ページテーブルや管理情報までゼロになるわけではない。

電流源の電力符号

電源が供給するか吸収するかは，電流が高電位端子から入るかどうかで決まる。この問題では電流源の電流方向に沿った電圧が負になるため，電流源は電力を供給している。

加減算器

2の補数減算では，ビット反転と最下位キャリー1の両方が必要である。制御信号の意味を取り違えると，XNORとXOR，NOTとバッファが逆になる。

採点の置き所

回路では、節点方程式から端子電圧を求め、独立源を止めて等価抵抗を出し、電圧源と電流源それぞれの電力符号を判定する流れが採点される。加減算器では、$M=1$ が加算、$M=0$ が減算という指定から $Z_i$ の真理値表を作り、初段キャリーと桁あふれ条件を別に答える。

典型ミスと検算

電流源の電力は、電流の向きに沿った電圧が負なら供給である。$100\mathrm{V}$ 源の供給 $2100\mathrm{W}$ と10A源の供給 $300\mathrm{W}$ は、抵抗消費電力の合計と整合する。減算時に $Y$ を反転して初段キャリー1を足す必要があるため、反転器だけ、またはキャリーだけでは2の補数減算にならない。

リンク層とネットワーク層

MACアドレスは次ホップまでの配送に使われる。一方，IPアドレスはエンドツーエンドの宛先を表すので，通常のルータ転送では送信元・宛先IPアドレスは変化しない。

累積ACK

TCPの確認応答番号は「次に受け取りたいバイト番号」である。1000バイトのセグメントが $seq=1$ から5本続けば，最後まで揃った後のACKは5001になる。

採点の置き所

フレームA/Bの表では、MACアドレスが各リンクで張り替わり、IPアドレスはエンドツーエンドで維持されることを明示する。パケット判定は、IPヘッダのProtocol番号、TCP宛先ポート、ペイロードの文字列、SYNフラグを根拠にする。Go-back-Nとスロースタートでは、ACK番号とウィンドウ増加を数式または時系列で示す。

典型ミスと検算

ルータ転送で送信元IPをルータのIPに変えると、通常のIP転送ではなくNATを仮定した答案になってしまう。TCPのACK番号は受信済み最後の番号ではなく次に欲しい番号であるため、最後の1000バイトが $4001$ から始まるならACKは $5001$ になる。スロースタート後の $2W$ は1RTT後の値であり、1ACKごとの増加とRTT単位の倍増を混同しない。