全学共通科目講義（１回生～４回生対象）
|
| 現代の数学と数理解析 |
| ―― 基礎概念とその諸科学への広がり |
| |
| 日時： | ２００９年６月２６日（金） １６：３０－１８：００ |
| 場所： | 数理解析研究所 ４２０号室 |
| 講師： | 岩田 覚 教授 |
| 題目： | マトロイドと組合せ最適化 |
| 要約： |
マトロイドは，ベクトルの一次独立性・従属性の組合せ的な性質を
公理化した概念として，H. Whitney (1935) によって導入された．
数理計画法の分野においては，1970年前後に効率的に解くことの
できる多くの組合せ最適化問題がマトロイドを用いて説明できる
ことが指摘された．その結果，組合せ最適化問題をマトロイドの
言葉で定式化し，汎用アルゴリズムを適用する手法が確立されて，
現在に至っている．
本講では，ベクトルの一次独立性・従属性に関する線形代数の 復習 (あるいは予習) を出発点として，マトロイドを紹介する． さらに，グラフ上の最小木問題に代表される組合せ最適化問題が 効率的に解ける仕組みをマトロイドを用いて解説する． |
|
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html" | |
