シラバス参照
シラバス参照
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2021年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 曜限 /Day, Period |
火／Tue 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/2021/hom/ | ||
| 更新日 /Last update |
2021/03/05 15:50:17 | 更新状況 /Update status |
公開中 /now open to public |
| 主題および達成目標 （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 academic year is "Graph homomorphisms." Graph homomorphisms appear as a generalization of the coloring problem, and they are to be a new standard of combinatorial optimization with their rich combinatorial and algebraic structures. The learning objective is to understand the concepts and methods, and to apply them to examples. |
|---|---|
| 前もって履修 しておくべき科目 （1,000文字以内） /Prerequisites （up to 1,000 letters） |
離散数学 Discrete Mathematics |
| 前もって履修しておくこ とが望ましい科目 （1,000文字以内） /Recommended prerequisites and preparation （up to 1,000 letters） |
アルゴリズム論第一，アルゴリズム論第二，グラフとネットワーク Algorithms I, Algorithms II, Graphs and Networks |
| 教科書等 （1,000文字以内） /Course textbooks and materials （up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書，参考文献： P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford University Press, 2004. C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001. G. Hahn and C. Tardif, Graph Homomorphisms: Structure and Symmetry, In: G. Hahn and G. Sabidussi (eds.) "Graph Symmetry", pp. 107-166, 1997. M. Bodirsky, Graph Homomorphisms and Universal Algebra Course Notes, TU Dresden, 2021. その他の参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books and Notes: P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford University Press, 2004. C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001. G. Hahn and C. Tardif, Graph Homomorphisms: Structure and Symmetry, In: G. Hahn and G. Sabidussi (eds.) "Graph Symmetry", pp. 107-166, 1997. M. Bodirsky, Graph Homomorphisms and Universal Algebra Course Notes, TU Dresden, 2021. The related materials will be referred to in the class. |
| 授業内容とその進め方 （2,000文字以内） /Course outline and weekly schedule （up to 2,000 letters） |
授業計画： 1. グラフの彩色と準同型 2. 準同型の基本性質 (1)：部分構造 3. 準同型の基本性質 (2)：準同型の合成 4. グラフの円彩色 5. グラフの分数彩色 6. グラフの積と準同型 7. 頂点可移性と準同型 8. グラフの商と引き込み 9. 前半のまとめ 10. グラフのコア 11. 準同型が導く半順序 (1)：構成 12. 準同型が導く半順序 (2)：構造 13. アルゴリズム (1)：例 14. アルゴリズム (2)：双対性 15. 後半のまとめ，最近の話題 Plan: 1. Graph colorings and homomorphisms 2. Fundamental properties of homomorphisms (1): Substructures 3. Fundamental properties of homomorphisms (2): Compositions 4. Circular colorings of graphs 5. Fractional colorings of graphs 6. Graph products and homomorphisms 7. Vertex-transitivity and homomorphisms 8. Quotients of graphs and retracts 9. Summary 1 10. Cores of graphs 11. The partially ordered set derived from homomorphisms (1): Construction 12. The partially ordered set derived from homomorphisms (2): Structures 13. Algorithms (1): Examples 14. Algorithms (2): Duality 15. Summary 2 and recent topics |
| 対面授業・遠隔授業の別 /Face-to-face or online lecture |
対面授業 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） （1,000文字以内） /Preparation and review outside class （up to 1,000 letters） |
講義動画を用いて復習を行う Recap by lecture videos |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 2回のレポートによって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること． Evaluation: Submission of two reports Evaluation criteria: Understanding of basic concepts, and ability of application of methods to examples |
| オフィスアワー：授業相談 （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 |
グラフの準同型，彩色，円彩色，巡回グラフ，分数彩色，Kneserグラフ，デカルト積，圏積，強積，頂点可移性，商，引き込み，コア，前順序，半順序，鎖，反鎖，稠密性，整合性 |