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

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

- Web版: https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2025
- 解答・解説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問 — 形式言語とオートマトン

### 解説

**平方根言語の見方**

$H(L)$ は「同じ語を2回続けたものが $L$ に入るか」を見る操作である。
したがって，単に正規表現を半分に切るのではなく，$ww$ の前半と後半に同じ構造が
現れることを使う。(1)では2個の $c$ の位置が強い制約になっている。

**正規言語で閉じる理由**

正規言語では，語そのものを覚える必要はない。語 $w$ がDFAの状態集合上に作る
有限個の状態変換だけを覚えればよい。有限集合 $Q$ に対する写像は高々
$|Q|^{|Q|}$ 個なので，これを状態にしたDFAが作れる。

**文脈自由言語で同じ議論が使えない理由**

プッシュダウンオートマトンでは，$w$ を1回読んだあとに同じ $w$ をもう一度
同じ順序で読むことを有限制御だけでは表せない。スタックに $w$ を積むと取り出しは
逆順になるため，正規言語のように「変換だけを持つ」という処理ができない。
このため，文脈自由言語では反例が存在する。

### 解答

- 語 $w$ が $H(L_2)$ に属する条件は，$ww$ が

$$
a(a+b)^*c(a+b)^*bc
$$

の形に入ることである。この正規表現に現れる $c$ は2個であり，2個目は末尾の
$c$ である。したがって $ww$ の前半 $w$ も1個の $c$ を含み，その
$c$ は $w$ の末尾でなければならない。
$w=xc$ と書くと，

$$
ww=xcxc
$$

である。これが上の正規表現に入るためには，最初の $x$ は
$a(a+b)^*$ に属し，2つ目の $x$ は $(a+b)^*b$ に属する必要がある。
よって

$$
x\in a(a+b)^*b
$$

であり，

$$
\boxed{H(L_2)=a(a+b)^*bc}
$$

となる。
- 各語が与える状態変換だけを見る。状態を $q_0,q_1$ とし，文字1つが誘導する
写像を考えると

$$
\begin{array}{c|cc}
 & q_0 & q_1\\ \hline
a & q_0 & q_0\\
b & q_1 & q_1\\
c & q_1 & q_0
\end{array}
$$

である。語 $w$ が誘導する写像を $f_w$ と書くと，

$$
w\in H(L_3)
\quad\Longleftrightarrow\quad
f_w(f_w(q_0))=q_1
$$

である。
到達し得る写像は次の4種類である。

$$
I,\quad C_0:q_0,q_1\mapsto q_0,\quad
C_1:q_0,q_1\mapsto q_1,\quad
S:q_0\leftrightarrow q_1.
$$

このうち $f(f(q_0))=q_1$ を満たすのは $C_1$ だけである。
ただし，$I$ と $S$ はこの判定に関して同値であり，最小化すると3状態で足りる。
最小DFAを

$$
Q=\{A,B,C\},\qquad q_{\mathrm{init}}=A,\qquad F=\{C\}
$$

とする。ここで $A$ は $I,S$ を併合した状態，$B=C_0$，$C=C_1$ である。
遷移は

$$
\begin{array}{c|ccc}
 & a & b & c\\ \hline
A & B & C & A\\
B & B & C & C\\
C & B & C & B
\end{array}
$$

で与えられる。
- 命題は真である。正規言語 $L$ を受理するDFAを

$$
M=(Q,\Sigma,\delta,q_0,F)
$$

とする。語 $w$ が $M$ 上で誘導する状態変換を

$$
f_w(q)=\delta(q,w)
$$

とおく。すると

$$
w\in H(L)
\quad\Longleftrightarrow\quad
\delta(q_0,ww)\in F
\quad\Longleftrightarrow\quad
f_w(f_w(q_0))\in F
$$

である。
そこで，状態集合を有限集合 $Q^Q$ とするDFAを作る。初期状態は恒等写像
$\mathrm{id}$ とし，文字 $x$ を読んだとき

$$
f\longmapsto \delta_x\circ f,
\qquad
\delta_x(q)=\delta(q,x)
$$

と更新する。受理状態は

$$
\{f\in Q^Q\mid f(f(q_0))\in F\}
$$

である。このDFAはちょうど $H(L)$ を受理するので，$H(L)$ は正規言語である。
- 命題は偽である。反例として

$$
L=\{a^n b^n a^{2m}b^k a^k\mid n,m,k\ge 0\}
$$

