計算モデル論2003

授業の前半では, 「計算機で問題を解くときの, 問題の難しさをはかる尺度はあるのだろうか」という観点から, 逐次計算モデルにおける基本的で重要な考え方であるNP完全性について説明する.また, 逐次計算モデルの状態遷移においてランダム性を導入する, 状態を木構造に拡張する, 超並列性を導入することにより,それぞれ, ランダム計算, 項型計算, 分子計算のモデルが得られる.授業の後半では, これらの計算モデルを紹介する.
１.逐次計算モデルにおける計算量理論

・NP完全性の定義
・Cookの定理
・還元による証明法

2. ランダム計算モデル

・確率チューリング機械
・クラスPP, BPP, ZPP, R
・暗号理論との関連

3. 項型計算モデル

・項書換え系と木オートマトン
・合流性, 停止性, 書換え戦略

4. 分子計算モデル

・DNA計算の考え方