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