東大 コンピュータ科学 院試 過去問対策｜5年20問で見る形式言語・OS・アルゴリズム

東大コンピュータ科学の院試は、名前だけ見ると「プログラミングが得意なら戦える」と思いやすい試験です。しかし、2022〜2026年度の解答解説を作ってみると、問われているのは実装経験そのものではありません。形式言語の構成、OSの状態追跡、キャッシュとパイプラインの時間計算、グラフや近似アルゴリズムの証明を、紙の答案として短く書けるかが勝負です。

この記事では、東京大学大学院 情報理工学系研究科 コンピュータ科学専攻の2022〜2026年度、5年20問の解答解説をもとに、「どの年度から解くか」「最初の10分で何を見るか」「答案の最初に何を書くか」を整理します。

この記事の根拠

• 2022〜2026年度の5年分、各4問、合計20問の解答解説をもとにしています。
• 2026年5月25日時点で、公式のコンピュータ科学専攻入試案内には2027年度入試案内書、書籍リスト、2022〜2026年度相当の過去問題リンクが掲載されています。
• 研究科全体の過去問アーカイブでは、筆記試験問題は過去5年分公開と案内され、一般教育科目と各専攻の専門科目への入口が整理されています。

先に結論: 最初は2024年度、仕上げは2026年度

初回演習には2024年度が向いています。形式言語と状態数、キャッシュとIPC、連結性と全域木、評価戦略と再帰が並び、理論・システム・アルゴリズム・プログラミング言語の4領域を一度に確認できます。問題が派手すぎず、東大CSの答案に必要な「構成して、表にして、証明する」動きを見やすい年度です。

次に2025年度で、平方根言語、パイプラインとキャッシュ、スケジューリングとセマフォ、グラフ連結度へ広げます。最後に2026年度で、削除操作の形式言語、ページングとTLB、パイプラインと論理回路、有限差分と対数時間探索を確認してください。2022年度と2023年度は、古い年度というより、CPUスケジューリング、再帰的ソート、ページ置換、CPI計算を使って基礎の穴を見つける年度です。

5年20問の年度別テーマ

最初の10分で見る順序

東大CSは4問構成なので、全問を均等に読んでから悩むと時間を失います。最初の10分で、どの問題を完答候補にするか、どの問題を部分点狙いにするかを分けてください。

形式言語は「構成」か「反例」かを先に決める

2022〜2026年度を通して、形式言語・オートマトンは毎年の入口になっています。2026年度は削除操作、2025年度は平方根言語、2024年度はNFAとDFAの状態数差と非正規性、2023年度は半分接頭辞、2022年度は部分語位置の写像です。いずれも、定義を読んだあとに「構成で示すのか、閉包性で示すのか、反例で崩すのか」を決める必要があります。

答案の最初には、対象の言語操作を一文で書き直してください。正規言語ならDFAやNFAの状態遷移で追える情報は何か。文脈自由言語ならPDAのスタックに何を持たせるか。非正規性を示すなら、正規言語との共通部分や一文字アルファベットへの制限で単純化できるか。ここが見えれば、後半の証明はかなり短くなります。

失点しやすいのは、結論だけを「正規」「文脈自由」と書くことです。東大CSでは、オートマトンを構成したのか、閉包性を使ったのか、正規ではない理由をどの補題で示したのかまで必要です。特に文脈自由言語では、正規言語で使えた有限状態の変換がそのまま使えない場面があります。

OSとアーキテクチャは表を作る

システム系は、2026年度のページングとTLB、2025年度のパイプラインとキャッシュ、2024年度のキャッシュとIPC、2023年度のページ置換とCPI、2022年度のスケジューリングとパイプラインに現れます。どれも、公式を知っているだけでは点になりません。参照列、フレーム、ヒット/ミス、待ち時間、ストール、CPIの増分を表として追う必要があります。

ページ置換では、LRU、FIFO、最適置換の違いを過去と未来のどちらを見るかで説明します。TLBでは、TLBミスとページフォールトを同じものとして扱わない。キャッシュでは、容量ミス、競合ミス、ラインサイズ、ミスペナルティを分ける。パイプラインでは、ロードユースハザードだけが特別にストールを生むのか、分岐や構造ハザードも含めるのかを確認します。

典型ミスは、ページフォールト数だけを答えて表を残さないこと、CPI/IPCを逆数として扱う途中でペナルティの単位を落とすこと、スケジューリングで応答時間とターンアラウンド時間を混同することです。システム系は、答えよりも途中表が答案の価値になります。

