令和3年度「現代の数学と数理解析」(5月21日分)

質問など遠慮なくどうぞ→kawamura@kurims.kyoto-u.ac.jp

応対算法と競合比解析

与えられる入力(例えばゲームの局面)に対して何らかの答(次に打つ手)を出すやり方を予め定めたものを算法(algorithm)といいます。入力が未知なので、算法の性能は「如何なる入力に対しても○○以上に良い答を出す」という形で測ります(最悪の場合による評価)。無数にあり得る入力と算法との勝負ですから、性能の限界をくっきりと解明することは難しく、素朴な題材においてもしばしば未解決です。本講義ではこのような算法評価の例として、次々と与えられる入力に即答してゆく応対問題(online problem)を幾つか取り上げ、その算法の評価尺度である競合比(competitive ratio)の解析手法について紹介します。

講義資料

リンク