シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 開講年度 /Academic year |
2013年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 連携専門科目 | ||
| 開講類・専攻 /Cluster/Department |
情報・通信工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-mail |
okamotoy@uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/localsearch/ | ||
| 更新日 /Last update |
2013/07/28 07:22:06 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ．今年度は「局所探索法の理論的側面」を題材とする． 局所探索法における基本的な概念の理解，および，解析手法と例に対する応用が可能となることを目標とする． |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学 |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
アルゴリズム論第一，アルゴリズム論第二，数理解析，数理計画法 (あるいは，それに準じる内容) |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書：なし．資料を毎回用意する． 参考書： W. Michiels, E. Aarts, J. Korst, "Theoretical Aspects of Local Search", Springer, 2007. E. Aarts, J. K. Lenstra, eds., "Local Search in Combinatorial Optimization", Princeton University Press, 2003. 柳浦睦憲，茨木俊秀，「組合せ最適化―メタ戦略を中心として―」，朝倉書店，2001． その他，参考となる文献は講義中に挙げる． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．例に対する応用は講義時間外の演習にて各自が行う． 授業計画： 第１回： 離散最適化問題と局所探索法 第２回： 解の表現 第３回： 近傍関数と近傍グラフ 第４回： 近傍グラフの性質 (1)：連結性 第５回： 近傍グラフの性質 (2)：直径 第６回： 性能保証 (1)：厳密近傍 第７回： 性能保証 (2)：近似保証 (下界) 第８回： 性能保証 (3)：近似保証 (上界) 第９回： 計算量 (1)：上界と下界 第１０回： 計算量 (2)：クラスPLSとPLS完全性 第１１回： 計算量 (3)：PLS完全性 第１２回： 大規模近傍 第１３回： 近似局所探索 第１４回： 最近のトピック (1) 第１５回： 最近のトピック (2) |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 期末試験によって評価を行う． 評価基準： 局所探索法における基本的な概念を理解し，解析手法と例に対する応用ができること．出題される演習問題の半分程度を解くことができる能力を最低達成基準とする． |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
金曜5限．時間が不都合な場合はメールにて相談してください． |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
局所探索法は離散最適化に対する重要なアプローチですが，その理論的側面が大学の講義で扱われることはほとんどありませんでした．この講義では他の大学では受けられないユニークでエキサイティングな内容を扱います． |
| その他 /Others |
情報数理工学コース，コンピュータサイエンスコース以外の学生も歓迎します． |
| キーワード /Keywords |
局所探索法，近傍，アルゴリズムの性能保証，アルゴリズムの計算量，クラスPLS |