大学院教育・講義

TOP > 大学院教育・講義 > 全学共通科目「現代の数学と数理解析」

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

 

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


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

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

第2回
日時: 2015年4月17日(金)
16:30-18:00
場所: 数理解析研究所 420号室
講師: 高澤 兼二郎 助教
題目: 最小木問題と最短巡回路問題--離散数学の "解ける" 問題と "解けない" 問題--
要約:
与えられたネットワークにおいて,任意の 2 節点が通信可能であるような最小の部分ネットワークは高速に求めることができる.
一方,すべての節点を丁度 1 回通って初めの節点に戻ってくる最短の巡回路を高速に求める方法は知られていない.

これらの二つの問題は似ているようにも見えるが,計算量の視点からはまったく異なる難しさをもっている.
本講義では,計算機科学の基礎をなす P,NP などの概念,P≠NP予想,最適化アルゴリズム設計などについて, 最小木問題と最短巡回路問題という代表的な二つの問題を例にとり解説する.

参考文献:

  • William J. Cook: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press, 2012.
    (邦訳) ウィリアム J. クック (著), 松浦俊輔 (訳): 驚きの数学:巡回セールスマン問題, 青土社, 2013.
  • B. Korte and J. Vygen: Combinatorial Optimization, Fourth edition, Springer-Verlag, 2008.
  • 繁野麻衣子: ネットワーク最適化とアルゴリズム, 朝倉書店, 2010.


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

 

← BACK TO THE TOP

← BACK TO THE TOP

  • Follow on

Research Institute for Mathematical Sciences (RIMS)