第８回日本情報オリンピック （JOI 2008-2009） 春季トレーニング合宿講義予定
- 講義１ 3月20日
泉 祐介 先生
東京工業大学大学院情報理工学研究科計算工学専攻 博士課程在学
mi.cs.titech.ac.jp/yuizumi/index-ja.html
ACM-ICPC World Final 出場者
タイトル：メモ化探索と動的計画法 ― 馬鹿再帰から動的計画法へ ―
概要：
近年の情報オリンピックでは，動的計画法のアルゴリズムを一から
組み立てることが当たり前のように要求されているようであるが，
これはかなりの慣れがないと難しい．そこで本講義では，再帰による
総当たり的アルゴリズム（俗に「馬鹿再帰」などと呼ばれるもの）
から出発して，メモ化探索を経由しながら動的計画法に至るまでの
アプローチを紹介する．
主として動的計画法のアルゴリズムが組み立てられずに困っている者を
念頭に置いているが，動的計画法について理解している者に関しても，
メモ化探索と動的計画法の関係について改めて見つめる機会となること
を期待している．
- 講義２ 3月21日
原 正雄 先生
東海大学理学部 准教授
タイトル：コーディング以前
私が IOI や JOI，大学の教育活動の中で出会った問題の中からいくつか
を選んで解説をします．コーディングをする以前の問題に関する解析に
ついてお話をします．具体的な問題について，問題を論理的に記述し，
それを解くためのアルゴリズムを考え，そのアルゴリズムの効率を解析
します．この記述と解析には数学が便利です．なぜなら，数学は数量的
論理的な事柄を記述するための非常に強力な言語だからです．
話は私がどのように考えたかを紹介するかなり個人的な内容になると
思われますが，数学フリークのおじさんの経験談から皆さんたちの問題
へのアプローチについて見直したり互いに話し合ったりするきっかけに
なればよいと思っています．
- 講義３ 3月22日
岡本 吉央 先生
東京工業大学大学院 特任准教授
タイトル：組合せ最適化入門
概要：
組合せ最適化の初歩を講義します．題材はグラフに関する最適化問題と
します．特に，最適性を保証する「最大最小定理」に焦点を絞り，
そのような定理がなぜ嬉しいのか議論します．
- 講義４ 3月23・24日
未定（ショートコーディング大会かも？）