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

座席列の数え方

人と人の間に2席以上空ける条件は、最初に必須の空席を置いてから余りを分配すると一気に簡単になる。$n$ 人の間には隙間が $n-1$ 個あり、それぞれに2個ずつ空席が必要である。残りの空席は、両端と各隙間に自由に追加できるので、重複組合せの形になる。

オーダー記法の否定

「ある定数で全ての十分大きい $n$ を押さえられる」の否定は、「どんな定数を選んでも、十分先に条件を破る $n$ がある」である。量化記号の順番を逆にすることが重要で、ここを曖昧にすると別の主張になってしまう。

短絡評価

論理演算の短絡評価では、式の形と真偽値によって評価する節点数が変わる。完全二分木でも、最良なら根から葉までの1経路だけで済む。一方、短絡が起こらなければ全節点を訪問するため線形時間になる。

採点の置き所

座席列では、必須の空席数 $2(n-1)$ と余りの分配先 $n+1$ 箇所を明示できていれば、二項係数の導出に点が入る。漸化式では、先頭が空席の場合と着席の場合を分け、後者で直後2席を固定する理由を書く。オーダー記法では量化子の順序を正しく反転し、短絡評価では最良が高さ、最悪が節点数に対応することを述べる。

典型ミスと検算

「間に2席以上」を $1(00^*1)^*$ としてしまうと、着席者間の空席数が1個でも許されるので誤りである。$S(29,10)$ は最小長 $28$ に1席だけ余るので11通り、$S(30,10)$ は2席余るので $\binom{12}{10}=66$ 通りとなり、値の大きさも自然である。$\Theta(2^n)$ と $\Theta(3^n)$ は底の違いではなく指数の比が発散するため別オーダーである。

固定フィールドの利点

RISC-Vは命令形式を単純にするため、主要なレジスタ番号フィールドを形式間で同じ位置に置いている。即値は分割されていても、レジスタ番号が固定なら、レジスタファイル読出しを早く開始できる。これは高クロック化やパイプライン化で重要になる。

制御信号の決め方

制御信号は「その命令でデータがどこから来て、どこへ行くか」を追うと決まる。R-typeはレジスタ2個からALUへ、ALU結果からレジスタへ戻る。S-typeはレジスタと即値からアドレスを作り、メモリに書く。使われない経路のMUX値は、書込みイネーブルが0なら結果に影響しない。

採点の置き所

レジスタ数の推定では、5ビットフィールドから $2^5=32$ 本を読むところが最初の得点箇所である。固定フィールドの利点は、命令型判定後に読む位置を切り替える必要がないこと、すなわちデコードとレジスタファイル読出しを並行しやすいことまで書く。制御信号表では、R-typeとS-typeのデータの流れを図上で追い、書込みイネーブルを明示する。

典型ミスと検算

S-typeでレジスタファイルを書き込むと、store命令の意味と矛盾する。MUX2はレジスタ書込みが無効なので任意だが、MUX1はアドレス計算に即値を使うため任意ではない。R-typeではメモリを書かない、S-typeではメモリを書く、という2点で制御表を検算すると取り違えを見つけやすい。

組合せ回路の最小化

真理値表から最小積和形を作る問題では、1になる行を主項、出力に影響しない行をドントケアとしてまとめる。ドントケアは「値が不明」ではなく「設計者が都合よく0または1を選んでよい」入力である。これによりカルノー図のグループを大きくでき、積項数やリテラル数を減らせる。

最大電力伝送

テブナン抵抗 $R_{\mathrm{Th}}$ をもつ端子対から負荷へ最大電力を送る条件は $R_L=R_{\mathrm{Th}}$ である。ただし、もとの回路に負荷以外の抵抗が含まれる場合、理想電圧源が供給する 全電力に対する負荷電力の割合は、テブナン等価回路だけから即座に50\%とはいえない。最大電力条件を求めた後、 もとの回路に戻して電源電流と負荷電力を計算するのが確実である。

採点の置き所

論理回路では、まず $D,E,F$ の各出力を真理値表から積和形に直し、次に $Z=D+EF$ で空欄を埋める順序が採点される。ドントケアの使用では、$D=1$ の行で $E,F$ が不要になる理由と、$Z=0$ の行では $D=0$ を保つ必要がある理由を書く。回路計算では、開放電圧、等価抵抗、最大電力、電源供給電力の順に分けると部分点を拾いやすい。

典型ミスと検算

ドントケアをすべて同じ値に固定すると、$D=A+C'$ まで簡単化できないことがある。最大電力の問題では、$R_L=R_{\mathrm{Th}}=5\Omega$ のとき負荷電力が $720\mathrm{W}$ で、供給電力 $2016\mathrm{W}$ より小さいので割合 $5/14$ は妥当である。ここを50\%と即答すると、テブナン内部以外の抵抗で消費される電力を見落としている。

プロトコル名と目的を対にする

ネットワークの穴埋め・記述問題では、用語だけでなく目的まで書けることが重要である。ARPはMACアドレス解決、DNSは名前解決、ICMPは診断、NAT/NAPTはアドレス変換、TCPは信頼性のあるバイトストリームを担当する。

TCPの基本語

SYN、ACK、FIN、シーケンス番号、ACK番号、重複ACK、タイムアウト、輻輳ウィンドウ、スロースタート閾値は、TCPの典型的な採点語である。各語を単独で暗記するのではなく、接続開始、信頼性制御、輻輳制御のどこに出てくるかを対応させる。

Web表示までの流れ

無線LAN接続では、まずリンク層でアクセスポイントにつながり、その後IP設定を取得する。URLを開く段階では、DNS、ARP、TCP、TLS、HTTP/HTTPSが順に関係する。階層をまたいでいるため、時系列で書くと読みやすい答案になる。

採点の置き所

OSI層の問題では、層名だけでなく、その層で扱う識別子や代表プロトコルまで対応させると安定して点になる。ARP、ICMP、DNS、NAT/NAPTは、何を何に対応させるか、または何を診断するかを一文で区別する。Web表示の記述は、無線接続、IP設定、名前解決、次ホップ解決、TCP/TLS、HTTP要求という順序で並べると欠落が少ない。

典型ミスと検算

DNSとARPを逆にしないことが重要である。DNSはホスト名からIPアドレス、ARPは同一リンク上でIPアドレスからMACアドレスを得る。NATは主にアドレス変換、NAPTはポート番号も含む変換であり、TCPのポート番号による多重化と混同しない。HTTPSではHTTP要求より前にTLSハンドシェイクが入る。