を考える。この言語は

$$
a^n b^n,\quad a^{2m},\quad b^k a^k
$$

を順に生成すればよいので文脈自由である。
一方，$w\in H(L)$ なら $ww\in L$ である。$ww$ が上の形に入るためには，
$w$ は

$$
w=a^n b^n a^n
$$

の形でなければならない。実際，

$$
ww=a^n b^n a^n a^n b^n a^n
=a^n b^n a^{2n}b^n a^n
$$

であり，これは $m=n,\ k=n$ として $L$ に属する。逆も同様に従う。
したがって

$$
H(L)=\{a^n b^n a^n\mid n\ge 0\}
$$

である。これは標準的な非文脈自由言語である。よって，文脈自由言語全体は
$H$ に関して閉じていない。

### 最終答

$$
H(L_2)=a(a+b)^*bc.
$$

$H(L_3)$ の最小DFAは3状態で，遷移表は本文の通り。
正規言語についての命題は真，文脈自由言語についての命題は偽である。

## 第2問 — パイプラインとキャッシュ

### 解説

**CPIの分解**

この問題では，総サイクル数を

$$
\text{命令実行の基本サイクル}
+\text{ロードユースストール}
+\text{キャッシュミスストール}
+\text{分岐ミスペナルティ}
$$

に分けると見通しがよい。パイプラインの立ち上がり・終了コストは問題文で無視してよい
扱いなので，基本サイクルは命令数そのものとして数える。

**ラインサイズの決まり方**

配列を4バイト刻みで順に読む場合，キャッシュラインサイズが $B$ バイトなら，
1本のラインに $B/4$ 個のアクセスが入る。初期状態が空なので，各ラインの最初の
ロードだけがミスになる。ここでは合計1024バイトを走査してミスが32回なので，
1ラインは $1024/32=32$ バイトである。

**命令フォーマットの比較**

レジスタ番号の位置をそろえる設計は，レジスタファイルの読み出しポートに渡す信号を
単純にできる。一方で，即値を分割すると，命令種別に応じた連結・並べ替え・符号拡張の
回路が必要になる。実際の命令セットでも，この2つはしばしばトレードオフになる。

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

## 第3問 — スケジューリングとセマフォ

### 解説

**待ち時間の数え方**

待ち時間には実行可能キューで待つ時間だけでなく，セマフォの待ちキューで待つ時間も
含まれる。全プロセスが終了する場合は

$$
\text{待ち時間}=\text{終了時刻}-\text{到着時刻}-\text{実行時間}
$$

でまとめて計算できるので，途中でどのキューにいたかを細かく足し上げるより安全である。

**SRTFとセマフォの相互作用**

セマフォがないSRTFでは，時刻20に到着した短い $P_5$ が $P_1$ を中断する。
しかし(3)では $P_5$ は $S_1$ を取得できないため待ちに入り，$P_1$ がそのまま
終了まで進む。このように，優先度が高いプロセスでも資源を取れなければ実行できない。

**デッドロックの確認**

(4)のRRでは，$P_2$ と $P_3$ が逆順に $S_1,S_2$ を要求する。
片方が $S_1$ を持って $S_2$ を待ち，もう片方が $S_2$ を持って $S_1$ を待つと，
どちらも進めない。時刻80でこの循環待ちが完成する。

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

## 第4問 — グラフの連結度とサイクル

### 解説

**サイクルと2本のパス**

2点 $a,b$ を含むサイクルは，サイクル上で $a$ から $b$ へ進む2通りの向きの
パスに分解できる。この2本は端点以外の頂点を共有しない。逆に，内点素な2本の
$a$-$b$ パスを合わせればサイクルになる。この対応が(1)の中心である。

**新しい頂点を足す補題**

(2)は，あとで「指定された点集合」を「新しい1点の近傍」として扱うための準備である。
$u$ を消さない場合でも，$A$ には $k$ 点あり，削除できるのは高々 $k-1$ 点なので，
$u$ とつながる頂点が必ず1つ残る。この数え上げが証明の要点である。

**一般化の構造**

高連結性は，ある頂点から既存のサイクルへ多数の互いに独立な接続路を保証する。
接続点が指定点の数より1つ多くあるため，指定点を含まない弧を避けてサイクルを
作り直せる。これが「$k$ 連結なら任意の $k$ 点が同一サイクルに乗る」理由である。

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

---

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