超碰人人揉人人捏人人添-97人人超碰国产精品-成人激情欧美国产第一页-亚洲欧美日韩中文字幕第一区

《分布式計(jì)算》教學(xué)大綱

一、課程的性質(zhì)、目的與任務(wù)

并行與分布式計(jì)算是當(dāng)今計(jì)算機(jī)科學(xué)與技術(shù)最為活躍的領(lǐng)域之一，以網(wǎng)絡(luò)為基礎(chǔ)的分布式計(jì)算是成本低，應(yīng)用范圍廣，具有廣闊發(fā)展前景的一個(gè)重要方向，而分布式算法是深入開(kāi)展分布式計(jì)算的核心基礎(chǔ)。

《分布式計(jì)算》是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)和軟件工程專(zhuān)業(yè)本科生的專(zhuān)業(yè)選修課程。本課程的教學(xué)任務(wù)和目標(biāo)是針對(duì)以計(jì)算機(jī)網(wǎng)絡(luò)為背景的大規(guī)模信息處理與計(jì)算機(jī)應(yīng)用問(wèn)題，介紹分布式計(jì)算中最基本的分布式算法設(shè)計(jì)的理論基礎(chǔ)、核心思想、基本概念、基本原理、基本方法、基本技術(shù)以及一些重要的基礎(chǔ)算法，幫助學(xué)生掌握分布式算法領(lǐng)域最基本的知識(shí)，使他們能夠運(yùn)用這些知識(shí)解決分布式計(jì)算領(lǐng)域內(nèi)一些簡(jiǎn)單問(wèn)題的分布式算法設(shè)計(jì)問(wèn)題，能夠?qū)Ψ植际剿惴ǖ恼_性和復(fù)雜性進(jìn)行分析。

通過(guò)本課程的學(xué)習(xí)，要求學(xué)生達(dá)到:

1．通過(guò)規(guī)范地完成若干“分布式算法設(shè)計(jì)基礎(chǔ)”課程的實(shí)驗(yàn)，進(jìn)一步鞏固所學(xué)的相關(guān)書(shū)本知識(shí)，在知識(shí)、能力、素質(zhì)上得到進(jìn)一步的提高；

2．有能力閱讀分布式計(jì)算領(lǐng)域的一些科技文獻(xiàn)，獨(dú)立開(kāi)展一些分布式算法設(shè)計(jì)、分析與應(yīng)用方面的工作，為未來(lái)從事分布式計(jì)算領(lǐng)域的工作奠定必要的分布式算法設(shè)計(jì)基礎(chǔ)。

二、課程教學(xué)基本內(nèi)容與要求

第一章 導(dǎo)論：分布式系統(tǒng)

（一）基本教學(xué)內(nèi)容

1.1 分布式系統(tǒng)的定義

1.2 體系結(jié)構(gòu)和語(yǔ)言

1.3 分布式算法

（二）基本要求

教學(xué)目的：掌握計(jì)算機(jī)分布式系統(tǒng)的基本概念、理解計(jì)算機(jī)體系結(jié)構(gòu)和語(yǔ)言，了解分布式算法。

教學(xué)重點(diǎn)：重點(diǎn)講解分布式系統(tǒng)的定義、體系結(jié)構(gòu)。

教學(xué)難點(diǎn)：分布式算法。

第二章 模型

（一）基本教學(xué)內(nèi)容

2.1 轉(zhuǎn)移系統(tǒng)和算法

2.2 轉(zhuǎn)移系統(tǒng)性質(zhì)的證明

2.3 事件的因果序和邏輯時(shí)鐘

2.4 附加假設(shè)，復(fù)雜度

（二）基本要求

教學(xué)目的：掌握模型的基本概念、轉(zhuǎn)移系統(tǒng)性質(zhì)，理解事件的因果序和邏輯時(shí)鐘，了解附加假設(shè)，復(fù)雜度。

教學(xué)重點(diǎn)：轉(zhuǎn)移系統(tǒng)和算法、事件的因果序和邏輯時(shí)鐘。

教學(xué)難點(diǎn)：轉(zhuǎn)移系統(tǒng)性質(zhì)的證明。

第三章 通信協(xié)議

（一）基本教學(xué)內(nèi)容

3.1 平衡滑動(dòng)窗口協(xié)議

3.2 基于計(jì)時(shí)器的協(xié)議

（二）基本要求

