# 東大 情報理工学系研究科 コンピュータ科学専攻 専門科目（コンピュータ科学） 2023年度 院試 過去問 解答例・解説

> 東大 情報理工学系研究科 コンピュータ科学専攻 専門科目（コンピュータ科学） 2023年度の院試過去問、4項目の解説。テーマは正規表現・形式言語。大問1問の途中式・最終答を無料公開。解答PDFは6年分収録で3,200円。問題本文は非収録。

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

## 第1問 — 半分接頭辞と言語クラス

### 解説

**前半だけを見る操作**

$\Gamma(L)$ は，$L$ の語を同じ長さの前半・後半に分けたときの前半集合である。
接頭辞全体ではなく「ちょうど半分」である点が重要である。

**DFAでの構成**

後半 $w$ は存在すればよく，具体的に入力として読む必要はない。
残り長さが $t$ のときに受理状態へ到達できる状態集合を逆向きに更新すれば，
有限個の状態で管理できる。

### 解答

- $L_2=(ab)^n\ (n\ge0)$ の語の長さは $2n$ であり，$\Gamma(L_2)$ は
その前半，すなわち $(ab)^n$ の長さ $n$ の接頭辞全体である。
偶数長なら $(ab)^m$，奇数長なら $(ab)^m a$ になるので

$$
\boxed{\Gamma(L_2)=(ab)^*(\varepsilon+a)}
$$

である。
- $a^n b^n a^m b^m$ の全長は $2(n+m)$ であるから，前半の長さは $n+m$ である。
$m\le n$ のとき，前半は

$$
a^n b^m
$$

であり，$m\ge n$ のとき，前半は

$$
a^n b^n a^{m-n}
$$

である。したがって

$$
\Gamma(L_3)
=\{a^n b^m\mid n\ge m\ge0\}
\cup
\{a^n b^n a^r\mid n,r\ge0\}.
$$

これを生成する文脈自由文法の一例は次である。

$$
\begin{array}{rcl}
S&\to&S_1\mid S_2,\\
S_1&\to&aS_1b\mid aS_1\mid \varepsilon,\\
S_2&\to&CR,\\
C&\to&aCb\mid \varepsilon,\\
R&\to&aR\mid \varepsilon.
\end{array}
$$

- DFA $M=(Q,\Sigma,\delta,q_0,F)$ に対して，$\Gamma(L_M)$ を受理するDFAを作る。
入力として読んだ部分を $v$ とする。必要なのは

$$
\delta(q_0,v)\in \mathrm{Pre}_{|v|}(F)
$$

である。ここで

$$
\mathrm{Pre}_t(F)=\{q\in Q\mid \exists w\in\Sigma^t,\ \delta(q,w)\in F\}
$$

とする。
状態を

$$
Q\times 2^Q
$$

とする。第1成分 $p$ は $\delta(q_0,v)$，第2成分 $A$ は
$\mathrm{Pre}_{|v|}(F)$ を表す。初期状態は

$$
(q_0,F)
$$

である。文字 $c$ を読むと

$$
p\mapsto \delta(p,c),\qquad
A\mapsto \{q\in Q\mid \exists x\in\Sigma,\ \delta(q,x)\in A\}
$$

と更新する。受理状態は

$$
\{(p,A)\mid p\in A\}
$$

である。これにより，読んだ語 $v$ と同じ長さの後半 $w$ を付けて
$vw\in L_M$ とできるかを判定できる。
- 命題は真である。$L$ を受理するプッシュダウンオートマトン $P$ を用いる。
入力 $v$ を読む間，$P$ にはそのまま $v$ を読ませ，同時に長さを数えるための
マーカーをスタックに1個ずつ積む。
入力を読み終えたら，今度は入力を消費せずに，後半 $w$ を非決定的に生成する。
1文字生成するたびに長さマーカーを1個取り除き，その文字を $P$ に読ませる。
マーカーがすべてなくなった時点で $P$ が受理状態に入れるなら受理する。
このPDAは，ある $w$ が存在して $|w|=|v|$ かつ $vw\in L$ である場合に
ちょうど受理する。したがって $\Gamma(L)$ は文脈自由言語である。

### 最終答

$$
\Gamma((ab)^*)=(ab)^*(\varepsilon+a).
$$

$\Gamma(L_3)$ は本文の文法で生成できる。正規言語・文脈自由言語はいずれも
$\Gamma$ に関して閉じている。

## 第2問 — 集合分割の近似アルゴリズム

### 解説

**平均下界と最大要素下界を組み合わせる**

この問題の近似比の証明では，最適値 $\mathrm{OPT}$ に対する基本的な下界を2つ使う。
1つは総和を $m$ 個に分ける以上，最大和は平均値 $\|P\|/m$ 以上であるという下界である。
もう1つは，どの要素もどこかの集合に入るため，最大要素そのものも $\mathrm{OPT}$ 以下である
という下界である。終了条件は
$\|S_j\|\le \mathrm{top}(S_j)+\|S_k\|$ と読み替えられるので，
この2つを足すだけで2近似が出る。

**ループ回数の証明で見るべき不変量**

一見すると，移動した要素が別のスタックからまた戻ってくる可能性がありそうに見える。
ここで効く不変量は「全体の最小和は減少しない」という性質である。
ある要素 $x$ が移動した時点の移動先の既存部分の和を $a$ とすると，
その後に $x$ を再び動かすには，現在の最小和が $a$ より小さくなっている必要がある。
しかし最小和は減少しないため，これは起こらない。
したがって，各要素は高々1回しか移動せず，反復回数は $n$ で抑えられる。

**データ構造の選び方**

このアルゴリズムで毎回必要なのは「最大和のスタック」と「最小和のスタック」である。
全スタックを毎回走査すると1回 $O(m)$ かかり，全体で $O(nm)$ になってしまう。
和をキーにしたヒープを使えば，最大・最小の取得と更新を対数時間にできる。
スタック本体とスタック和を分けて管理するのが，実装上の要点である。

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

## 第3問 — ページ置換

### 解説

**LRUと最適置換の違い**

LRUは過去を見て「最も長く使われていないページ」を捨てる。最適置換は未来を見て
「次に使うのが最も遅いページ」を捨てる。試験では，この2つを混同せず，表を作って
1参照ずつ追うことが重要である。

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

## 第4問 — キャッシュとCPI

### 解説

**リトルエンディアン**

リトルエンディアンでは，数値の低位バイトが小さいアドレスに置かれる。
整数値をそのまま16進で左から読むのではなく，バイト単位に分解してアドレス順を考える。

**CPI式の作り方**

キャッシュミスペナルティは「1命令あたり何回そのミス機会があるか」にミス率とペナルティを
掛ける。命令キャッシュは全命令，データキャッシュはロード・ストア命令だけが対象である。

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

---

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