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

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

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

### 解説

**削除操作の見方**

$\odot$ は連続部分文字列の削除ではなく，部分列の削除である。
したがって $ababa\odot ab$ では，1文字目の $a$ と4文字目の $b$ を
削除する場合も考える必要がある。この点を落とすと(1)の列挙で漏れが出る。

**正規表現の作り方**

$(ab)^*$ では $a$ は各ブロックの先頭に1つずつ現れる。
2つの $a$ を消すと，それぞれのブロックは $b$ だけになる。
その前，間，後ろには通常の $ab$ ブロックが任意個残るため，
$(ab)^*b(ab)^*b(ab)^*$ という形が自然に出る。

**オートマトン構成の核心**

残す文字は入力として読む。削除する文字は入力には現れないので
$\varepsilon$ 遷移で処理する。この2種類の遷移を同じ $A_1$ 上で動かすことで，
「残した語」と「削除した語」を合わせたものが $L_1$ に属するかを確認できる。
文脈自由の場合も同じ発想で，削除列を有限オートマトンではなく
プッシュダウンオートマトンに読ませればよい。

### 解答

- まず，各語から指定された部分列を削除した結果を列挙する。

$$
\begin{aligned}
ababa\odot ab&=\{aba,\,baa\},\\
ababa\odot bb&=\{aaa\},\\
abb\odot ab&=\{b\},\\
abb\odot bb&=\{a\}.
\end{aligned}
$$

したがって和集合を取れば

$$
\{ababa,abb\}\ominus\{ab,bb\}
=\{aba,\,baa,\,aaa,\,b,\,a\}
$$

である。
- $(ab)^n$ から部分列 $aa$ を削除するには，異なる2つのブロックの
$a$ を1つずつ選ぶ必要がある。削除されずに残る語は，削除前のブロック，
2つの削除位置の間のブロック，削除後のブロックの3部分に分けて

$$
(ab)^p\,b\,(ab)^q\,b\,(ab)^r
\qquad (p,q,r\ge 0)
$$

と書ける。逆にこの形の語は，$(ab)^{p+q+r+2}$ のうち
$(p+1)$ 番目と $(p+q+2)$ 番目の $a$ を削除して得られる。
よって正規表現は

$$
(ab)^*b(ab)^*b(ab)^*
$$

である。
- $A_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$,
$A_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ とする。
求める非決定性有限オートマトン $B$ を

$$
B=(Q_1\times Q_2,\Sigma,\Delta,(q_1,q_2),F_1\times F_2)
$$

で定める。状態 $(p,r)$ は「もとの語を読む $A_1$ の状態が $p$，
削除した部分列を読む $A_2$ の状態が $r$」である。
各 $c\in\Sigma$ について，遷移を次の2種類入れる。

$$
(p,r)\xrightarrow{c}(\delta_1(p,c),r),
\qquad
(p,r)\xrightarrow{\varepsilon}(\delta_1(p,c),\delta_2(r,c)).
$$

前者は入力として残す文字を読む遷移，後者は削除される文字を
$\varepsilon$ 遷移として処理する遷移である。入力語をすべて読んだ後，
$A_1$ が $L_1$ を受理し，かつ削除した文字列を読んだ $A_2$ が
$L_2$ を受理していれば受理する。
- 命題は真である。
$L_2$ を受理するプッシュダウンオートマトン $P_2$ を取り，
上の(3)と同じ考え方で，$L_1$ を受理する有限オートマトン $A_1$
と $P_2$ を積にしたプッシュダウンオートマトン $P$ を作る。
$P$ は，入力として出力語の文字を読むときは $A_1$ だけを進める。
一方，削除される文字を選ぶときは，入力を消費せずに $A_1$ をその文字で進め，
同時に $P_2$ にその文字を読ませる。
このようにすると，$P$ は

$$
v\in L_1\ominus L_2
$$

