計算モデル論　　 Computation Models

---

◇ 担当教員：関　浩之（せき　ひろゆき）
◇ 単位数：２　◇開講時期：�V期　月曜１時限・木曜２時限 ◇講義室：L2
◇ 講義目的：
授業の前半では、「計算機で問題を解くときの、問題の難しさをはかる尺度はあるのだろうか」という観点から、逐次計算モデルにおける基本的で重要な考え方であるNP完全性について説明する。また、逐次計算モデルの状態遷移においてランダム性を導入する、状態を木構造に拡張する、超並列性を導入することにより、それぞれ、ランダム計算、項型計算、分子計算のモデルが得られる。授業の後半では、これらの計算モデルを紹介する。
◇　講義内容：
１．逐次計算モデルにおける計算量理論
・NP完全性の定義
・Cookの定理
・還元による証明法
２．ランダム計算モデル
・確率チューリング機械
・クラスPP、 BPP、ZPP、R
・暗号理論との関連
３．項型計算モデル
・項書換え系と木オートマトン
・合流性、停止性、書換え戦略
４．分子計算モデル
・DNA計算の考え方


◇ 教科書　：
なし。
◇ 参考書　：
授業中に紹介する。
◇ 前提とする知識（受講要件ではない）：
アルゴリズムとデータ構造（アルゴリズム概論）
形式言語理論、計算可能性（計算理論I）
一階述語論理 （人工知能基礎論）
◇ 成績評価：
レポート（２０〜３０％)、試験（７０〜８０％）。