アルゴリズムとグラフは不変量を書く

2025年度のグラフ連結度とサイクル、2024年度の連結性と全域木、2023年度の集合分割近似、2022年度の再帰的ソート、2026年度の対数時間探索は、どれも「アルゴリズム名を書けば終わり」ではありません。なぜ正しいか、どの量が単調に進むか、どの下界と比較しているかを答案に残す必要があります。

DFS/BFSなら、訪問済み集合と探索木を明示します。全域木なら、辺交換で木であり続ける理由を書く。近似アルゴリズムなら、平均下界と最大要素下界など、比較対象となる下界を先に置く。再帰式なら、再帰の枝数と部分問題サイズからオーダーを出します。対数時間探索なら、探索区間が毎回定数倍で縮む根拠を書きます。

証明問題で手が止まる受験生は、定理名を探しすぎています。まず小さな不変量を置いてください。「連結性が保たれる」「サイクルが作れる」「負荷の最大値は下界以上」「探索区間は半分になる」といった一文があるだけで、答案の方向が決まります。

参考書に戻る章

コンピュータ科学専攻は範囲が広いので、参考書を最初から読む計画は破綻しやすいです。過去問で止まった箇所から章単位で戻る方が現実的です。

4週間の演習順序

1. 1週目は2024年度を解きます。形式言語、キャッシュ、グラフ、評価戦略を1年で見て、どの分野で答案の初手が出ないかを診断します。
2. 2週目は2025年度を解きます。平方根言語、CPI分解、SRTFとセマフォ、連結度とサイクルを使い、理論とシステムの両方で証明の骨格を作ります。
3. 3週目は2026年度を解きます。最新年度として、削除操作、TLB、パイプライン、有限差分と探索を確認し、表と証明の精度を上げます。
4. 4週目は2022年度と2023年度を解きます。スケジューリング、再帰的ソート、ページ置換、CPI、近似アルゴリズムで基礎を固めます。

自己採点チェック

• 形式言語で、DFA/NFA/PDAのどれを構成するか、またはどの閉包性を使うかを最初に書いたか。
• 非正規性や文脈自由でないことを、反例や制限言語を使って説明したか。
• ページ置換、TLB、スケジューリングで、表や時系列を答案に残したか。
• CPI/IPCやキャッシュで、ミスペナルティ、ヒット率、命令数、サイクル数の単位を揃えたか。
• パイプラインで、どの依存関係がストールを生むかを命令列上で示したか。
• グラフや近似アルゴリズムで、不変量、下界、交換 argument、計算量を書いたか。
• 最終答が合っていても、採点者が途中状態を追える答案になっているか。

今は深追いしないもの

コンピュータ科学専攻を目指すと、最新の機械学習論文、競技プログラミングの難問、分散システムの細かい実装、CPU設計の深い最適化まで手を広げたくなります。しかし直近5年の専門科目を見る限り、まず必要なのは、形式言語の構成、OSとアーキテクチャの表、アルゴリズムの不変量です。最新技術の広い読書は、これらの答案の型を作ってからで十分です。

特に短期対策では、実装だけに寄せすぎないでください。東大CSの答案では、プログラムを書けることより、なぜそのアルゴリズムが正しいか、なぜそのページが追い出されるか、なぜその言語クラスで閉じるかを説明する力が点になります。

公式情報で確認する入口

出願年度の試験形式、TOEFL、口述試験、志望研究室への連絡、専門科目の公開範囲は必ず公式情報で確認してください。この記事では、東京大学大学院 情報理工学系研究科のコンピュータ科学専攻 入試案内と、研究科全体の過去問アーカイブを参照しています。2026年5月25日時点で、コンピュータ科学専攻の入試案内には2022〜2026年度相当の専門科目リンクが掲載されています。

同じ研究科の他専攻と募集時期

2027年度修士の募集専攻・日程で、過去問のある専攻と現在募集している専攻を分けて確認できます。

情報理工学系研究科には、コンピュータ科学・数理情報学・システム情報学・電子情報学・知能機械情報学・創造情報学の6専攻があります。2027年度の修士冬入試はシステム情報学・創造情報学のみで、コンピュータ科学は含まれません。

• 東大 システム情報学 院試 過去問対策
• 東大 数理情報学 院試 過去問対策
• 東大 電子情報学 院試 過去問対策