全学共通科目講義(1回生~4回生対象)
|
現代の数学と数理解析 |
―― 基礎概念とその諸科学への広がり |
| |
日時: | 2015年4月17日(金) 16:30-18:00 |
場所: | 数理解析研究所 420号室 |
講師: | 高澤 兼二郎 助教 |
題目: | 最小木問題と最短巡回路問題--離散数学の "解ける" 問題と "解けない" 問題-- |
要約: |
与えられたネットワークにおいて,任意の 2 節点が通信可能であるような最小の部分ネットワークは高速に求めることができる. 一方,すべての節点を丁度 1 回通って初めの節点に戻ってくる最短の巡回路を高速に求める方法は知られていない.
これらの二つの問題は似ているようにも見えるが,計算量の視点からはまったく異なる難しさをもっている. 参考文献:
|
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html" |