全学共通科目講義(1回生〜4回生対象)
|
現代の数学と数理解析 |
―― 基礎概念とその諸科学への広がり |
| |
日時: | 2023年5月26日(金) 16:45−18:15 |
場所: | 数理解析研究所420号室 |
講師: | 河村 彰星 准教授 |
題目: |
応対算法と競合比解析 https://www.kurims.kyoto-u.ac.jp/~kawamura/t/gss/ |
要約: |
与えられる入力(例えばゲームの局面)に対して何らかの答(次に打つ手)を出すやり方を予め定めたものを算法(algorithm)といいます。入力が未知なので、算法の性能は「如何なる入力に対しても∞以上に良い答を出す」という形で測ります(最悪の場合による評価)。無数にあり得る入力と算法との勝負ですから、性能の限界をくっきりと解明することは難しく、素朴な題材においてもしばしば未解決です。本講義ではこのような算法評価の例として、次々と与えられる入力に即答してゆく応対問題(online
problem)を幾つか取り上げ、その算法の評価尺度である競合比(competitive ratio)の解析手法について紹介します。
参考文献:
|
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html" |