科目ナンバー

SG-IG5-7C40

履修条件・関連科目等

授業で使用する言語

日本語／英語

授業で使用する言語（その他の言語）

授業の概要

本講義では，アルゴリズムの設計と解析の基礎を体系的に学ぶ．漸近解析などの解析基盤を踏まえ，貪欲法・分割統治法・動的計画法・ネットワークフローといった代表的設計手法を、典型問題を通して修得する．さらにNPと計算困難性の概念を導入し，近似アルゴリズムの基本手法と性能保証の考え方を学ぶ．

科目目的

本講義の目的は，主要なアルゴリズム設計パラダイムを理解し，問題に応じて適切な方針を選択して解法を構成できる能力を養うことである．設計したアルゴリズムの正当性を説明（証明）し，計算量と近似性能を評価できることを目指す．

到達目標

- 計算量解析の基本技法を用いて，アルゴリズムの性能を評価できる．
- 貪欲法・分割統治法・動的計画法・フローに基づく解法を設計し，正当性を論じられる．
- NP完全性等の計算困難性を踏まえ，近似アルゴリズムの性能保証を説明できる．

授業計画と内容

1. ガイダンス
2. アルゴリズム解析の基礎
3. 貪欲法（グラフの探索, 最小全域木）
4. 貪欲法（スケジューリング、マトロイド構造）
5. 分割統治法（漸化式による計算量、マージソート、行列積）
6. 分割統治法（カラツバ法、FFTによる乗算）
7. 動的計画法（重み付き区間スケジューリング、部分和問題、ナップサック問題）
8. 動的計画法（最短経路問題、巡回セールスマン問題）
9. ネットワークフロー（最大流問題、最小カット問題）
10. ネットワークフロー（二部グラフのマッチング）
11. NPと計算困難性
12. 近似アルゴリズム（近似比の定義、ロードバランス問題、頂点被覆問題、巡回セールスマン問題）
13. 近似アルゴリズム（集合被覆問題、劣モジュラ最大化、ナップサック問題）
14. まとめ

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

References
- Jon Kleinberg and Éva Tardos: “Algorithm Design”
- Bernhard Korte and Jens Vygen: “Combinatorial Optimization: Theory and Algorithms”
- Michael R. Garey and David S. Johnson: “Computers and Intractability: A Guide to the Theory of NP-Completeness”
- Vijay V. Vazirani: “Approximation Algorithms”

その他特記事項

参考URL