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

第1問 形式言語とオートマトン
削除操作の見方
は連続部分文字列の削除ではなく,部分列の削除である。 したがって では,1文字目の と4文字目の を 削除する場合も考える必要がある。この点を落とすと(1)の列挙で漏れが出る。
正規表現の作り方
では は各ブロックの先頭に1つずつ現れる。 2つの を消すと,それぞれのブロックは だけになる。 その前,間,後ろには通常の ブロックが任意個残るため, という形が自然に出る。
オートマトン構成の核心
残す文字は入力として読む。削除する文字は入力には現れないので 遷移で処理する。この2種類の遷移を同じ 上で動かすことで, 「残した語」と「削除した語」を合わせたものが に属するかを確認できる。 文脈自由の場合も同じ発想で,削除列を有限オートマトンではなく プッシュダウンオートマトンに読ませればよい。
解答
- まず,各語から指定された部分列を削除した結果を列挙する。 したがって和集合を取れば である。
- から部分列 を削除するには,異なる2つのブロックの を1つずつ選ぶ必要がある。削除されずに残る語は,削除前のブロック, 2つの削除位置の間のブロック,削除後のブロックの3部分に分けて と書ける。逆にこの形の語は, のうち 番目と 番目の を削除して得られる。 よって正規表現は である。
- , とする。 求める非決定性有限オートマトン を で定める。状態 は「もとの語を読む の状態が , 削除した部分列を読む の状態が 」である。 各 について,遷移を次の2種類入れる。 前者は入力として残す文字を読む遷移,後者は削除される文字を 遷移として処理する遷移である。入力語をすべて読んだ後, が を受理し,かつ削除した文字列を読んだ が を受理していれば受理する。
- 命題は真である。 を受理するプッシュダウンオートマトン を取り, 上の(3)と同じ考え方で, を受理する有限オートマトン と を積にしたプッシュダウンオートマトン を作る。 は,入力として出力語の文字を読むときは だけを進める。 一方,削除される文字を選ぶときは,入力を消費せずに をその文字で進め, 同時に にその文字を読ませる。 このようにすると, は であること,すなわち,ある を の中に挿入して の語が得られることをちょうど非決定的に確認する。 プッシュダウンオートマトンで受理される言語は文脈自由言語であり, 同等な文脈自由文法へ変換できるので, は文脈自由言語である。
最終答
が正規なら積オートマトンで を受理できる。 また, が正規, が文脈自由なら は文脈自由である。
第2問 ページングとTLB
ページテーブルサイズの基本
仮想ページ番号はページ内オフセットを除いた上位ビットで決まる。 そのため,総ページ数は である。 単一レベルページテーブルでは,全仮想ページにPTEを1つずつ持つため, ページテーブルサイズは「総ページ数 PTEサイズ」で決まる。
FIFOの落とし穴
FIFOは最も古く入ったページを追い出すだけで,最近使われたかどうかを見ない。 そのため,フレーム数を3から4に増やしてもフォールト数が12から13に増える。 これはアルゴリズムの性質によるもので,計算ミスではない。
TLBとページフォールトの時間
TLB missでページフォールトがない場合は,TLB参照,ページテーブル参照, データ参照の3段階になる。ページフォールトがある場合は, ページテーブル参照でフォールトを検出してから処理を行い,その後にアクセスを再開する。 「処理後はTLB参照から再開する」と明記されているので,再開後のTLB参照と ページテーブル参照も時間に含める。
第3問 パイプラインと論理回路
パイプライン時間の分解
実行時間は「クロック周期 サイクル数」である。 クロック周期はステージ遅延の最大値で決まる。サイクル数は理想的には だが,ロード直後利用の回数だけ1サイクルずつ増える。 この問題ではストール理由がそれだけに限定されているため,分岐や構造ハザードを 追加で考える必要はない。
ゲート数制限への対応
デコーダでは3入力ANDをそのまま作るとゲート数が増える。 のように, NANDでOR項を作り最後をNORで受ける形にすると,4出力を条件内で作れる。
ロードユースハザード
フォワーディングは「計算済みだがまだレジスタに書かれていない値」を早く渡す仕組みである。 しかしロード値はMAステージでメモリから戻るまで計算済みにならない。 この時刻の違いが,ロード命令だけ特別に1サイクル止まる理由である。
第4問 有限差分と対数時間探索
有限差分の係数
は離散版の 階微分に対応する。 係数は二項係数で現れ,符号は と交互になる。したがって5階差分では が並び, の係数は である。
最大値探索の見方
列そのものを見るより,隣接差分 を見る方がよい。差分が正なら上り坂,負なら下り坂である。 2階差分が負という条件は,この傾きが単調に下がることを意味するので, 山は高々1つになり,二分探索が使える。
一般の固定次数の場合
が入力サイズに依存しないことが重要である。 山や谷の個数は によってのみ抑えられるため,候補点の数は定数個で済む。 もし が とともに増えるなら,同じ議論では は保証できない。
年度別の解答例
2026年度の出題内容
同じテーマを出した他大学・他年度
前年度(2025年度)との違い
東京大学の他の解答PDF
院試対策ガイド
東京大学の公式過去問
- 公開年度範囲
- 2022〜2026
- 公式の解答例
- 解答例の掲載なし