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

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

- Web版: https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2024
- 解答・解説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問 — 最尤推定と混合正規分布

### 解説

**方針**

前半は最尤推定の標準計算である。対数を取ると積が和になり，正規分布では二乗和を最小にする
平均と，その平均まわりの平均二乗偏差が現れる。分散の推定量で分母を $N$ にする点は，
不偏推定量との混同が起きやすい。

**EMの見方**

混合正規分布で難しいのは，各観測値がどの成分から来たか分からないことである。EM法は，
この不明な割当を責任度 $\gamma_{nk}$ という軟らかい重みで補い，重み付きの単一正規分布
推定へ分解する方法と見ればよい。Eステップは割当の推定，Mステップは重み付き平均と
重み付き分散の再計算である。

**採点上の注意**

Jensenの不等式を使う箇所では，$\lambda_{nk}$ を導入してから
$\lambda_{nk}(\pi_k\varphi_k/\lambda_{nk})$ と書き直す一行が重要である。この一行がないと，
なぜ下界が補助関数になっているのかが伝わらない。また，混合比の更新では
$\sum_k\pi_k=1$ の制約を忘れず，ラグランジュ未定乗数または正規化の議論を添えるとよい。

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

## 第2問 — ハミング距離検索と専用回路

### 解説

**方針**

検索前処理の問題では，表を大きくすると一回の検索は速くなるが空間が増える。長さ $b$ の
全ビット列を直接見る表は速い一方で $2^b$ の欄を持つ。長さを半分に分けると空間は
 $2^{b/2}$ まで落ちるが，候補が $N/2^{b/2}$ 程度残るので照合が必要になる。

**半径1検索の考え方**

全体で1ビット以下しか違わないなら，前半か後半のどちらかは必ず完全一致する。この必要条件で
候補を拾い，最後に厳密な距離を計算する。これは「拾い漏らしをしない粗い条件で候補を作る」
という近傍検索の基本形である。

**回路の注意**

ハミング距離回路は，不一致ビットを数える加算回路である。最初に各ビットでXORを作り，
その後は1の個数を足し上げる。4ビットでは最大値が4なので3ビット出力が必要であり，
最高位の桁上がりを落とすと距離4を表せない。

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

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

### 解説

**方針**

用語説明では，最初に一文で定義し，続けて仕組み，最後に利点や注意点を書くと答案が安定する。
単語の日本語訳だけではなく，どの入力に対して何を出す技術なのかを明確にするとよい。

**選択の理由**

上の4項目は，いずれも短い行数で具体例や計算量上の特徴を書きやすい。動的計画法は状態遷移，
BNFは生成規則，キャッシュは遅延削減と一貫性，$k$-近傍法は距離尺度と $k$ の選択という
採点されやすい観点を含められる。

**典型ミス**

動的計画法を単なる再帰，BNFをプログラムそのもの，キャッシュを常に正しい複製，$k$-近傍法を
クラスタリングと書くと不正確である。用途だけでなく，内部で何を保存し，何を比較し，どの条件で
性能が変わるかを一つ添えると説明の説得力が増す。

### 解答

ここでは，動的計画法，BNF，広域ネットワークのトランスペアレントキャッシュ，
$k$-近傍法の4項目を選ぶ。

**動的計画法**

動的計画法は，大きな問題を重複する部分問題に分け，部分問題の解を表に保存して再利用する
設計手法である。典型例は最短経路，ナップサック問題，編集距離であり，状態と遷移を定義して
小さい状態から順に値を埋める。再帰をそのまま実行すると同じ部分問題を何度も解くが，メモ化
または表形式の計算により多項式時間へ改善できる。成立条件は，最適解が部分問題の最適解から
構成できることである。

**BNF**

BNFは，プログラミング言語やデータ形式の構文を再帰的な生成規則で表す記法である。
非終端記号を山括弧などで表し，それがどの記号列へ置き換えられるかを規則として書く。
たとえば式を「項」「演算子」「式」の組合せとして定義すれば，パーサは入力列が文法に従うかを
機械的に判定できる。自然言語の説明より曖昧さが少なく，コンパイラや通信プロトコル仕様で
使いやすい。

**広域ネットワークのトランスペアレントキャッシュ**

トランスペアレントキャッシュは，利用者やアプリケーションが明示的に設定しなくても，
ネットワーク上の中継点がコンテンツを一時保存して再利用する仕組みである。遠隔サーバから
同じデータを毎回取得せず，近い場所のキャッシュから返すことで遅延と外部回線の負荷を下げる。
一方で，古い内容を返さないための有効期限管理，認証付き通信との相性，プライバシー保護が
重要になる。WebプロキシやCDNの考え方と近い。

**$k$-近傍法**

$k$-近傍法は，未知データの周辺にある学習データを距離で探し，その近傍のラベルや値から
分類・回帰を行う手法である。分類では，距離が近い $k$ 個のデータの多数決でクラスを決める。
モデルの学習は軽いが，予測時には多くのデータとの距離計算が必要になりやすい。距離尺度，
特徴量のスケーリング，$k$ の選び方に結果が大きく依存するため，高次元データでは近似探索や
次元削減を併用することが多い。

### 最終答

選択した4項目について，動的計画法は部分問題の再利用，BNFは構文の生成規則，トランスペアレントキャッシュは利用者に意識させない中継保存，$k$-近傍法は距離に基づく近傍多数決・平均化として説明できる。

---

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