院試 アルゴリズムの出題傾向と対策

院試 アルゴリズム は、情報系研究科を志望する受験生にとって、専門試験の核となる分野です。学部のアルゴリズムとデータ構造の標準範囲が中心ですが、計算量解析（オーダー記法）を厳密に書ける状態と、ソート・探索・グラフアルゴリズム・動的計画法を擬似コードレベルで答案に書ける状態が求められます。情報系の院試は配点が大きく、ここでの取りこぼしは合否に直結します。本記事ではアルゴリズムを主要試験科目とする研究科の傾向と頻出パターン、答案で失点しやすい論点、推奨教科書を整理します。

この分野が出題される大学・研究科

情報系では、東京大学 情報理工学系研究科 電子情報学、九州大学 システム情報科学府 情報科学（数学系）、東京科学大学 工学院 情報通信系などで、アルゴリズムとデータ構造の問題が必答もしくは選択問題として毎年出題されます。電気通信大学 情報理工学研究科 機械知能システムや東北大学 工学研究科 電気・情報工学 基礎・専門でも、計算機関連科目の一部として出題範囲に含まれます。出題形式は研究科で異なり、東大は擬似コードと計算量の論証、九大は具体的なグラフ問題の手順記述、東京科学大は離散数学と組み合わせた論証問題が中心という傾向が見られます。志望研究科の出題スタイルを確認してから演習対象を絞るのが効率的です。

頻出の出題パターン

アルゴリズムの試験で頻出のサブトピックは以下です。擬似コードを書く形式と、計算量を式で論証する形式の双方に慣れておく必要があります。

• 計算量：オーダー記法（O・Ω・Θ）、最悪計算量・平均計算量、漸化式の解法（マスター定理）
• ソート：クイックソート、マージソート、ヒープソート、基数ソート、計算量と安定性
• 探索：二分探索、ハッシュ法、二分探索木、AVL木、赤黒木、B木
• データ構造：スタック・キュー・ヒープ・優先度付きキュー、Union-Find
• グラフアルゴリズム：DFS/BFS、ダイクストラ法、ベルマン・フォード法、ワーシャル・フロイド法、最小全域木（クラスカル・プリム）、最大流（フォード・ファルカーソン）
• 動的計画法：ナップサック問題、編集距離、最長共通部分列、ビタビアルゴリズム
• 計算可能性・計算量クラス：チューリング機械、NP完全性、SATの帰着（情報系上位校で出題）
• 近似アルゴリズム・乱択アルゴリズム（東大・東京科学大などで頻出）

答案で失点しやすいポイント

アルゴリズムの答案で最も多い失点は、計算量の論証を「O(n log n) です」とだけ書いて終わらせることです。漸化式 T(n) = 2T(n/2) + O(n) を経由してマスター定理で結論を出すか、ループの回数とループ内処理の計算量を分解して積で示すか、どちらかの形で論証を残さないと部分点を取り切れません。グラフアルゴリズムでは、隣接リスト表現・隣接行列表現のどちらを採用したかを明示しないと、ダイクストラ法のヒープを使った O((V+E) log V) なのかフィボナッチヒープでの O(E + V log V) なのかが判別できません。動的計画法では遷移式 dp[i][j] = ... の意味を1行の自然言語で添えないと、採点者は配列の意味を逆算しなければならず効率が悪くなります。NP完全性の問題では帰着の方向（既知のNP困難問題からの帰着）を取り違えると証明全体が成立しません。

推奨教科書・参考書

• Cormen-Leiserson-Rivest-Stein『アルゴリズムイントロダクション』（近代科学社）：事実上の標準教科書
• 石畑清『アルゴリズムとデータ構造』（岩波書店）
• セジウィック『アルゴリズムC』
• 渋谷哲朗・北野俊行『アルゴリズム理論』
• Garey-Johnson『Computers and Intractability』：NP完全性の標準
• 『プログラミングコンテストチャレンジブック』：演習量の補強用

院試hub の解答パックでカバーされる範囲

院試hub ではアルゴリズムが試験範囲に含まれる情報系研究科について、年度別の解答パックを揃えています。九大 システム情報科学府 情報科学（数学系）、東大 情報理工学系研究科 電子情報学、東京科学大 工学院 情報通信系 などを横断的に確認することで、擬似コード型と論証型の出題スタイルの違いが整理できます。公式PDFを自力で解いた後に答案を突き合わせ、計算量の論証部分を解答パックで確認するという順番で使ってください。

公開前に必ず最新の公式募集要項・公式過去問ページで試験科目・出題範囲を確認してください。