《分布式算法導(dǎo)論》課程教學(xué)大綱

《分布式算法導(dǎo)論》教學(xué)大綱適用范圍：2020版本科人才培養(yǎng)方案課程代碼：08150321課程性質(zhì)：專業(yè)選修課學(xué)分：3學(xué)分學(xué)時(shí)：48學(xué)時(shí)（其中：理論32學(xué)時(shí)，實(shí)驗(yàn)16學(xué)時(shí)）先修課程：HCNA存儲(chǔ)網(wǎng)絡(luò)體系后續(xù)課程：適用專業(yè)：物聯(lián)網(wǎng)工程、物聯(lián)網(wǎng)工程（專升本）教材：《分布式算法導(dǎo)論》（第二版），泰爾著，霍紅衛(wèi)譯，機(jī)械工業(yè)出版社，2004.9開課單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一、課程的性質(zhì)與任務(wù)課程性質(zhì)：本課程是物聯(lián)網(wǎng)工程、物聯(lián)網(wǎng)工程（專升本）專業(yè)本科學(xué)生的專業(yè)選修課。課程任務(wù)：通過本課程的學(xué)習(xí)，使學(xué)生對(duì)于分布式算法的基本理論與基礎(chǔ)知識(shí)能有所接觸了解，并實(shí)際編程解決課堂上的算法問題，以掌握部分算法的編程與操作，為物聯(lián)網(wǎng)專業(yè)上的能力打下牢固的基礎(chǔ)。本課程的教學(xué)任務(wù)和目標(biāo)是針對(duì)以計(jì)算機(jī)網(wǎng)絡(luò)為背景的大規(guī)模信息處理與計(jì)算機(jī)應(yīng)用問題，介紹分布式計(jì)算中最基本的分布式算法設(shè)計(jì)的理論基礎(chǔ)、核心思想、基本概念、基本原理、基本方法、基本技術(shù)以及一些重要的基礎(chǔ)算法，幫助學(xué)生掌握分布式算法領(lǐng)域最基本的知識(shí)，使他們能夠運(yùn)用這些知識(shí)解決分布式計(jì)算領(lǐng)域內(nèi)一些簡(jiǎn)單問題的分布式算法設(shè)計(jì)問題，能夠?qū)Ψ植际剿惴ǖ恼_性和復(fù)雜性進(jìn)行分析。二、課程教學(xué)目標(biāo)1.知識(shí)目標(biāo)掌握和理解分布式算法基本原理、主要算法及應(yīng)用等基本知識(shí)；2.能力目標(biāo)掌握分步式算法編程實(shí)踐；3.素質(zhì)目標(biāo)樹立正確的政治理想和政治道德，培養(yǎng)對(duì)黨和國(guó)家，社會(huì)主義事業(yè)忠誠(chéng)可靠的建設(shè)者和接班人。三、課程的基本內(nèi)容及要求（一）導(dǎo)論：分布式系統(tǒng)1．課程教學(xué)內(nèi)容（1）分布式系統(tǒng)的定義；（2）體系結(jié)構(gòu)和語言；（3）分布式算法。2．課程重點(diǎn)難點(diǎn)重點(diǎn):重點(diǎn)講解分布式系統(tǒng)的定義、體系結(jié)構(gòu)。難點(diǎn):分布式算法。3．課程教學(xué)要求掌握計(jì)算機(jī)分布式系統(tǒng)的基本概念、理解計(jì)算機(jī)體系結(jié)構(gòu)和語言，了解分布式算法。（二）路由算法1．課程教學(xué)內(nèi)容（1）基于目的節(jié)點(diǎn)的路由；（2）所有點(diǎn)對(duì)之間的最短路徑問題；（3）變更算法；（4）帶有壓縮路由表的路由；（5）分級(jí)路由存儲(chǔ)管理。2．課程重點(diǎn)難點(diǎn)重點(diǎn):所有點(diǎn)對(duì)之間的最短路徑問題、分級(jí)路由存儲(chǔ)管理技術(shù)。難點(diǎn):變更算法。3．課程教學(xué)要求了解基于目的節(jié)點(diǎn)的路由，掌握所有點(diǎn)對(duì)之間的最短路徑問題。（三）無死鎖的包交換1．課程教學(xué)內(nèi)容（1）有結(jié)構(gòu)的方法；（2）無結(jié)構(gòu)的方法；（3）需進(jìn)一步研究的問題。2．課程重點(diǎn)難點(diǎn)重點(diǎn):有結(jié)構(gòu)的方法。難點(diǎn):無結(jié)構(gòu)的方法。3．課程教學(xué)要求掌握有結(jié)構(gòu)的、無結(jié)構(gòu)的無死鎖的包交換方法。（四）波動(dòng)算法與遍歷算法1．課程教學(xué)內(nèi)容（1）波動(dòng)算法的定義和使用；（2）波動(dòng)算法集；（3）遍歷算法；（4）深度優(yōu)先搜索的時(shí)間復(fù)雜度；（5）遺留問題。2．課程重點(diǎn)難點(diǎn)重點(diǎn):遍歷算法。難點(diǎn):深度優(yōu)先搜索的時(shí)間復(fù)雜度。3．課程教學(xué)要求掌握波動(dòng)算法的定義和使用、波動(dòng)算法集的基本概念。（五）選舉算法1．課程教學(xué)內(nèi)容（1）環(huán)網(wǎng)；（2）任意網(wǎng)；（3）korach-kutten-moran算法。2．課程重點(diǎn)難點(diǎn)重點(diǎn):korach-kutten-moran算法。難點(diǎn):選舉算法的環(huán)網(wǎng)和任意網(wǎng)。3．課程教學(xué)要求掌握korach-kutten-moran算法，了解選舉算法的環(huán)網(wǎng)和任意網(wǎng)。（六）終止檢測(cè)1．課程教學(xué)內(nèi)容（1）計(jì)算樹和森林；（2）基于波動(dòng)的方法；（3）其他方法。2．課程重點(diǎn)難點(diǎn)重點(diǎn):基于波動(dòng)的方法。難點(diǎn):計(jì)算樹和森林。3．課程教學(xué)要求了解終止檢測(cè)的計(jì)算樹和森林，掌握基于波動(dòng)的方法。（七）匿名網(wǎng)絡(luò)1．課程教學(xué)內(nèi)容（1）確定算法；（2）概率選舉算法；（3）網(wǎng)絡(luò)規(guī)模計(jì)算。2．課程重點(diǎn)難點(diǎn)重點(diǎn):概率選舉算法。難點(diǎn):網(wǎng)絡(luò)規(guī)模計(jì)算。3．課程教學(xué)要求了解匿名網(wǎng)絡(luò)的確定算法，掌握概率選舉算法和網(wǎng)絡(luò)規(guī)模計(jì)算。（八）快照1．課程教學(xué)內(nèi)容（1）兩個(gè)快照算法；（2）使用快照算法；（3）應(yīng)用：死鎖檢測(cè)。2．課程重點(diǎn)難點(diǎn)重點(diǎn):使用快照算法。難點(diǎn):應(yīng)用：死鎖檢測(cè)。3．課程教學(xué)要求了解兩個(gè)快照算法，掌握快照算法的使用，并進(jìn)行應(yīng)用。四、課程學(xué)時(shí)分配教學(xué)章節(jié)理論實(shí)踐（驗(yàn)）討論、習(xí)題一、導(dǎo)論：分布式系統(tǒng)4二、路由算法44三、無死鎖的包交換4四、波動(dòng)算法與遍歷算法44五、選舉算法4六、終止識(shí)別44七、匿名網(wǎng)絡(luò)4八、快照44總計(jì)3216五、課程考核方式與要求考核方式：本課程主要以課程視頻、課堂表現(xiàn)、作業(yè)、測(cè)試和期末大作業(yè)等方式對(duì)學(xué)生進(jìn)行考核評(píng)價(jià)?？己嘶疽螅嚎己丝偝煽?jī)由期末大作業(yè)成績(jī)和過程性評(píng)價(jià)成績(jī)組成。其中：期末大作業(yè)成績(jī)?yōu)?00分（權(quán)重60%），試題類型為設(shè)計(jì)、編程等題型；課程視頻、課堂表現(xiàn)、作業(yè)、測(cè)試等過程性評(píng)價(jià)成績(jī)?yōu)?00分（權(quán)重40%）；過程性評(píng)價(jià)和考試試題分值分配應(yīng)與教學(xué)大綱各章節(jié)的學(xué)時(shí)基本成比例。六、課程資源庫(kù)1.NancyA.Lynch，DistributedAlgorithms,ElsevierIndia，2009.7。2.王柏，分布計(jì)算環(huán)境，北京郵電大學(xué)出版社，2000.8。3.HagitAttiya，JenniferWelch(駱志剛譯)，分布式計(jì)算（第二版），電子工業(yè)出版社，2008.4。4.DistributedAlgorithms:AnIntuitiveApproach，WanFokkink著，MIT出版社，2018.2。5.李文軍.并行與分布式計(jì)算教學(xué)改革與課程建設(shè)[J].高等理科教育,2005(4):62-66.6.何鳳英,鐘尚平,蔣秀鳳.分布式計(jì)算課程教學(xué)方法探索[J].計(jì)算機(jī)教育,2013(13):94-97.7.孫宏安.分布式計(jì)算梅森數(shù)和費(fèi)馬數(shù)[J].中學(xué)數(shù)學(xué)教學(xué)參考,2006(21):59-61.8.Benn,楊宏戟.分布式計(jì)算系統(tǒng)在英國(guó)學(xué)術(shù)界的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,1992(8):60-62.9.Tomassini,Marco."Parallelanddistributedevolutionaryalgorithms:Areview."(1999).10.OReillyMedia，百度分布式數(shù)據(jù)庫(kù)，/v_show/id_X