東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2026年度 院試 解答例・解説

方針

この問題は，個々の真理値表を暗記で処理するよりも「下位から最初に1が現れるまで」という 条件を接頭辞ORとして数式化するのが安全である。$i$ 番目の出力は $i$ より下位のビットだけを 見れば決まるので，入力 $x_i$ 自身を含めない点に注意する。

典型ミス

$y_i=\overline{x_0\lor\cdots\lor x_i}$ としてしまうと，最初に1が現れたビットまで0になり， 例に合わない。減算回路でも，同じ理由で「最初の1を含めて反転する」ことを確認してから $T_4$ の出力をXORの制御に使う必要がある。

採点上の注意

回路図を描く設問では，ゲート数だけでなく，どの入力がマルチプレクサの選択信号なのかを 明示することが重要である。特に $s=0$ で $a$ を選ぶ向きを取り違えると，XOR回路と減算回路が どちらも反転してしまう。

単位を先にそろえる

Mbpsは $10^6$ bit/s として扱う。伝搬距離と伝送速度を混同すると，0.5 msと0.4 msの 寄与を逆にしたり，片道と往復を取り違えたりしやすい。RTTでは伝搬・送信・処理がそれぞれ 往復で何回入るかを表にしてから足すとよい。

FECと再送の比較

再送制御の期待遅延は「失敗時だけ余分に1 RTT」と見ると一行で出る。FECは誤りを消す代わりに 毎回パケットを長くする方式なので，誤り率が低い領域では損になり，高い領域では得になる。 境界 $p=0.1$ は追加遅延 $0.2\ \mathrm{ms}$ と再送の期待追加遅延 $2.0p\ \mathrm{ms}$ を等置しても得られる。

バックオフの積

$k$ 回目で初めて解決する事象は，「1回目から $k-1$ 回目までは同じスロットを選び， $k$ 回目で異なるスロットを選ぶ」という積である。指数バックオフではスロット数が倍々に 増えるため，衝突確率の指数の和 $1+2+\cdots+(k-1)$ が現れる。

採点されやすい説明の形

用語説明では，最初の1文で定義を置き，続けて仕組み，最後に利点・限界・計算量のいずれかを 述べると答案が安定する。単に「重要な技術である」と書いても点になりにくい。

選ぶ項目

短時間で高得点を狙うなら，計算量や具体的な機構を書きやすい項目を選ぶのがよい。マージソートは $O(n\log n)$，仮想記憶はページテーブルとページフォルト，Transformerは自己注意の式まで 書けるため，説明の密度を出しやすい。

典型ミス

Transformerを単に大規模言語モデルの名前として書く，ガベージコレクションを手動解放と混同する， 仮想記憶をキャッシュと同一視する，といった誤りは減点されやすい。専門用語を並べるだけでなく， 「何を入力として何を解決する仕組みか」を明確にすることが大切である。