集中講義　解析学における計算の理論

九州大学　数理科学特論９／数理科学特別講義Ⅸ（集中講義）

平成29年7月10日（月）～14日（金）［初回7月10日（月）13:30～ ウエスト1号館D625中セミナー室（D棟6階）］

2日目（火）以降も13:30～です。

質問などはこちらのメールアドレスまで

計算可能性や計算量は離散的・有限的な操作による処理の能力と限界を語る概念であるが、適切な定式化によりこれを実数、実数値函数・集合、また一般の距離や測度といった解析学的対象にも適用して諸演算・構成の複雑さの度合を計算の視点から論ずることができる。本講義では計算可能解析学と呼ばれるこの分野の基礎から最近の話題まで紹介する。

特に予備知識は仮定せず、前半は一般的な計算可能性・計算量の理論への入門講義とする。後半ではこれを実数など連続的な世界に当てはめる枠組である二型計算と表現の理論を解説し、その応用として幾つかの分野（微分方程式、力学系、計算幾何など）の具体的な基本問題の計算可能性と計算量を扱う。

1. 計算理論の基礎（前半）
   • 問題と算法
   • 時間・空間の制限（P、L、PSPACEなど）
   • 非決定性・乱択・計数（NP、BPP、#Pなど）
   • 帰着、困難性、相対化
   • 参考書
     • M・シプサ著、太田・田中監訳『計算理論の基礎』原著第二版（共立出版）平成20年
     • 渡辺治『今度こそわかるP≠NP予想』（講談社）平成26年
     • I. Wegener, Komplexitätstheorie, Springer, 2003.（英訳Complexity Theory, Springer, 2005）
   • 演習問題はこちら
   • 初日のスライド.pdf
   • 二日目のスライド.pdf
   • 三日目のスライド.pdf
2. 実数の計算理論（後半）
   • 二型計算と表現の理論
   • 実数の表現と計算
   • 実函数や実数集合の計算
   • 参考書
     • K. Ko, Complexity Theory of Real Functions, Birkhäuser, 1991.
     • K. Weihrauch, Computable Analysis, Springer, 2000.
   • 四日目のスライド.pdf
   • 五日目のスライド.pdf

評価方法

単位を取る人は前半部の演習問題を所定の点数分だけ解いて下さい（講義中に誰かが黒板でやったものも可、7月31日までに事務室の提出箱へ）