シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講学科・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-Mail |
okamotoy followed by @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2020/matching/ | ||
| 更新日 /Last updated |
2020/04/03 15:30:31 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
離散最適化における1つのトピックを集中的に学ぶ．今年度は「マッチング」を題材とする． マッチングの理論とアルゴリズムは，組合せ最適化の研究を推進する重要な役割を担っている．その基礎的な部分，つまり，Edmondsのアルゴリズムの理解を目指して，関連する概念と手法を理解し，例に対して応用が可能となることを達成目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this academic year is "Matchings." The theory and algorithms of matchings play a fundamental role in the development of combinatorial optimization. This course aims at understanding the basics, namely Edmonds' algorithm. The learning objective is to understand the concepts and methods, and to apply them to examples. |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
離散数学 Discrete Mathematics |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
アルゴリズム論第一，アルゴリズム論第二，数理計画法，グラフとネットワーク Algorithms I, Algorithms II, Mathematical Programming, Graphs and Networks |
| 教科書等 /Course textbooks and materials |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997. C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization Algorithms and Complexity, Dover, 1998. L. Lovász, M. Plummer, Matching Theory, AMS, 2009. その他，参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997. C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization Algorithms and Complexity, Dover, 1998. L. Lovász, M. Plummer, Matching Theory, AMS, 2009. The related materials will be referred to in the class. |
| 授業内容と その進め方 /Course outline and weekly schedule |
進め方：講義では基礎概念と考え方について学ぶ．より深い理解と具体例に対する応用は演習問題を通じて行う． 授業計画： 1. マッチングの用語 2. 二部グラフの最大マッチング 3. 二部グラフの最大マッチング：アルゴリズム 4. 一般グラフの最大マッチング 5. 一般グラフの最大マッチング：アルゴリズム 6. 線形計画法の復習 7. 整数計画法の復習 8. まとめ１ 9. 二部グラフの最小費用完全マッチング：線形計画法 10. 二部グラフの最小費用完全マッチング：アルゴリズム 11. 一般グラフの最小費用完全マッチング：線形計画法 12. 一般グラフの最小費用完全マッチング：完全整数双対性 13. 一般グラフの最小費用完全マッチング：アルゴリズム (概要) 14. 一般グラフの最小費用完全マッチング：アルゴリズム (詳細) 15. まとめ２ Plan: Basic concepts will be discussed in the class. Deeper understanding and applications will be complemented with homework and exercises. Schedule: 1. Terminology on matchings 2. Maximum matchings in bipartite graphs 3. Maximum matchings in bipartite graphs: Algorithm 4. Maximum matchings in general graphs 5. Maximum matchings in general graphs: Algorithm 6. Review: Linear programming 7. Review: Integer programming 8. Summary 1 9. Minimum-cost perfect matchings in bipartite graphs: Linear programming 10. Minimum-cost perfect matchings in bipartite graphs: Algorithm 11. Minimum-cost perfect matchings in general graphs: Linear programming 12. Minimum-cost perfect matchings in general graphs: Total dual integrality 13. Minimum-cost perfect matchings in general graphs: Algorithm (overview) 14. Minimum-cost perfect matchings in general graphs: Algorithm (detail) 15. Summary 2 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
演習問題に取り組む． Solving exercises |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
成績評価方法： 期末試験によって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること．出題される演習問題の半分程度を解くことができる能力を最低達成基準とする． Evaluation: Final exam Evaluation criteria: Understanding of basic concepts, and ability of application of methods to examples Minimum requirement: Being able to solve half of the exercises |
| オフィスアワー： 授業相談 /Office hours |
メールにて相談． Appointment by email |
| 学生へのメッセージ /Message for students |
マッチングの理論は初期の組合せ最適化研究において，非常に重要な役割を果たし，いまでもその輝きは失われていません．そこで培われた技法は，他の組合せ最適化問題にも適用され，現在の組合せ最適化理論が形成されました．この講義ではその端緒を味わいます． |
| その他 /Others |
他専攻，他研究科の学生も歓迎します． Students from other departments are welcome to join. |
| キーワード /Keyword(s) |
マッチング，最大マッチング，完全マッチング，交互道，増加道，Hallの定理，Kőnig-Egerváryの定理，奇成分，Tutteの定理，Tutte-Bergeの公式，花，縮約，線形計画法，双対定理，相補性定理，最適性条件，整数計画法，線形計画緩和，接続行列，完全双対整数性，ハンガリー法，ラミナ― matching, maximum matching, perfect matching, alternating path, augmenting path, Hall's theorem, Kőnig-Egerváry's theorem, odd component, Tutte's theorem, Tutte-Berge formula, blossom, contraction, Gallai-Edmonds decomposition, linear programming, duality theorem, complementarity theorem, optimality condition, integer programming, linear programming relaxation, incidence matrix, total dual integrality, Hungarian method, laminar |