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

ハノイの塔の考え方

通常のハノイの塔では「何回動かすか」だけを見るが、本問では円盤ごとに費用が異なる。最大円盤は必ず1回だけ動き、それ以外の円盤の移動は左右に同じ小問題として2回現れる。この構造を見落とさなければ、漸化式は自然に $2T(n-1)+n^2$ になる。

多項式を足す理由

非斉次漸化式を斉次化する典型手法である。右辺の非斉次項が $n^2$ なので、同じ次数の多項式 $P(n)$ を加えて指数関数だけの形に直す。$P(n)-2P(n-1)$ の係数比較を書けば、計算の根拠が明確になる。

停止条件の本質

後半のプログラムは、2つの等差数列 $$M_0,\ M_0+M,\ M_0+2M,\ldots,\qquad N_0,\ N_0+N,\ N_0+2N,\ldots$$ の共通項を探している。共通項が存在すれば、両方の値が同じ $k$ にそろった回で停止する。共通項が存在しなければ、一方が追いつくたびに他方が先へ進むため、代入が永久に続く。

採点の置き所

ハノイの塔は、最大円盤を1回だけ動かすために同じ小問題が2回現れることを説明してから $T(n)=2T(n-1)+n^2$ を書く。閉形式では、$P(n)-2P(n-1)=-n^2$ の係数比較を見せると導出点が入る。プログラム停止条件では、2つの等差数列の共通項問題に変換し、中国剰余定理の条件 $\gcd(M,N)\mid(M_0-N_0)$ まで到達することが重要である。

典型ミスと検算

通常のハノイの塔の移動回数 $2^n-1$ をそのまま使うと、円盤ごとの費用 $i^2$ を無視している。求めた式は $T(1)=6\cdot2-1-4-6=1$ を満たすので初期条件で検算できる。停止しない例は、単に値が大きくなる例ではなく、合同式が解を持たない例を出す必要がある。

単位を先にそろえる

転送速度の問題は、バイト数、サイクル数、ミリ秒の順に単位をそろえると失点しにくい。1キロバイトを $1000$ バイトではなく $1024$ バイトとして計算する点に注意する。

ディスク待ち時間の分解

磁気ディスクの読み出し時間は、シーク時間、回転待ち時間、データ転送時間に分けて考える。ランダム配置の最悪ケースでは、各ブロックでほぼ最悪の待ちが起こると見積もる。一方、SCANは要求をトラック順に並べ替えるので、主にシーク時間を削減するアルゴリズムであり、回転待ちや転送時間そのものを消すわけではない。

LRUとFCFSの差

LRUは直近で使ったブロックを残すため、繰り返し現れる $A=(3,2)$ と相性がよい。FCFSでは、古く入った $A$ が途中で追い出されるため、同じ参照列でもミスが1回増える。キャッシュ問題では、各時点の中身を2枠の表として追うと機械的に判定できる。

採点の置き所

転送時間では、1KBを1024B、32ビットを4B、64ビットを8Bに直してからサイクル数を出す。ディスク読み出しでは、シーク、回転待ち、転送を別々に足すこと、SCANでは主にシーク回数が減ることを明示する。キャッシュ置換では、参照列を $A,B,A,C,A,D,A,E$ と記号化し、各時点の2枠の内容を書くと部分点が取りやすい。

典型ミスと検算

ランダム配置の10ブロックを1回のシークで読めると見なすと、最悪条件を使えていない。SCAN後の $119\mathrm{ms}$ は、シークがまとめられる一方で10ブロック分の回転待ちと転送が残る値である。LRUの5回に対してFIFO扱いのFCFSが6回になるのは、頻出する $A$ がFIFOでは途中で追い出されるためであり、ここを同じ回数にすると置換方針を区別できていない。

電圧計は回路を変える

内部抵抗が有限の電圧計を接続すると、端子は開放ではなく負荷接続になる。そのため、測定値は開放端電圧 $V_{\mathrm{Th}}$ そのものではなく、$R_{\mathrm{Th}}$ と電圧計内部抵抗の分圧になる。誤差率は $V_{\mathrm{Th}}$ の大きさに依存せず、抵抗比だけで決まる。

パリティ回路

XORは「1の個数の偶奇」を計算する演算である。$A\oplus B\oplus C$ は3ビット中の1の個数が奇数なら1、偶数なら0になる。奇数パリティを付けるには、全体が奇数になるようにその反転を付ければよい。

ドントケアを使う最小化

正しいパリティを満たさない入力は実際には現れないため、出力を0にも1にも選べる。これを使うと、素数判定の式は $P$ を含まない $F=C+\overline{A}B$ まで簡単になる。ドントケアを単なる空欄として扱わず、隣接グループを大きくするために使うのが要点である。

採点の置き所

電圧計の問題では、まず端子から見た $V_{\mathrm{Th}}$ と $R_{\mathrm{Th}}$ を求め、次に電圧計内部抵抗との分圧を計算する。相対誤差は測定値と開放電圧の差を開放電圧で割る。パリティでは、送信用の $P$ と受信側の誤り検出 $Z$ を分けて式にし、素数判定では対象となる入力値とドントケアの扱いを示す。

典型ミスと検算

理想電圧計とみなして $30\mathrm{V}$ と答えると、内部抵抗の指定を使っていない。測定値 $26.70\mathrm{V}$ は開放端電圧より小さく、誤差率も $5/(5+40.5)$ と抵抗比だけで決まるので検算しやすい。奇数パリティでは全体の1の個数を奇数にするため、$P=A\oplus B\oplus C$ ではなくその反転が必要である。

階層ごとに考える

ネットワークの記述問題は、データリンク層、ネットワーク層、トランスポート層、アプリケーション層に分けると抜け漏れが減る。MACアドレスは同一リンク内、IPアドレスはネットワーク間、ポート番号はホスト内のプロセス識別に対応する。

距離ベクトルの更新

距離ベクトル型では、Aがネットワーク全体の形を直接知っているわけではない。隣接ルータから受け取った距離情報に、自分からその隣接ルータへのリンクコストを加えて比較する。このため、1回目、2回目、3回目と、到達可能な経路情報がホップ数の広がりに応じて伝わっていく。

Web接続手順の採点ポイント

単に「Webページを開く」と書くのではなく、DHCP、認証、DNS、ARP、TCP、TLS、HTTP/HTTPSの役割を順に述べる。特に、URLが既知でもIPアドレスが既知とは限らないためDNSが必要であり、IPアドレスがわかっても次ホップのMACアドレス解決にはARPが必要である。

採点の置き所

選択問題は、正誤だけでなく各選択肢がMAC、IP、ルータ、ポート番号のどの性質に対応するかを説明すると得点が安定する。サブネットではホスト部6ビット、全64個、利用可能62個の順に書く。距離ベクトルでは、1回目と2回目でAがどの隣接ルータからどの距離を受け取るかを表にして、最終経路木まで更新過程を残す。

典型ミスと検算

距離ベクトルを最初から全体最短路問題として解くだけだと、更新回数ごとの設問に答えていない。$192.168.11.0/26$ のブロードキャストが .63 になることを確認すれば、ホスト数62も検算できる。Web接続手順では、MACアドレスがルータを越えて維持されると書くのは誤りで、リンクごとに張り替わる。