| 授業科目名（和文） ［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. ビンパッキング問題 ?多様なものを「詰め込む」問題の 1つとしてビンパッキング問題を取り上げ，視点を変えることでより効果的な近似アルゴリズムが設計できることを知る． 9. 巡回セールスマン問題 ?巡回セールスマン問題の性質を紹介しその簡単なアルゴリズムを示す． 10. ネットワーク設計問題 ?効果的なネットワークを設計する問題の 1つであるシュタイナー木問題を紹介し近似アルゴリズムを示す． 11. 線形計画法の多項式時間アルゴリズムと半定値計画法 ?線形計画法を「効率的」に解くアルゴリズムを紹介し，近似アルゴリズムを設計するにあたりより複雑な半定値計画法が使えることを示す． 12. 充足最大化問題と半定値計画法 ?半定値計画法を用いて充足最大化問題に対する近似アルゴリズムが設計できることを示す． 13. 頂点彩色問題 ?グラフの頂点彩色問題は近似という観点からも難しい問題である．ここでは半定値計画法を応用した近似アルゴリズムを紹介する． 14. 最適化問題の変換 ?ある最適化問題を，「近似アルゴリズム」の観点から他の最適化問題に変換するときの考え方を示す． 15. まとめ ?講義の概要をまとめる． |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
出席状況?態度やレポートの内容などで評価を行う |
| 教科書 ［Textbook］ |
教科書：指定しない．毎回資料を配布する． |
| 自主学習ガイド及び キーワード ［Self learning］ |
本授業で取り上げるアルゴリズムは，数理計画法（線形計画法）や統計的手法（確率?期待値など）に基づいている．このうち，統計的な手法については分かっていることを前提とするので，各自で理解しておくこと． |
| 開講年度 ［Year of the course］ |
28 |