計算理論 II
Theory of Computation II

講義内容

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

  1. 分散計算モデル
  2. 分散アルゴリズムの計算量（通信計算量・領域計算量・時間計算量）
  3. 基本的な分散アルゴリズム（論理時計・リーダー選挙）
  4. フォールトトレラント分散アルゴリズム（自己安定アルゴリズム）
  5. 並列計算モデル（並列ランダムアクセス機械）
  6. 並列アルゴリズムの計算量（プロセッサ数・時間計算量）
  7. 基本的な並列アルゴリズム（リストランキング・グラフアルゴリズム）
  8. Ｐ完全性

教科書

なし

参考書

  1. J. JaJa : An Introduction to Parallel Algorithms, Addison Wesley, 1992
  2. A. Gibbons・W. Rytter : Efficient Parallel Algorithms, Cambridge University Press, 1988
  3. 宮野悟 : 並列アルゴリズム，近代科学社，1993
  4. G. Tel : Introduction to Distributed Algorithms, Cambridge University Press, 1994
  5. 亀田恒彦・山下雅史 : 分散アルゴリズム，近代科学社，1994

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