全学共通科目講義(1回生〜4回生対象)

 

現代の数学と数理解析
  ―― 基礎概念とその諸科学への広がり

授業のテーマと目的:
数学が発展してきた過程では、自然科学、 社会科学などの種々の学問分野で提起される問題を解決するために、 既存の数学の枠組みにとらわれない、 新しい数理科学的な方法や理論が導入されてきた。 また、逆に、そのような新しい流れが、 数学の核心的な理論へと発展した例も数知れず存在する。 このような数学と数理解析の展開の諸相について、第一線の研究者が、 自身の研究を踏まえた入門的・解説的な講義を行う。

数学・数理解析の研究の面白さ・深さを、 感性豊かな学生諸君に味わってもらうことを意図して講義し、 原則として予備知識は仮定しない。

第3回
日時: 2011年4月22日(金)
      16:30−18:00
場所: 数理解析研究所 420号室
講師: 岩田 覚 教授
題目: マトロイドと組合せ最適化
要約:
マトロイドは,ベクトルの一次独立性・従属性の組合せ的な性質を 公理化した概念として,H. Whitney (1935) によって導入された. 数理計画法の分野においては,1970年前後に効率的に解くことの できる多くの組合せ最適化問題がマトロイドを用いて説明できる ことが指摘された.その結果,組合せ最適化問題をマトロイドの 言葉で定式化し,汎用アルゴリズムを適用する手法が確立されて, 現在に至っている.

 本講では,ベクトルの一次独立性・従属性に関する線形代数の 復習 (あるいは予習) を出発点として,マトロイドを紹介する. さらに,グラフ上の最小木問題に代表される組合せ最適化問題が 効率的に解ける仕組みをマトロイドを用いて解説する.


"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html"