シラバス参照
|
シラバス参照
|
| 科目一覧へ戻る | 2019/08/20 現在 |
| 科目名（和文） ／Course |
近似アルゴリズム論 |
|---|---|
| 科目名（英文） ／Course |
Approximation Algorithms |
| 時間割コード ／Registration Code |
61111201 |
| 学部（研究科） ／Faculty |
情報系工学研究科 博士前期課程 |
| 学科（専攻） ／Department |
システム工学専攻 |
| 担当教員（○：代表教員）
／Principle Instructor （○） and Instructors |
○小野 孝男 |
| オフィスアワー ／Office Hour |
小野 孝男(火曜日 ５限) |
| 開講年度 ／Year of the Course |
2017年度 |
| 開講期間 ／Term |
前期 |
| 対象学生 ／Eligible Students |
1年,2年 |
| 単位数 ／Credits |
2.0 |
| 更新日 ／Date of renewal |
2017/03/30 |
|---|---|
| 使用言語 ／Language of Instruction |
日本語 |
| オムニバス ／Omnibus |
該当なし |
| 授業概略と目的 ／Cource Description and Objectives |
日常的に表れる問題の多くは離散最適化問題として定式化することができる.しかし, それらの問題のほとんどは現実的な時間で最適解を求めることが困難であり, 理論的・実用的な観点から「適度な時間でなるべく良い解を見つける」手法が検討されている. 本講義では理論的な立場から離散最適化問題について概観し, 近似アルゴリズムを設計するためのいくつかの方針について学ぶ. また, 実際に得られた近似アルゴリズムに対してその性能を理論的に評価する手法についても理解することを目的とする. |
| 履修に必要な知識・能力・キーワード ／Prerequisites and Keywords |
数理計画法, 特に線形計画法と双対定理は頻発するので, 講義中説明はするもののあらかじめ簡単に理解しておくことが望ましい. また, アルゴリズムの記述方法と解析についても確認しておいてほしい. キーワード: 離散最適化問題, 近似アルゴリズム, 数理計画法 |
| 履修上の注意 ／Notes |
講義の最後には次回の内容について簡単に紹介するので, 各自で調べておくと内容を理解しやすいだろう. |
| 教科書 ／Textbook(s) |
なし. 毎回資料を配布する. |
| 参考文献等 ／References |
|
| 自主学習ガイド ／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework |
講義ではいろいろなアルゴリズムを紹介するが, 説明を聞くだけでは表面的な理解になりがちである. 簡単でもいいから具体的に問題を設定しアルゴリズムを実行することによって, アルゴリズムや解析の背景をよりよく理解することができるだろう. |
| 資格等に関する事項 ／Attention Relating to Professional License |
|
| 備考 ／Notes |
| No. | 単元（授業回数） ／Unit (Lesson Number) |
単元タイトルと概要 ／Unit Title and Unit Description |
時間外学習 ／Preparation and Review |
配布資料 ／Handouts |
|---|---|---|---|---|
| 1 | 1 | [最適化問題と近似アルゴリズム] 本講義で対象とする離散最適化問題と, 近似アルゴリズムの評価で用いる「近似率」について紹介する. |
||
| 2 | 2 | [線形計画法と双対定理] 近似アルゴリズムの設計・解析でしばしば用いられる線形計画法と双対定理について理解する. |
||
| 3 | 3 | [集合被覆問題] 多くの問題がのモデルとして重要な集合被覆問題に対し近似アルゴリズムを紹介し基本的な解析手法を学ぶ. |
||
| 4 | 4 | [ナップサック問題] ナップサック問題とその近似アルゴリズムを理解し, 「近似」という観点で最も簡単な問題であることを学ぶ. |
||
| 5 | 5 | [充足最大化問題] 充足最大化問題を例として確率的な近似アルゴリズムを紹介する. また, そのようなアルゴリズムから乱数を取り除く手法についても説明する. |
||
| 6 | 6 | [最大独立集合問題] 無向グラフに対する最適化問題として最大独立問題を紹介する. |
||
| 7 | 7 | [最適化問題の分類] 最適化問題が「最適解を求める」ための計算量とは別に「得られる近似解の精度」によっても分類できることを理解する. |
||
| 8 | 8 | [ビンパッキング問題] 多様なものを「詰め込む」基本的な問題としてビンパッキング問題を紹介し, 簡単な前処理を行うことで近似性能が変化する場合があることを知る. |
||
| 9 | 9 | [巡回セールスマン問題] 現実的な問題である巡回セールスマン問題の性質を理解し簡単な近似アルゴリズムを知る. |
||
| 10 | 10 | [ネットワーク設計問題] 複数地点を接続して効率的なネットワークを作るという問題にはいくつかのバリエーションがある. ここでは単純な場合としてシュタイナー木問題を取り上げる. |
||
| 11 | 11 | [線形計画法の解法] 線形計画法に対する「効率的」な開放を紹介し, その拡張としての半定値計画法を学ぶ. |
||
| 12 | 12 | [半定値計画法の近似アルゴリズムへの応用] 充足最大化問題を例にとり, 半定値計画法を応用して近似アルゴリズムが設計できることを示す. |
||
| 13 | 13 | [頂点彩色問題] 頂点彩色問題は一般に非常に難しい問題である. この問題に対して半定値計画法を応用することで性能の良い近似アルゴリズムが設計できることを示す. |
||
| 14 | 14 | [最適化問題間の変換] 「近似可能性」という点に着目してある最適化問題を他の最適化問題に変換する方法を紹介する. |
||
| 15 | 15 | [まとめ] 講義の内容について簡単にまとめを行う. |
| No. |
到達目標 ／Learning Goal |
知識・理解 ／Knowledge & Undestanding |
技能・表現 ／Skills & Expressions |
思考・判断 ／Thoughts & Decisions |
伝達・コミュニケーション ／Communication |
協働 ／Cooperative Attitude |
||
|---|---|---|---|---|---|---|---|---|
| 1 | 近似アルゴリズムの評価方法について理解する. | ○ | ○ | |||||
| 2 | 与えられた近似アルゴリズムを具体的に評価する. | ○ | ○ | ○ | ○ | |||
| 3 | 最適化問題の間の難易度について理解する. | ○ | ○ | ○ |
| No. |
到達目標 ／Learning Goal |
定期試験 ／Exam. |
中間レポート | ||||
|---|---|---|---|---|---|---|---|
| 1 | 近似アルゴリズムの評価方法について理解する. | ○ | |||||
| 2 | 与えられた近似アルゴリズムを具体的に評価する. | ○ | ○ | ||||
| 3 | 最適化問題の間の難易度について理解する. | ○ | |||||
|
評価割合（％） ／Allocation of Marks |
70 | 30 | |||||