教學(xué)目的：理解平衡滑動(dòng)窗口協(xié)議，了解基于計(jì)時(shí)器的協(xié)議機(jī)制。

教學(xué)重點(diǎn)：基于計(jì)時(shí)器的協(xié)議。

教學(xué)難點(diǎn)：平衡滑動(dòng)窗口協(xié)議。

第四章 路由算法

（一）基本教學(xué)內(nèi)容

4.1 基于目的節(jié)點(diǎn)的路由

4.2 所有點(diǎn)對(duì)之間的最短路徑問(wèn)題

4.3 變更算法

4.4 帶有壓縮路由表的路由

4.5 分級(jí)路由存儲(chǔ)管理

（二）基本要求

教學(xué)目的：了解基于目的節(jié)點(diǎn)的路由，掌握所有點(diǎn)對(duì)之間的最短路徑問(wèn)題、變更算法，了解分級(jí)路由存儲(chǔ)管理技術(shù)。

教學(xué)重點(diǎn)：所有點(diǎn)對(duì)之間的最短路徑問(wèn)題、分級(jí)路由存儲(chǔ)管理技術(shù)。

教學(xué)難點(diǎn)：變更算法。

第五章 無(wú)死鎖的包交換

（一）基本教學(xué)內(nèi)容

5.1 引言

5.2 有結(jié)構(gòu)的方法

5.3 無(wú)結(jié)構(gòu)的方法

5.4 需進(jìn)一步研究的問(wèn)題

（二）基本要求

教學(xué)目的：掌握有結(jié)構(gòu)的、無(wú)結(jié)構(gòu)的無(wú)死鎖的包交換方法。

教學(xué)重點(diǎn)：有結(jié)構(gòu)的方法。

教學(xué)難點(diǎn)：無(wú)結(jié)構(gòu)的方法。

第六章 波動(dòng)算法與遍歷算法

（一）基本教學(xué)內(nèi)容

6.1 波動(dòng)算法的定義和使用

6.2 波動(dòng)算法集

6.3 遍歷算法

6.4 深度優(yōu)先搜索的時(shí)間復(fù)雜度

6.5 遺留問(wèn)題

（二）基本要求

教學(xué)目的：掌握波動(dòng)算法的定義和使用、波動(dòng)算法集的基本概念，理解遍歷算法和深度優(yōu)先搜索的時(shí)間復(fù)雜度，了解波動(dòng)算法與遍歷算法的遺留問(wèn)題。

教學(xué)重點(diǎn)：遍歷算法。

教學(xué)難點(diǎn)：深度優(yōu)先搜索的時(shí)間復(fù)雜度。

第七章 選舉算法

（一）基本教學(xué)內(nèi)容

7.1 引言

7.2 環(huán)網(wǎng)

7.3 任意網(wǎng)

7.4 korach-kutten-moran算法

（二）基本要求

教學(xué)目的：掌握korach-kutten-moran算法，了解選舉算法的環(huán)網(wǎng)和任意網(wǎng)。

教學(xué)重點(diǎn)：korach-kutten-moran算法。

教學(xué)難點(diǎn)：選舉算法的環(huán)網(wǎng)和任意網(wǎng)。

第八章 終止檢測(cè)

（一）基本教學(xué)內(nèi)容

8.1 預(yù)備知識(shí)

8.2 計(jì)算樹(shù)和森林

8.3 基于波動(dòng)的方法

8.4 其他方法

（二）基本要求

教學(xué)目的：了解終止檢測(cè)的計(jì)算樹(shù)和森林，掌握基于波動(dòng)的方法。

教學(xué)重點(diǎn)：基于波動(dòng)的方法。

教學(xué)難點(diǎn)：計(jì)算樹(shù)和森林。

第九章 匿名網(wǎng)絡(luò)

（一）基本教學(xué)內(nèi)容

9.1 預(yù)備知識(shí)

9.2 確定算法

9.3 概率選舉算法

9.4 網(wǎng)絡(luò)規(guī)模計(jì)算

（二）基本要求

教學(xué)目的：了解匿名網(wǎng)絡(luò)的確定算法，掌握概率選舉算法和網(wǎng)絡(luò)規(guī)模計(jì)算。

教學(xué)重點(diǎn)：概率選舉算法。

教學(xué)難點(diǎn)：網(wǎng)絡(luò)規(guī)模計(jì)算。

第十章 快照

（一）基本教學(xué)內(nèi)容

10.1 預(yù)備知識(shí)

