計算理論�U　 Theory of Computation�U

---

◇ 担当教員：井上　美智子（いのうえ　みちこ）
◇ 単位数：２　◇　開講時期：�U期　月曜２時限・木曜１時限　◇　講義室：L2
◇ 講義目的：
本講義では、多数の計算機を利用して問題を解くための並列アルゴリズム，分散アルゴリズムの基本的な技法の習得を目的とする。基本的な問題を具体例として取り上げ，並列アルゴリズム，分散アルゴリズムの基本的技法を紹介する。また，並列計算量の理論，フォールトトレラント分散アルゴリズムについても述べる。
◇　講義内容：
１． 並列計算モデル（並列ランダムアクセス機械）　
２． 並列アルゴリズムの計算量（プロセッサ数・時間計算量）　　
３． 基本的な並列アルゴリズム　　
４． Ｐ完全性　
５． 粗粒度 並列モデルとアルゴリズム　
６． 分散計算モデル　　
７． 分散アルゴリズムの計算量（通信計算量・領域計算量・時間計算量）　　
８． 基本的な分散アルゴリズム　
９． フォールトトレラント分散アルゴリズム


◇ 教科書　：
特になし。講義ノートを配布。
◇ 参考書　：
１．J. JaJa : An Introduction to Parallel Algorithms, Addison Wesley, 1992　
２．宮野悟：並列アルゴリズム，近代科学社，1993　　
３．G.. Tel : Introduction to Distributed Algorithms, Cambridge University Press, 1994
４．亀田恒彦・山下雅史：分散アルゴリズム，近代科学社，1994
◇ 受講要件：
　　　前提とする知識（必ずしも専修条件ではない）
アルゴリズムとデータ構造（アルゴリズム概論 ）　
計算量理論（計算理論I）
◇ 成績評価：
試験（70％）および出席状況（30％）により成績を評価する。