計算理論Ⅱ (130002)

担当教員 井上 美智子(Michiko Inoue / いのうえ みちこ)、 大下 福仁(Fukuhito Ooshita / おおした ふくひと)
単位数 :1単位 選択・必修 :選択 講義室 :L2 講義スタイル :講義/公開
開講時期 Ⅱ期 木曜2限

授業目的  Distributed algorithms efficiently make multiple computers or processors work cooperative, and parallel algorithms solve larger-size problems very fast using multiple processors. Therefore, these algorithms need different design paradigms or design measures from those developed for the sequential computation theory. In this lecture, we can study the computation theory for distributed and parallel algorithms, and learn computation models, algorithm designs and analyses for these algorithms.
授業内容   We learn basic design and analysis techniques for parallel and distributed algorithms. Basic techniques are learned using fundamental problems as examples, and, in addition, advanced computation theory for parallel algorithms and fault-tolerant distributed algorithms are learned.

Chapter 1. Computation Model and Fundamental Distributed Algorithms
Chapter 2. Robust Fault-Tolerant Distributed Algorithm
Chapter 3. Self-Stabilizing Algorithm
Chapter 4. Wait-Free Algorithm
Chapter 5. PRAM Model and Fundamental Parallel Algorithms
Chapter 6. PRAM Techniques
Chapter 7. Mobile Agent
Chapter 8. Conclusions and Examination

教科書 No designated textbook. The handouts are available from this page.
参考書 1.G. Tel : Introduction to Distributed Algorithms, Cambridge University Press, 1994
2.J. JaJa : An Introduction to Parallel Algorithms, Addison Wesley, 1992
履修条件 Students are desired to have the background knowledge on
- algorithms and data structures, and
- computation theory for sequential algorithms.
成績評価 Students are evaluated by assignment (40%) and examination (60%).
オフィスアワー 16:50 - 18:20 on Thursday at B411.
配布資料 現在、配布資料はありません。