10.2 兩個(gè)快照算法

10.3 使用快照算法

10.4 應(yīng)用：死鎖檢測(cè)

（二）基本要求

教學(xué)目的：了解兩個(gè)快照算法，掌握快照算法的使用，并進(jìn)行應(yīng)用。

教學(xué)重點(diǎn)：使用快照算法。

教學(xué)難點(diǎn)：應(yīng)用：死鎖檢測(cè)。

第十一章 方向偵聽(tīng)與定向

（一）基本教學(xué)內(nèi)容

11.1 引言和定義

11.2 環(huán)和弦環(huán)的選舉算法

11.3 超立方體上的計(jì)算

11.4 與復(fù)雜度有關(guān)的問(wèn)題

11.5 結(jié)論和未解決的問(wèn)題

（二）基本要求

教學(xué)目的：掌握環(huán)和弦環(huán)的選舉算法、超立方體上的計(jì)算，了解與復(fù)雜度有關(guān)的問(wèn)題。

教學(xué)重點(diǎn)：環(huán)和弦環(huán)的選舉算法、超立方體上的計(jì)算。

教學(xué)難點(diǎn)：與復(fù)雜度有關(guān)的問(wèn)題。

第十二章 網(wǎng)絡(luò)中的同步

（一）基本教學(xué)內(nèi)容

12.1 預(yù)備知識(shí)

12.2 同步網(wǎng)絡(luò)中的選舉

12.3 同步器算法

12.4 應(yīng)用：廣度優(yōu)先搜索

（二）基本要求

教學(xué)目的：掌握同步網(wǎng)絡(luò)中的選舉、同步器算法，了解網(wǎng)絡(luò)同步的應(yīng)用廣度優(yōu)先搜索。

教學(xué)重點(diǎn)：同步網(wǎng)絡(luò)中的選舉、同步器算法。

教學(xué)難點(diǎn)：應(yīng)用：廣度優(yōu)先搜索。

第十三章 分布式系統(tǒng)中的容錯(cuò)

（一）基本教學(xué)內(nèi)容

13.1 利用容錯(cuò)算法的原因

13.2 健壯算法

13.3 穩(wěn)定算法

（二）基本要求

教學(xué)目的：了解利用容錯(cuò)算法的原因，掌握健壯算法、穩(wěn)定算法。

教學(xué)重點(diǎn)：健壯算法。

教學(xué)難點(diǎn)：穩(wěn)定算法。

第十四章 異步系統(tǒng)中的容錯(cuò)

（一）基本教學(xué)內(nèi)容

14.1 一致性的不可能性

14.2 初始死進(jìn)程

14.3 確定可實(shí)現(xiàn)實(shí)例

14.4 概率一致性算法

14.5 弱終止性

（二）基本要求

教學(xué)目的：了解初始死進(jìn)程，掌握概率一致性算法、弱終止性。

教學(xué)重點(diǎn)：確定可實(shí)現(xiàn)實(shí)例。

教學(xué)難點(diǎn)：概率一致性算法。

第十五章 同步系統(tǒng)中的容錯(cuò)

（一）基本教學(xué)內(nèi)容

15.1 同步判定協(xié)議

15.2 鑒別協(xié)議

15.3 時(shí)鐘同步

（二）基本要求

教學(xué)目的：了解同步判定協(xié)議，掌握鑒別協(xié)議、時(shí)鐘同步。

教學(xué)重點(diǎn)：鑒別協(xié)議。

教學(xué)難點(diǎn)：時(shí)鐘同步。

第十六章 故障檢測(cè)

（一）基本教學(xué)內(nèi)容

16.1 模型和定義

16.2 用弱精確檢測(cè)器解一致性問(wèn)題

16.3 最終弱精確檢測(cè)器

16.4 故障檢測(cè)器的實(shí)現(xiàn)

（二）基本要求

教學(xué)目的：了解故障檢測(cè)的模型和定義，掌握用弱精確檢測(cè)器解一致性問(wèn)題、故障檢測(cè)器的實(shí)現(xiàn)。

教學(xué)重點(diǎn)：用弱精確檢測(cè)器解一致性問(wèn)題。

教學(xué)難點(diǎn)：故障檢測(cè)器的實(shí)現(xiàn)。

第十七章 穩(wěn)定性

（一）基本教學(xué)內(nèi)容

17.1 引言

17.2 圖論算法

17.3 穩(wěn)定方法學(xué)

（二）基本要求

