大学院
HOME 大学院 数理構造論
過去(2019年度)の授業の情報です
学内のオンライン授業の情報漏洩防止のため,URLやアカウント、教室の記載は削除しております。
最終更新日:2024年3月15日

授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。

数理構造論

Discrete Structures and Optimization
This course introduces discrete structures that help design of efficient algorithms for optimization. More specifically, it focuses on matching, matroids and extensions. The ultimate goal of this course is to explain the weighted linear matroid parity algorithm developed by S. Iwata and Y. Kobayashi (2017).
MIMA Search
時間割/共通科目コード
コース名
教員
学期
時限
4820-1008
GIF-MA6208L3
数理構造論
岩田 覚
S1 S2
木曜2限
マイリストに追加
マイリストから削除
講義使用言語
英語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
開講所属
情報理工学系研究科
授業計画
1. Matroids 2. Matroid Duality 3. Matroid Polytope 4. Exchangeability Graph 5. Matroid Intersecion 6. Weighted Matroid Intersection 7. Matching 8. Maximum Weight Matching 9. Matching Polytope 10. Applications 11. Matroid Parity 12. Weighted Linear Matroid Parity
授業の方法
Aural lecture with blackboard.
成績評価方法
Grade by assignments.
教科書
No particular textbook.
参考書
B. Korte and J. Vygen: Combinatorial Optimization, 5th ed., Springer-Verlag, 2010. L. Lovasz and M. D. Plummer: Matching Theory, AMS, 2009. A. Schrijver: Combinatorial Optimization --- Polyhedra and Efficiency, Springer-Verlag, 2003.
履修上の注意
Questions and discussions during the lecture will be welcome.