| 授業科目名（和文） ［Course］ |
近似アルゴリズム論 |
| 授業科目名（英文） ［Course］ |
Approximation Algorithms |
| 学部（研究科） ［Faculty］ |
情報系工学研究科 |
| 学科（専攻） ［Department］ |
システム工学専攻前期 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○小野 孝男 自室番号（2608）、電子メール（onotakao**c.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
2単位 |
| 対象学生 ［Eligible students］ |
1?2年次生 |
| 授業概略と目標 ［Course description and Objects］ |
日常的に表れる問題はしばしば離散最適化問題として定式化できるが，現実的な時間でその最適解を求めることは困難であることが多い．そこで，理論的な，あるいは現実的な立場から「適度な時間でなるべくよい解を見つける」手法が研究されている． 本講義では，理論的な立場からこれらの離散最適化問題を概観し近似アルゴリズムを設計するいくつかの手法について学ぶ． |
| 到達目標 ［Learning Goal］ |
1. 線形計画法と双対理論について理解する 2. 最適化問題と近似アルゴリズムの理論的な扱いを知る 3. いくつかの離散最適化問題に対する近似アルゴリズムを学ぶ |
| 履修上の注意 ［Notes］ |
履修の要件：数理計画法やアルゴリズムについて理解していることが望ましい． |
| 授業計画とスケジュール ［Course schedule］ |
1. 最適化問題とは 2. 線形計画法と双対定理 3. 整数線形計画法 4. 集合被覆問題 5. ナップサック問題 6. 充足最大化問題 7. 最大独立集合問題 8. 最適化問題の分類 9. ビンパッキング問題 10. 巡回セールスマン問題 11. ネットワーク設計問題 12. 楕円体法：線形計画法の多項式時間アルゴリズム 13. 半定値計画法と凸計画法 14. 半定値計画法の応用 15. 頂点彩色問題 |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
出席状況?態度やレポートの内容などで評価を行う |
| 教科書 ［Textbook］ |
教科書：適宜資料を配布する． |
| 自主学習ガイド及び キーワード ［Self learning］ |
本授業で取り上げるアルゴリズムは，数理計画法（線形計画法）や統計的手法（確率?期待値など）に基づいている．このうち，統計的な手法については分かっていることを前提とするので，各自で理解しておくこと． |
| 開講年度 ［Year of the course］ |
26 |