計算量理論が出た院試 過去問
情報の頻出テーマ
定義・定理・計算例から確かめるには:アルゴリズムとデータ構造・計算量と漸化式、計算理論・計算可能性と NP 完全性
計算量理論を出した大学 × 年度
| 大学 | 2027 | 2026 | 2025 | 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2016 | 2010 | 合計 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 東京大学 | – | 3 | 3 | 2・3 | 3・4 | – | 3 | – | 3 | 2 | 2・8 | 12 |
| 京都大学 | – | – | 8 | 5 | 2 | 3・6 | 6・9 | – | – | – | – | 7 |
| 大阪大学 | – | 1 | 1 | 1 | – | 1 | – | 1 | – | – | – | 7 |
| 京都工芸繊維大学大学院 | – | 3 | 3 | 2 | – | – | – | – | – | – | – | 3 |
| 名古屋大学大学院 | – | 6 | – | 17 | – | 7 | – | – | – | – | – | 3 |
| 九州工業大学大学院 | – | 1・2 | – | – | – | – | – | – | – | – | – | 2 |
| 静岡大学大学院 | – | – | – | 2 | – | – | – | – | – | – | – | 1 |
| 東京科学大学 | – | – | – | – | – | – | – | 3 | – | – | – | 1 |
| 東京都立大学大学院 | – | 4 | – | – | – | – | – | – | – | – | – | 1 |
| 名古屋工業大学 | 1 | – | – | – | – | – | – | – | – | – | – | 1 |
セルの数字はその年度の大問番号(同じ年度に複数の科目で出た場合は番号の重複を除く)。列は出題のあった11年度だけ。
計算量理論の出題例と解説の小見出し
- 九州工業大学大学院 共通科目(情報基礎) 2026年度 第1問 — プログラミング
挿入位置の決め方 / 採点上の注意
- 京都工芸繊維大学大学院 専門科目(情報工学) 2026年度 第3問 — プログラミング(2)
- 名古屋大学大学院 数理情報学 2026年度 第6問 — 離散最適化
- 東京大学 創造情報学 専門科目 2026年度 第3問 — 情報システム用語の説明
採点されやすい説明の形 / 選ぶ項目
- 東京都立大学大学院 情報科学域 専門科目 2026年度 第4問 — データ構造とアルゴリズム
最後の一手で分類する / a_0=1 の意味
- 京都大学 通信情報システムコース 2025年度 第8問 — B-4 データ構造と探索
ヒープ配列表現 / 再帰関数の端点
- 京都工芸繊維大学大学院 専門科目(情報工学) 2025年度 第3問 — プログラミング(2)
- 大阪大学 専門科目(情報数理学) 2025年度 第1問 — 情報基礎
中央値の中央値法の要点 / 答案で落としやすい点
- 東京大学 創造情報学 専門科目 2025年度 第3問 — 情報システム用語の説明
採点上の注意
- 京都大学 社会情報学コース 2024年度 第5問 — 情報学基礎:計算量
内側ループを数式化する / 計算量の改善
- 京都工芸繊維大学大学院 専門科目(情報工学) 2024年度 第2問 — プログラミング(1)
- 名古屋大学大学院 複雑系科学 2024年度 第17問 — 情3:二分探索木の構築・走査順と計算量
特定カードの位置は一様である / 二分探索木は挿入順で形が変わる
- 大阪大学 専門科目(情報工学) 2024年度 第1問 — アルゴリズムとプログラミング(挿入ソート)
挿入ソートで見るべき場所 / 二分探索の終了位置
- 大阪大学 専門科目(情報数理学) 2024年度 第1問 — 情報基礎
このアルゴリズムが求めている量 / 計算量の見方
- 東京大学 創造情報学 専門科目 2024年度 第2問 — ハミング距離検索と専用回路
半径1検索の考え方 / 回路の注意
- 東京大学 専門科目 2024年度 第3問 — 最大部分列和
固定長はスライディングウィンドウ / 長さ制約なしはKadane法
- 東京大学 専門科目(コンピュータ科学) 2024年度 第3問 — 連結性と全域木
全域木の基本 / 辺交換の考え方
- 静岡大学大学院 情報科学 2024年度 第2問 — ソフトウェア系
採点観点
- 京都大学 社会情報学コース 2023年度 第2問 — 情報学基礎:最小値・最大値探索
最小値比較が省略される理由 / 再帰版の比較回数
- 東京大学 専門科目 2023年度 第3問 — 最大フローと二部マッチング
逆辺の意味 / 最大フローの証明は切断で締める
- 東京大学 専門科目 2023年度 第4問 — 経路制御
距離ベクトルとリンク状態の違い / BGPは距離の短さだけではない
- 京都大学 通信情報システムコース 2022年度 第6問 — A-6 アルゴリズム
ハッシュ表の評価 / 連結リストでの挿入ソート
- 京都大学 社会情報学コース 2022年度 第3問 — 情報学基礎 F-3:探索と整列
最大回数の式 / 再帰と効率
- 名古屋大学大学院 数理情報学 2022年度 第7問 — 第1科目・アルゴリズム設計法
擬多項式時間 / 数えるDP
計算量理論を解答まで読める問題
解説に加えて解答も無料で公開している9問です。院試の対策のほか、学部の授業や期末試験で計算量理論の計算を練習する例題としても使えます。問題文は各大学の公式過去問で確認してください。
- 東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2010年度 第2問 — 漸化式と高速計算
計算量の見分け方 / 周期性の証明で必要な点
- 東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2010年度 第8問 — C 言語とリスト操作
sort の採点観点 / reverse の不変条件
- 東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2016年度 第2問 — 動的計画法
貪欲法ではない
- 大阪大学 専門科目(情報数理学) 2022年度 第1問 — 情報基礎
中央の配列で分解する / なぜ二分探索で十分か
- 大阪大学 専門科目(情報工学) 2022年度 第1問 — アルゴリズムとプログラミング
基準値の位置に注目する / 交換回数の数え方
- 京都大学 社会情報学コース 2023年度 第2問 — 情報学基礎:最小値・最大値探索
最小値比較が省略される理由 / 再帰版の比較回数
- 大阪大学 専門科目(情報工学) 2024年度 第1問 — アルゴリズムとプログラミング(挿入ソート)
挿入ソートで見るべき場所 / 二分探索の終了位置
- 大阪大学 専門科目(情報数理学) 2024年度 第1問 — 情報基礎
このアルゴリズムが求めている量 / 計算量の見方
- 東京大学 創造情報学 専門科目 2025年度 第3問 — 情報システム用語の説明
採点上の注意
計算量理論が出る試験科目
| 大学・研究科 | 試験科目名 | 出題数 | 出題年度 |
|---|---|---|---|
| 東京大学情報理工学系研究科 システム情報学専攻 | 専門科目 | 4 | 2021〜2024(3年度) |
| 大阪大学情報科学研究科 情報基礎数学専攻 | 専門科目(情報数理学) | 4 | 2022〜2026(4年度) |
| 東京大学情報理工学系研究科 システム情報学専攻 | 創造情報学 専門科目 | 3 | 2024〜2026(3年度) |
| 大阪大学情報科学研究科 情報基礎数学専攻 | 専門科目(情報工学) | 3 | 2020〜2024(3年度) |
| 京都工芸繊維大学大学院工芸科学研究科 情報工学専攻 | 専門科目(情報工学) | 3 | 2024〜2026(3年度) |
| 京都大学情報学研究科 | 通信情報システムコース | 3 | 2021〜2025(3年度) |
| 京都大学情報学研究科 | 社会情報学コース | 3 | 2022〜2024(3年度) |
| 東京大学学際情報学府 | 学際情報学専攻 先端表現情報学コース 専門科目 | 3 | 2010〜2016(2年度) |
| 名古屋大学大学院情報学研究科 | 数理情報学 | 2 | 2022〜2026(2年度) |
| 九州工業大学大学院情報工学府 | 共通科目(情報基礎) | 1 | 2026 |
| 九州工業大学大学院情報工学府 | 専門科目(知能情報工学) | 1 | 2026 |
| 静岡大学大学院総合科学技術研究科 情報学専攻 | 情報科学 | 1 | 2024 |
| 東京大学情報理工学系研究科 システム情報学専攻 | 専門科目(コンピュータ科学) | 1 | 2024 |
| 東京大学情報理工学系研究科 システム情報学専攻 | 知能機械情報学 | 1 | 2019 |
| 東京科学大学情報理工学院 数理・計算科学系 | 専門科目(情報工学) | 1 | 2020 |
| 京都大学情報学研究科 | システム科学コース | 1 | 2021 |
| 東京都立大学大学院システムデザイン研究科 情報科学域 | 情報科学域 専門科目 | 1 | 2026 |
| 名古屋工業大学工学研究科 電気・機械工学系 機械工学プログラム | 情報工学系 | 1 | 2027 |
| 名古屋大学大学院情報学研究科 | 複雑系科学 | 1 | 2024 |