シラバス参照

授業情報／Course information

科目一覧へ戻る 2019/01/02 現在

授業基本情報
科目名（和文）
／Course		 近似アルゴリズム論
科目名（英文）
／Course		 Approximation Algorithms
時間割コード
／Registration Code		 61111201
学部（研究科）
／Faculty		 情報系工学研究科 博士前期課程
学科（専攻）
／Department		 システム工学専攻
担当教員（○：代表教員）
／Principle Instructor （○） and Instructors		 ○小野　孝男
オフィスアワー
／Office Hour		 小野　孝男(火曜日 ５限, 2608室)
開講年度
／Year of the Course		 2018年度
開講期間
／Term		 前期
対象学生
／Eligible Students		 1年,2年
単位数
／Credits		 2.0
授業概要情報
更新日
／Date of renewal		 2018/03/16
使用言語
／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 [まとめ]
講義の内容について簡単にまとめを行う.
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識?理解
／Knowledge & Undestanding		 技能?表現
／Skills & Expressions		 思考?判断
／Thoughts & Decisions		 伝達?コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 近似アルゴリズムの評価方法について理解する. ○ ○
2 与えられた近似アルゴリズムを具体的に評価する. ○ ○ ○ ○
3 最適化問題の間の難易度について理解する. ○ ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 中間レポート
1 近似アルゴリズムの評価方法について理解する. ○
2 与えられた近似アルゴリズムを具体的に評価する. ○ ○
3 最適化問題の間の難易度について理解する. ○
評価割合（％）
／Allocation of Marks		 70 30

科目一覧へ戻る