であること，すなわち，ある $u\in L_2$ を $v$ の中に挿入して
$L_1$ の語が得られることをちょうど非決定的に確認する。
プッシュダウンオートマトンで受理される言語は文脈自由言語であり，
同等な文脈自由文法へ変換できるので，$L_1\ominus L_2$ は文脈自由言語である。

### 最終答

$$
\{ababa,abb\}\ominus\{ab,bb\}=\{aba,baa,aaa,b,a\},
\qquad
(ab)^*\ominus\{aa\}=(ab)^*b(ab)^*b(ab)^*.
$$

$L_1,L_2$ が正規なら積オートマトンで $L_1\ominus L_2$ を受理できる。
また，$L_1$ が正規，$L_2$ が文脈自由なら $L_1\ominus L_2$ は文脈自由である。

## 第2問 — ページングとTLB

### 解説

**ページテーブルサイズの基本**

仮想ページ番号はページ内オフセットを除いた上位ビットで決まる。
そのため，総ページ数は $2^v/2^p=2^{v-p}$ である。
単一レベルページテーブルでは，全仮想ページにPTEを1つずつ持つため，
ページテーブルサイズは「総ページ数 $\times$ PTEサイズ」で決まる。

**FIFOの落とし穴**

FIFOは最も古く入ったページを追い出すだけで，最近使われたかどうかを見ない。
そのため，フレーム数を3から4に増やしてもフォールト数が12から13に増える。
これはアルゴリズムの性質によるもので，計算ミスではない。

**TLBとページフォールトの時間**

TLB missでページフォールトがない場合は，TLB参照，ページテーブル参照，
データ参照の3段階になる。ページフォールトがある場合は，
ページテーブル参照でフォールトを検出してから処理を行い，その後にアクセスを再開する。
「処理後はTLB参照から再開する」と明記されているので，再開後のTLB参照と
ページテーブル参照も時間に含める。

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

## 第3問 — パイプラインと論理回路

### 解説

**パイプライン時間の分解**

実行時間は「クロック周期 $\times$ サイクル数」である。
クロック周期はステージ遅延の最大値で決まる。サイクル数は理想的には
$N+4$ だが，ロード直後利用の回数だけ1サイクルずつ増える。
この問題ではストール理由がそれだけに限定されているため，分岐や構造ハザードを
追加で考える必要はない。

**ゲート数制限への対応**

デコーダでは3入力ANDをそのまま作るとゲート数が増える。
$e\bar{x}_1\bar{x}_0=\overline{\bar{e}\lor(x_1\lor x_0)}$ のように，
NANDでOR項を作り最後をNORで受ける形にすると，4出力を条件内で作れる。

**ロードユースハザード**

フォワーディングは「計算済みだがまだレジスタに書かれていない値」を早く渡す仕組みである。
しかしロード値はMAステージでメモリから戻るまで計算済みにならない。
この時刻の違いが，ロード命令だけ特別に1サイクル止まる理由である。

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

## 第4問 — 有限差分と対数時間探索

### 解説

**有限差分の係数**

$D^{(k)}$ は離散版の $k$ 階微分に対応する。
係数は二項係数で現れ，符号は

$$
(-1)^k,\ (-1)^{k-1},\ldots,1
$$

と交互になる。したがって5階差分では

$$
-1,\ 5,\ -10,\ 10,\ -5,\ 1
$$

が並び，$a_{i+3}$ の係数は $10$ である。

**最大値探索の見方**

列そのものを見るより，隣接差分

$$
a_{i+1}-a_i
$$

を見る方がよい。差分が正なら上り坂，負なら下り坂である。
2階差分が負という条件は，この傾きが単調に下がることを意味するので，
山は高々1つになり，二分探索が使える。

**一般の固定次数の場合**

$c$ が入力サイズに依存しないことが重要である。
山や谷の個数は $c$ によってのみ抑えられるため，候補点の数は定数個で済む。
もし $c$ が $n$ とともに増えるなら，同じ議論では $O(\log n)$ は保証できない。

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

---

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