東大 情報理工学系研究科 コンピュータ科学専攻 専門科目(コンピュータ科学) 2025年度 院試 過去問 解答例・解説
- 大学
- 東京大学
- 研究科・専攻
- 情報理工学系研究科 コンピュータ科学専攻
- 科目
- 専門科目(コンピュータ科学)
- 年度
- 2025年度
解説は全問、途中式と最終答は大問1問を無料で公開しています。PDFの収録範囲は商品ページで確認できます。問題本文は含みません。

第1問 形式言語とオートマトン
平方根言語の見方
は「同じ語を2回続けたものが に入るか」を見る操作である。 したがって,単に正規表現を半分に切るのではなく, の前半と後半に同じ構造が 現れることを使う。(1)では2個の の位置が強い制約になっている。
正規言語で閉じる理由
正規言語では,語そのものを覚える必要はない。語 がDFAの状態集合上に作る 有限個の状態変換だけを覚えればよい。有限集合 に対する写像は高々 個なので,これを状態にしたDFAが作れる。
文脈自由言語で同じ議論が使えない理由
プッシュダウンオートマトンでは, を1回読んだあとに同じ をもう一度 同じ順序で読むことを有限制御だけでは表せない。スタックに を積むと取り出しは 逆順になるため,正規言語のように「変換だけを持つ」という処理ができない。 このため,文脈自由言語では反例が存在する。
解答
- 語 が に属する条件は, が の形に入ることである。この正規表現に現れる は2個であり,2個目は末尾の である。したがって の前半 も1個の を含み,その は の末尾でなければならない。 と書くと, である。これが上の正規表現に入るためには,最初の は に属し,2つ目の は に属する必要がある。 よって であり, となる。
- 各語が与える状態変換だけを見る。状態を とし,文字1つが誘導する 写像を考えると である。語 が誘導する写像を と書くと, である。 到達し得る写像は次の4種類である。 このうち を満たすのは だけである。 ただし, と はこの判定に関して同値であり,最小化すると3状態で足りる。 最小DFAを とする。ここで は を併合した状態,, である。 遷移は で与えられる。
- 命題は真である。正規言語 を受理するDFAを とする。語 が 上で誘導する状態変換を とおく。すると である。 そこで,状態集合を有限集合 とするDFAを作る。初期状態は恒等写像 とし,文字 を読んだとき と更新する。受理状態は である。このDFAはちょうど を受理するので, は正規言語である。
- 命題は偽である。反例として を考える。この言語は を順に生成すればよいので文脈自由である。 一方, なら である。 が上の形に入るためには, は の形でなければならない。実際, であり,これは として に属する。逆も同様に従う。 したがって である。これは標準的な非文脈自由言語である。よって,文脈自由言語全体は に関して閉じていない。
最終答
の最小DFAは3状態で,遷移表は本文の通り。 正規言語についての命題は真,文脈自由言語についての命題は偽である。
第2問 パイプラインとキャッシュ
CPIの分解
この問題では,総サイクル数を に分けると見通しがよい。パイプラインの立ち上がり・終了コストは問題文で無視してよい 扱いなので,基本サイクルは命令数そのものとして数える。
ラインサイズの決まり方
配列を4バイト刻みで順に読む場合,キャッシュラインサイズが バイトなら, 1本のラインに 個のアクセスが入る。初期状態が空なので,各ラインの最初の ロードだけがミスになる。ここでは合計1024バイトを走査してミスが32回なので, 1ラインは バイトである。
命令フォーマットの比較
レジスタ番号の位置をそろえる設計は,レジスタファイルの読み出しポートに渡す信号を 単純にできる。一方で,即値を分割すると,命令種別に応じた連結・並べ替え・符号拡張の 回路が必要になる。実際の命令セットでも,この2つはしばしばトレードオフになる。
第3問 スケジューリングとセマフォ
待ち時間の数え方
待ち時間には実行可能キューで待つ時間だけでなく,セマフォの待ちキューで待つ時間も 含まれる。全プロセスが終了する場合は でまとめて計算できるので,途中でどのキューにいたかを細かく足し上げるより安全である。
SRTFとセマフォの相互作用
セマフォがないSRTFでは,時刻20に到着した短い が を中断する。 しかし(3)では は を取得できないため待ちに入り, がそのまま 終了まで進む。このように,優先度が高いプロセスでも資源を取れなければ実行できない。
デッドロックの確認
(4)のRRでは, と が逆順に を要求する。 片方が を持って を待ち,もう片方が を持って を待つと, どちらも進めない。時刻80でこの循環待ちが完成する。
第4問 グラフの連結度とサイクル
サイクルと2本のパス
2点 を含むサイクルは,サイクル上で から へ進む2通りの向きの パスに分解できる。この2本は端点以外の頂点を共有しない。逆に,内点素な2本の - パスを合わせればサイクルになる。この対応が(1)の中心である。
新しい頂点を足す補題
(2)は,あとで「指定された点集合」を「新しい1点の近傍」として扱うための準備である。 を消さない場合でも, には 点あり,削除できるのは高々 点なので, とつながる頂点が必ず1つ残る。この数え上げが証明の要点である。
一般化の構造
高連結性は,ある頂点から既存のサイクルへ多数の互いに独立な接続路を保証する。 接続点が指定点の数より1つ多くあるため,指定点を含まない弧を避けてサイクルを 作り直せる。これが「 連結なら任意の 点が同一サイクルに乗る」理由である。
年度別の解答例
2025年度の出題内容
同じテーマを出した他大学・他年度
| テーマ | この年度 | 全体の出題実績 | 他大学の直近出題 |
|---|---|---|---|
| 正規表現・形式言語 | 第1問 | 10大学・33問 |
前年度(2024年度)との違い
- 大問数
- 2024年度 4問 → 2025年度 4問
- 2025年度で新しく出たテーマ
- 正規表現・形式言語
東京大学の他の解答PDF
院試対策ガイド
東京大学の公式過去問
- 公開年度範囲
- 2022〜2026
- 公式の解答例
- 解答例の掲載なし