◇ 担当教員：井上　美智子（いのうえ　みちこ）
◇ 単位数：２ ◇選択･必修：選択 ◇開講時期：�W期 水曜１限、金曜１限◇講義室：L3

◇ 授業目的：
多数のプロセッサを用いて高速に問題を解く並列アルゴリズム、多くの計算機を効率よく協調動作させる
分散アルゴリズムには、１台の計算機のための理論とは異なるアルゴリズムの設計論、解析手法が必要と
なる。本講義では、並列アルゴリズム、および分散アルゴリズムのための計算理論を学習し、これらのア
ルゴリズムのための計算モデル、アルゴリズムの設計法、解析法を習得する。

◇ 授業内容：
並列アルゴリズム、分散アルゴリズムの基本的な技法の設計法、解析法を習得する。基本的な問題を具体
例として取り上げ、並列アルゴリズム、分散アルゴリズムの基本的技法を学習する。また、並列計算量の
理論、フォールトトレラント分散アルゴリズムについても学習する。具体的には以下の内容を学習する。
1.	並列計算モデル（並列ランダムアクセス機械）　
2.	並列アルゴリズムの計算量（プロセッサ数・時間計算量）　　
3.	基本的な並列アルゴリズム　　
4.	Ｐ完全性　
5.	粗粒度 並列モデルとアルゴリズム　
6.	分散計算モデル　　
7.	分散アルゴリズムの計算量（通信計算量・領域計算量・時間計算量）　　
8.	基本的な分散アルゴリズム　
9.	フォールトトレラント分散アルゴリズム 



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