教學(xué)目的：了解穩(wěn)定性基本知識(shí)，掌握?qǐng)D論算法，了解穩(wěn)定方法學(xué)。

教學(xué)重點(diǎn)：圖論算法。

教學(xué)難點(diǎn)：穩(wěn)定方法學(xué)。

三、課程各章節(jié)學(xué)時(shí)分配

四、本課程課外學(xué)習(xí)與修學(xué)指導(dǎo)

本課程的課外教學(xué)內(nèi)容和形式主要由學(xué)生讀書(shū)，任課教師輔導(dǎo)、答疑、批改作業(yè)、實(shí)踐環(huán)節(jié)等幾部分構(gòu)成，其中，實(shí)踐環(huán)節(jié)的實(shí)驗(yàn)教學(xué)另行安排教學(xué)內(nèi)容，實(shí)驗(yàn)教學(xué)內(nèi)容已經(jīng)剝離。本課程要求學(xué)生在有時(shí)間的情況下，盡可能完成教材中所有的習(xí)題。學(xué)生應(yīng)在任課教師的幫助下，認(rèn)真聽(tīng)課，反復(fù)思考，大量完成作業(yè)，在學(xué)習(xí)中反復(fù)進(jìn)行閱讀、思考、做習(xí)題，通過(guò)閱讀、思考、做習(xí)題、分析、聯(lián)想、概括、歸納、總結(jié)等多種有效的方式方法，比較全面、準(zhǔn)確地掌握課程的主要內(nèi)容和教學(xué)重點(diǎn)。

課程對(duì)學(xué)生作業(yè)的質(zhì)量要求是：正確、簡(jiǎn)潔、規(guī)范。“分布式算法設(shè)計(jì)基礎(chǔ)”課程的作業(yè)一般有相當(dāng)?shù)碾y度。不經(jīng)過(guò)一定數(shù)量的習(xí)題的練習(xí)，要比較深入地掌握“分布式算法設(shè)計(jì)基礎(chǔ)”的主要內(nèi)容是比較困難的，而且，本課程涉及到過(guò)去學(xué)生學(xué)習(xí)過(guò)的眾多基礎(chǔ)課和專(zhuān)業(yè)基礎(chǔ)課的內(nèi)容，沒(méi)有較好的基礎(chǔ)，學(xué)習(xí)本門(mén)課程是比較困難的。因此，學(xué)生關(guān)鍵是要將過(guò)去所學(xué)習(xí)的知識(shí)與本門(mén)課程所學(xué)的知識(shí)建立聯(lián)系，用心思考，融會(huì)貫通，這樣，才能從根本上把握課程的要點(diǎn)，體會(huì)到分布式計(jì)算的精妙之處。

五、本課程考核方式及成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)

考核方式：開(kāi)卷考試

成績(jī)?cè)u(píng)定方法：本課程的考核是平時(shí)成績(jī)、實(shí)驗(yàn)成績(jī)、期終考試成績(jī)相結(jié)合。具體比例為：上課出勤、作業(yè)占20%，實(shí)驗(yàn)成績(jī)30%，期末考試成績(jī)占50%。

其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%?？荚囶}型主要有：選擇題、填空題、簡(jiǎn)答題、計(jì)算題、算法題、分析題、綜合應(yīng)用題等。

六、教材及參考書(shū)

教材：《分布式算法導(dǎo)論（第二版）》，（荷）Gerard Tel譯者：霍紅衛(wèi)，機(jī)械工業(yè)出版社，2004.9

主要參考書(shū)：

[1]《分布式計(jì)算（第二版）》，Hagit Attiya，Jennifer Welch著，駱志剛等譯，電子工業(yè)出版社，2008.4

[2]《分布式系統(tǒng)概念與設(shè)計(jì)（英文版，第三版）》，George Coulouris 等，機(jī)械工業(yè)出版社，2004.1

[3]《分布計(jì)算環(huán)境》，王柏等，北京郵電大學(xué)出版社，北京，2000。

[4]《CORBA系統(tǒng)結(jié)構(gòu)、原理與規(guī)范》，OMG編者，韋樂(lè)平，電子工業(yè)出版社，2000。

[5]《COM原理與應(yīng)用》，潘愛(ài)民，清華大學(xué)出版社，2001。

大綱撰寫(xiě)人：李曾妍

大綱審閱人：彭智朝

教學(xué)副主任：易葉青

編寫(xiě)日期：2012.6