授業の前半では, 「計算機で問題を解くときの, 問題の難しさをはかる尺度はあるのだろうか」という観点から, 逐次計算モデルにおける基本的で重要な考え方であるNP完全性について説明する. 逐次計算モデルの状態遷移においてランダム性を導入する, 状態を木構造に拡張する, 複数の遷移系列間の同期を許す, 超並列性を導入することにより,それぞれ,ランダム計算, 項型計算, 並行計算, 分子計算のモデルが得られる. 授業の後半では, これらの計算モデルを紹介する. １. 逐次計算モデルにおける計算量理論 時間計算量と領域計算量 NP完全性の定義 Cookの定理 還元による証明法 ２. ランダム計算モデル 確率チューリング機械 クラスPP, BPP, ZPP, R 暗号理論との関連 ３. 項型計算モデル 項書換え系と木オートマトン 合流性, 停止性, 書換え戦略 関数型プログラミングへの応用 ４.並行計算モデル プロセス代数の基礎 CCS, LOTOS ５. 分子計算モデル DNA計算の考え方

なし

授業中に紹介する

(必ずしも先修条件ではない) ・アルゴリズムとデータ構造 (アルゴリズム概論) ・形式言語理論, 計算可能性 (計算理論I) ・一階述語論理 (人工知能基礎論)

レポート(20〜30%), 試験(70〜80%)