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

> 東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2026年度の院試過去問、3項目の解説。テーマは計算量理論、ソートアルゴリズム。大問1問の途中式・最終答を無料公開。解答PDFは5年分収録で2,880円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2026
- 解答・解説PDF: https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized（税込2,880円、5年分を収録）
- 最終更新: 2026-11-16
- 公式の過去問: https://www.i.u-tokyo.ac.jp/edu/course/ci/admission.shtml（2022〜2026、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 論理回路と二進演算

### 解説

**方針**

この問題は，個々の真理値表を暗記で処理するよりも「下位から最初に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回路と減算回路が
どちらも反転してしまう。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized

## 第2問 — 通信遅延と指数バックオフ

### 解説

**単位を先にそろえる**

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)$ が現れる。

### 解答

片道伝搬遅延は

$$
\frac{150\times 10^3}{3.0\times 10^8}=5.0\times 10^{-4}\ \mathrm{s}=0.5\ \mathrm{ms}
$$

である。また，4000 bitを10 Mbpsで送る時間は

$$
\frac{4000}{10\times 10^6}=4.0\times 10^{-4}\ \mathrm{s}=0.4\ \mathrm{ms}
$$

である。

- 往復で伝搬が2回，送信が2回，処理遅延が端末側とアクセスポイント側で1回ずつ入るので，
  

$$
\mathrm{RTT}_0=2(0.5+0.4+0.1)=2.0\ \mathrm{ms}.
$$

- 初回成功なら所要時間は $\mathrm{RTT}_0$，初回失敗なら1回分だけ余分に
  $\mathrm{RTT}_0$ がかかる。したがって期待RTTは
  

$$
(1-p)\mathrm{RTT}_0+p(2\mathrm{RTT}_0)=(1+p)\mathrm{RTT}_0
$$

  であり，$p=0.2$ では増加分は
  

$$
p\mathrm{RTT}_0=0.2\times 2.0=0.4\ \mathrm{ms}.
$$

- 符号化率を $R_c=k/n=0.8$ とすると，
  

$$
n=\frac{k}{R_c}=\frac{4000}{0.8}=5000\ \mathrm{bits}.
$$

- 符号化後の送信時間は片道
  

$$
\frac{5000}{10\times 10^6}=0.5\ \mathrm{ms}
$$

  なので，
  

$$
\mathrm{RTT}_{\mathrm{FEC}}=2(0.5+0.5+0.1)=2.2\ \mathrm{ms}.
$$

- 誤り率を $p$ とおくと，再送制御の期待RTTは $2.0(1+p)\ \mathrm{ms}$ である。
  FECが小さい遅延になる条件は
  

$$
2.20.1
$$

  である。$p=0.1$ では同程度，それより小さければ冗長ビットの送信時間の方が不利になる。
- 再送制御は，失敗時だけRTTが大きく伸びるため遅延のばらつきが大きい。FECは毎回同じ
  冗長度を払うため平均遅延は少し増えるが，遅延は安定する。音声・映像会議，遠隔操作，
  対話型配信のように一定の遅延上限が重要な用途ではFECが適している。
- 1回目の再送では各端末が2個のスロットから独立に選ぶ。同じスロットを選ぶ確率は
  $1/2$ なので，競合が解決する確率は
  

$$
P_1=1-\frac{1}{2}=\frac{1}{2}.
$$

- 1回目に再衝突する確率が $1/2$，2回目の再送では4個のスロットから選ぶので，異なる
  スロットを選ぶ確率は $1-1/4=3/4$ である。よって
  

$$
P_2=\frac{1}{2}\cdot\frac{3}{4}=\frac{3}{8}.
$$

- $i$ 回目の再送で再衝突する確率は $2^{-i}$ である。したがって，$k$ 回目で初めて解決
  する確率は
  

$$
P_k=\left(\prod_{i=1}^{k-1}2^{-i}\right)(1-2^{-k})
       =2^{-k(k-1)/2}(1-2^{-k})\qquad(k>1).
$$

### 最終答

$\mathrm{RTT}_0=2.0\,\mathrm{ms}$，再送制御の平均増加分は $0.4\,\mathrm{ms}$，FEC後の長さは5000 bit，$\mathrm{RTT}_{\mathrm{FEC}}=2.2\,\mathrm{ms}$，FECが遅延面で有利なのは $p>0.1$。バックオフは $P_1=1/2,\ P_2=3/8,\ P_k=2^{-k(k-1)/2}(1-2^{-k})$。

## 第3問 — 情報システム用語の説明

### 解説

**採点されやすい説明の形**

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

**選ぶ項目**

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

**典型ミス**

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

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized

---

出典: 院試hub（https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2026）。引用するときはWeb版のURLを示してください。
