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

NFAから正規表現へ

最初の状態に $0,1$ の自己ループがあるので，任意の接頭辞を読み飛ばせる。その後に $1,1$ を読み，受理状態では $0$ のみを許すため，末尾側の形は $110^*$ になる。

スキップリスト

探索は「下に行けるだけ下に行き，右に進めるだけ進む」の繰り返しである。挿入後の昇格は確率的に止まるので，高さの期待値が対数になり，探索・挿入とも期待 $O(\log n)$ になる。

採点の置き所

NFAでは、受理される語の形を「任意の接頭辞」「連続する2個の1」「その後は0だけ」に分解して正規表現へ落とす。部分集合構成は、到達可能な状態集合と受理状態を含む集合を区別することが採点対象である。スキップリストでは、番兵、探索経路、昇格時に上段を追加する処理、期待 $O(\log n)$ の根拠を順に書く。

典型ミスと検算

正規表現を $(0+1)^*11(0+1)^*$ とすると、11の後に1が出る語まで許してしまう。末尾側が $0^*$ に限られる点を忘れない。スキップリストの空欄は、上方向の位置と直前に挿入した下段ノードを結ぶためのものであり、水平ポインタだけを考えると `above(p)' と $q$ の役割を逆にしやすい。

行優先配置

Cの2次元配列は右端の添字が連続アドレスになる。$a[j][k]$ は連続アクセス，$a[k][j]$ は大きなストライドアクセスであり，キャッシュミス数が大きく変わる。

競合ミスと局所性

ダイレクトマップで同じインデックスに写るデータを交互に触ると，容量が足りていても追い出し合う。連想度とブロッキングは，この追い出し合いを減らす代表的な対策である。

採点の置き所

キャッシュ容量、ラインサイズ、配列要素サイズから、インデックス、オフセット、1ラインあたりの要素数を先に確定する。プログラム1と2の差は、Cの行優先配置に対して添字のどちらが連続するかで説明する。プログラム3では先頭アドレス差がキャッシュ容量の整数倍であることを示し、ブロッキングでは短時間内の再利用を述べる。

典型ミスと検算

512個のintは2048Bなので、列方向アクセスでは64Bラインをほぼ活かせない。一方、行方向アクセスでは16個に1回だけミスするため32回になる。この512回と32回の差が出ていれば、行優先配置を正しく読めている。連想度増加は競合ミス対策であり、空間局所性そのものを増やすわけではない点も区別する。

テブナン等価

端子に接続する負荷だけを変える問題では，まず端子から見た開放電圧と等価抵抗を求めると，電流も最大電力も一気に決まる。

2の補数の桁あふれ

符号付き加算のオーバーフローは，最上位桁の単なるキャリーアウトではない。同符号加算で符号が反転したか，またはキャリーインとキャリーアウトが異なるかで判定する。

採点の置き所

端子等価回路では、開放時の節点方程式と、独立源を止めたときの等価抵抗を分けて書く。最大電力は $R_c=R_{\mathrm{th}}$ と $P_{\max}=V_{\mathrm{th}}^2/(4R_{\mathrm{th}})$ の両方が採点対象である。論理回路では、半加算器、多数決キャリー、符号付き桁あふれの3つを別々に導出する。

典型ミスと検算

端子電圧の向きを逆にすると電流方向も逆になるため、$a\to b$ の向きと $V_a-V_b$ の定義をそろえる。$R_c=0.6\Omega$ で $I=0.25\mathrm{A}$ なら負荷電圧は $0.15\mathrm{V}$ で、テブナン電圧 $0.5\mathrm{V}$ より小さいので妥当である。2の補数のオーバーフローをキャリーアウトだけで判定しないことも重要である。

アドレスの役割

MACアドレスはリンク内配送，IPアドレスはネットワークを越えた配送に使う。名前解決とアドレス解決は混同しやすいが，DNSは名前からIP，ARPはIPからMACである。

TCPフラグ

ポート80はHTTP/WWWの代表的な待受ポートである。ACKが立っておらずSYNのみが立つセグメントは，通常，クライアントが接続を開始するときの最初のセグメントである。

採点の置き所

プロトコルの定義では、規約という一般説明だけで終えず、IP、TCP、HTTPがそれぞれどの層で何を決めるかを書く。TCPヘッダ読解では、送信元ポート、宛先ポート、フラグ、通信方向を順に読む。サブネット、スロースタート、IGP/EGPは短答でも計算根拠や用途の違いを一語添えると部分点が安定する。

典型ミスと検算

宛先ポート80を見ても、SYNのみならまだHTTP要求本文は送られていない。接続開始セグメントとHTTPデータを混同しない。$10.0.0.0/16$ を8分割するには3ビット借りるので /19 であり、/24 では256分割になってしまう。スロースタートは5RTT後に $1\to2\to4\to8\to16\to32$ と数えて検算する。