計算理論Ⅱ (130002) Theory of Computation Ⅱ (130002)
 
◇ 担当教員 Instructor : 井上 美智子(Michiko Inoue / いのうえ みちこ)、 大下 福仁(Fukuhito Ooshita / おおした ふくひと)
◇ 単位数 Credits : 1単位 ◇ 選択・必修 Required/Elective : 選択 ◇ 講義室 Room : L2
◇ 講義スタイル Style : 講義/公開
◇ 開講時期 Quarter : Ⅱ期 木曜2限

◇ 授業目的 Course goals :  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.
◇ 授業内容 Course description :   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

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