計算理論 II
Theory of Computation II

---

講義内容

　　多数の計算機を利用して問題を解くための並列アルゴリズム，分散アルゴリズムの研究が盛んに行なわれている。
　　本講義では，基本的な問題を具体例として取り上げ，並列アルゴリズム，分散アルゴリズムの基本的技法を紹介する。また，並列計算量の理論，フォールトトレラント分散アルゴリズムについても述べる。

　　１. 並列計算モデル（並列ランダムアクセス機械）
　　２. 並列アルゴリズムの計算量（プロセッサ数・時間計算量）
　　３. 基本的な並列アルゴリズム
　　４. Ｐ完全性
　　５.粗粒度 並列モデルとアルゴリズム
　　６. 分散計算モデル
　　７. 分散アルゴリズムの計算量（通信計算量・領域計算量・時間計算量）
　　８. 基本的な分散アルゴリズム
　　９. フォールトトレラント分散アルゴリズム

教科書

　　なし

参考書

　　１. J. JaJa : An Introduction to Parallel Algorithms, Addison Wesley, 1992
　　２. 宮野悟：並列アルゴリズム，近代科学社，1993
　　３. G.Tel : Introduction to Distributed Algorithms, Cambridge University Press, 1994
　　４. H.Attiya.J.Welch：Distributed Computing：Fundamentals,
　　　Simulations and Advanced Topics, McGraw-Hill,1998.
　　５. 亀田恒彦・山下雅史：分散アルゴリズム，近代科学社，1994

前提とする知識(必ずしも先修条件ではない)

　　アルゴリズムとデータ構造 （アルゴリズム概論 ）
　　計算量理論（計算理論 I ）　

成績評価方法及び基準

成績評価は、授業の出席（20％）、レポート（40％）、及び試験（40％）によっ て行う。