シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2018年度 | 開講年次 /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/2018/perfect/ | ||
| 更新日 /Last update |
2018/03/02 01:28:23 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ． 今年度は「理想グラフに対する組合せ最適化」を題材とする． グラフに対する最適化問題に対するアプローチを，その数理的側面と計算的側面の双方を意識して講義する． 基本的な概念の理解，および，解析手法を学び，例に対して応用が可能となることを目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this fiscal year is "Combinatorial Optimization for Perfect Graphs," with which we learn techniques in discrete optimization through topics around perfect graphs, from both mathematical and computational viewpoints. The goal is to understand the basic concepts, to learn methods for designing and analyzing algorithms, and to be able to apply the methods to examples. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，アルゴリズム論第一，線形代数学 Discrete Mathematics, Algorithms I, Linear Algebra |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
数理計画法，グラフとネットワーク，アルゴリズム論第二 Mathematical Programming, Graphs and Networks, Algorithms II |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, 1986. M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988. B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. R. Diestel, Graph Theory, 5th Edition, Springer 2016. その他，参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, 1986. M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988. B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. R. Diestel, Graph Theory, 5th Edition, Springer 2016. The related materials will be referred to in the class. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．例に対する応用は講義時間外の演習にて各自が行う． 授業計画： 第１回： 理想グラフと組合せ最適化 第２回： 代表的な理想グラフ (1)：二部グラフと二部グラフの線グラフ 第３回： 代表的な理想グラフ (2)：二部グラフの線グラフの補グラフ 第４回： 代表的な理想グラフ (3)：区間グラフと弦グラフ 第５回： 弱理想グラフ定理 (1)：グラフ理論的手法 第６回： 組合せ最適化と線形計画法 第７回： 凸多面体の基礎 第８回： 弱理想グラフ定理 (2)：多面体的手法 第９回： まとめ１ 第１０回： 楕円体法 (1)：基礎 第１１回： 楕円体法 (2)：アルゴリズム 第１２回： 組合せ最適化と半正定値計画法 第１３回： グラフのシャノン容量 第１４回： 理想グラフに対するアルゴリズム 第１５回： まとめ２ Plan: Basic concepts will be discussed in the class. Deeper understanding and applications will be complemented with homework and exercises. Schedule: 1: Perfect graphs and combinatorial optimization 2: Representative perfect graphs (1): Bipartite graphs and their line graphs 3: Representative perfect graphs (2): The complements of the line graphs of bipartite graphs 4: Representative perfect graphs (3): Interval graphs and chordal graphs 5: Weak perfect graph theorem (1): Graph-theoretic approach 6: Combinatorial optimization and linear programming 7: Basics of convex polyhedra 8: Weak perfect graph theorem (2): Polyhedral approach 9: Summary 1 10: Ellipsoid method (1): Basics 11: Ellipsoid method (2): Algorithm 12: Combinatorial optimization and semidefinite programming 13: Shannon capacity of a graph 14: Algorithms for perfect graphs 15: Summary 2 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
講義で出題される演習問題に取り組む． Solving exercises from classes. |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 期末試験によって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること．出題される演習問題の半分程度を解くことができる能力を最低達成基準とする． 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 |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
メールにて相談． Appointment by email |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
理想グラフの話題は組合せ最適化の中でも古典的ではありますが，その理論体系は多くの重要な技法を含んでいます．また，「連続と離散」という分類がどれほど無意味なことであるのか，ということも教えてくれます．重要な未解決問題も存在し，とても勉強する甲斐があるテーマとなっています． |
| その他 /Others |
他専攻，他研究科の学生も歓迎します． Students from other departments are welcome to join. |
| キーワード /Keywords |
グラフ，理想グラフ，染色数，安定集合，線形計画法，半正定値計画法，シャノン容量，楕円体法 Graph, Perfect graph, Chromatic number, Stable set, Linear programming, Semidefinite programming, Shannon capacity, Ellipsoid method |