算法設(shè)計與分析課件

xxx算法設(shè)計與分析遼寧師范大學(xué)計算機與信息技術(shù)學(xué)院計算機科學(xué)與技術(shù)專業(yè)課程AlgorithmDesignandAnalysis關(guān)于任課教師課程介紹什么是算法算法的描述算法分析宋傳鳴講師2003年本科畢業(yè)于遼寧師范大學(xué)計算機科學(xué)與技術(shù)系計算機應(yīng)用技術(shù)專業(yè),工學(xué)學(xué)士2006年碩士畢業(yè)于遼寧師范大學(xué)計算機科學(xué)與技術(shù)系計算機應(yīng)用技術(shù)專業(yè),工學(xué)碩士2010年博士畢業(yè)于南京大學(xué)計算機科學(xué)與技術(shù)系計算機應(yīng)用技術(shù)專業(yè),工學(xué)博士2010年7月回校任教至今聯(lián)系方式電子郵件:辦公室:西山校區(qū)第二教學(xué)樓B614

個人主頁:關(guān)于《算法設(shè)計與分析》課程課程介紹什么是算法算法的描述算法分析課程性質(zhì)本課程屬于專業(yè)選修課(計算機科學(xué)與技術(shù))、專業(yè)必修課(計算機科學(xué)與技術(shù)(動畫))開設(shè)目的使學(xué)生掌握非數(shù)值算法設(shè)計的主要方法獨立設(shè)計算法和對算法進行復(fù)雜性計算奠定基礎(chǔ)利用所學(xué)的算法設(shè)計策略解決實際問題的能力

學(xué)時安排48學(xué)時,每周3學(xué)時,修完課程可獲3學(xué)分考核方式——考察期末為閉卷筆試,成績占總成績的50%平時出勤占5%,學(xué)期論文(3篇)占45%(第4/8/12周)試卷題型:概念型、設(shè)計型、證明型關(guān)于《算法設(shè)計與分析》課程課程介紹什么是算法算法的描述算法分析在專業(yè)教學(xué)計劃中的地位和作用在IEEEACM公布的《ComputerScienceCurriculum2008》與中國計算機學(xué)會教育委員會、全國高等學(xué)校計算機教育研究會推出的CCC2004(ChinaComputingCurricula2004-CS)中,算法設(shè)計與分析都是其核心課程之一算法設(shè)計與分析具有學(xué)科核心的重要地位,能夠充分體現(xiàn)計算機科學(xué)方法論的理論、抽象和設(shè)計3個過程,知識面較寬,有一定的深度

反復(fù)再現(xiàn)計算機科學(xué)中用到的典型問題的復(fù)雜性、效率、抽象的層次、重用、折衷等帶有普遍性的概念

不僅是計算機科學(xué)與技術(shù)專業(yè)后續(xù)課程的理論基礎(chǔ),而且還廣泛地用于新興的技術(shù)和研究領(lǐng)域

關(guān)于《算法設(shè)計與分析》課程課程介紹什么是算法算法的描述算法分析計算思維(ComputationalThinking)摘自《中國計算機學(xué)會通訊》2012年第一期理論科學(xué)、實驗科學(xué)、計算科學(xué)被稱為推動人類文明進步和科技發(fā)展的三大科學(xué)科學(xué)思維包括理論思維、實驗思維和計算思維理論思維以推理和演繹為特征,如數(shù)學(xué)學(xué)科實驗思維以觀察和總結(jié)自然規(guī)律為特征,如物理學(xué)科計算思維以設(shè)計和構(gòu)造為特征,如計算機學(xué)科計算思維是運用計算的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類行為的一種方法.它合用了數(shù)學(xué)思維(求解問題的方法)、工程思維(設(shè)計、評價大型復(fù)雜系統(tǒng))和科學(xué)思維(理解可計算性、智能、心理和人類行為)計算思維課程現(xiàn)已在部分高校中開啟教材(Textbook)課程介紹什么是算法算法的描述算法分析王曉東編著.計算機算法設(shè)計與分析(第3版).北京:電子工業(yè)出版社,2007.主要參考書(References)課程介紹什么是算法算法的描述算法分析M.H.Alsuwaiyel著,吳偉昶,方世昌譯.算法設(shè)計技巧與分析.北京:電子工業(yè)出版社,2010.ThomasH.Cormer等著,潘金貴,顧鐵成等譯.算法導(dǎo)論(第二版).北京:機械工業(yè)出版社,2010

主要參考書(References)課程介紹什么是算法算法的描述算法分析TheArtofComputerProgramming數(shù)據(jù)結(jié)構(gòu)的開拓者D.E.Knuth的計算機科學(xué)發(fā)展史上的不朽之作第1卷基本算法:介紹計算機程序設(shè)計的基本算法,包括基本的編程概念和技術(shù)以及信息結(jié)構(gòu)--機內(nèi)信息的表示、數(shù)據(jù)元及其處理的結(jié)構(gòu)關(guān)系第2卷半數(shù)值算法:介紹隨機數(shù)和算術(shù),提供了計算機編程和數(shù)值分析之間的豐富接口第3卷排序與查找:介紹排序和查找的最權(quán)威的經(jīng)典技術(shù),擴充了第1卷的數(shù)據(jù)結(jié)構(gòu),以處理大小型數(shù)據(jù)庫及內(nèi)外部存儲.本書偏重分析技術(shù),采用匯編語言描述算法,是一本本學(xué)科最經(jīng)典最權(quán)威的百科全書,適合于從事數(shù)據(jù)結(jié)構(gòu)與算法研究的專家閱讀《算法設(shè)計與分析》課程的主要內(nèi)容課程介紹什么是算法算法的描述算法分析第一章緒論第二章數(shù)學(xué)預(yù)備知識與典型的數(shù)據(jù)結(jié)構(gòu)第三章遞歸與分治策略

第四章動態(tài)規(guī)劃第五章貪心算法第六章NP完全問題第七章回溯法第八章分支限界法第九章隨機化算法

第十章網(wǎng)絡(luò)流算法第十一章并行算法入門《算法設(shè)計與分析》課程的基本要求課程介紹什么是算法算法的描述算法分析培養(yǎng)學(xué)習(xí)方法與習(xí)慣上課記筆記閱讀與自學(xué)理論聯(lián)系實際查找資料課上認(rèn)真聽講,課后多思考多翻閱資料關(guān)于理論計算機科學(xué)課程介紹什么是算法算法的描述算法分析關(guān)于計算機和計算機械的數(shù)學(xué)理論,也稱計算理論自動機與形式語言理論程序理論形式語義學(xué)算法分析和計算復(fù)雜性理論學(xué)科產(chǎn)生20世紀(jì)30年代,人們關(guān)注是否存在一種有效過程求解問題,即問題的可解與不可解性如果存在某個模型能夠建立一個算法求解問題,則將該問題歸入可解的問題類30年代前期,哥德爾等創(chuàng)立遞歸函數(shù)30年代中期,丘奇的λ演算,波斯特的波斯特機,圖靈的圖靈機40年代后期:存儲程序型計算機(RAM,RASPM)算法分析與計算復(fù)雜性理論課程介紹什么是算法算法的描述算法分析各類具體算法的復(fù)雜性的研究稱作算法分析一般算法的復(fù)雜性的研究稱作計算機復(fù)雜性理論計算復(fù)雜性理論原是可計算理論的一支,是以各種可計算函數(shù)(遞歸函數(shù))的計算復(fù)雜性為研究對象基本問題實際可計算函數(shù)的結(jié)構(gòu)和性質(zhì)60年代中期以來,有關(guān)研究者一般以計算時間多項式有界的函數(shù)作為實際可計算的函數(shù)確定性機器與非確定性機器的解題能力比較關(guān)于計算和算法的研究對串行計算的性質(zhì)研究多對并行計算性質(zhì)的研究少算法(Algorithm)的定義課程介紹什么是算法算法的描述算法分析解決問題的一種方法或過程,由若干條指令組成Algorithm一詞源于公元九世紀(jì)的一位波斯數(shù)學(xué)家MuhammadibnMusaal-Khwarizmi的書<Rulesofrestoringandequating>示例:給定正數(shù)m和n,找出兩個數(shù)的最大公約數(shù)E1.用n除以m,并令r為余數(shù)(0≦r<n)E2.如果r=0,則算法結(jié)束,n為所求E3.令m=n,n=r,轉(zhuǎn)入E1.算法的性質(zhì)輸入:有零個或多個由外部提供的量輸出:至多一個量作為輸出確定性:每條指令是清晰的,無歧義的有限性:每條指令執(zhí)行次數(shù)有限,執(zhí)行時間也有限有效性:每個操作須使用戶利用紙筆在有限時間內(nèi)精確地完成求解問題的一般過程課程介紹什么是算法算法的描述算法分析算法與程序課程介紹什么是算法算法的描述算法分析算法與程序的區(qū)別程序是算法用某種程序設(shè)計語言的具體實現(xiàn)程序可以不滿足算法的第四條性質(zhì)為什么要學(xué)習(xí)算法？算法是程序的靈魂問題求解過程:分析問題—設(shè)計算法—編寫程序—整理結(jié)果程序設(shè)計研究的四個層次:算法—方法學(xué)—語言—工具提高分析問題的能力算法的形式化—思維的邏輯性和條理性算法可以解決哪些類型的問題?課程介紹什么是算法算法的描述算法分析問題的特點有很多候選的解決方案,而要找出其中真正需要的方案并不容易的情況有著實際應(yīng)用背景,但是受到經(jīng)濟利益,運行成本等多方面的限制算法應(yīng)用舉例人類基因組項目:找出人類DNA中所有100000種基因,確定構(gòu)成人類DNA的30億種化學(xué)基對的各種序列,并將信息存儲,檢索和分析等互聯(lián)網(wǎng):尋找合理的數(shù)據(jù)傳輸路徑電子商務(wù):保持私人信息,采用公鑰和數(shù)字簽名等交通:GPS導(dǎo)航計算幾何:求解平面上n個點的凸殼數(shù)值計算:求解n個矩陣相乘,解方程組等……算法可以解決哪些類型的問題?課程介紹什么是算法算法的描述算法分析重要的問題類型查找問題排序問題圖問題組合問題幾何問題算法的描述課程介紹什么是算法算法的描述算法分析自然語言優(yōu)點:容易理解缺點:冗長,有二義性使用方法:粗線條描述算法思想注意事項:避免寫成自然段流程圖優(yōu)點:直觀缺點:缺少嚴(yán)密性和靈活性使用方法:描述簡單算法注意事項:注意抽象層次算法的描述課程介紹什么是算法算法的描述算法分析程序設(shè)計語言優(yōu)點:能由計算機執(zhí)行缺點:抽象性差,對語言要求高使用方法:對算法進行驗證注意事項:將算法寫成子函數(shù)算法的描述課程介紹什么是算法算法的描述算法分析偽代碼(PseudoCode)—算法語言介于自然語言和程序設(shè)計語言之間.采用某一程序設(shè)計語言的基本語法,操作指令可結(jié)合自然語言來設(shè)計優(yōu)點:表達能力強,容易理解1.r←m%n;2.循環(huán)直到r←02.1m←n;2.2n←r;2.3r←m%n;3.輸出n算法復(fù)雜性分析(ComplexityAnalysis)課程介紹什么是算法算法的描述算法分析算法復(fù)雜性=算法所需要的計算機資源時間復(fù)雜性(TimeComplexity):T=T(N,I)空間復(fù)雜性(SpatialComplexity):S=S(N,I)N表示問題的規(guī)模,I表示算法的輸入計算機包含的運算有多種,記為O1,O2,…,Ok,執(zhí)行時間分別為t1,t2,…,tk,每種運算的次數(shù)為e1,e2,…,ek,則有一般情況下,不考慮每種運算的時間差異有代表性的算法復(fù)雜性課程介紹什么是算法算法的描述算法分析評價規(guī)模為N的某些或某類有代表性的合法輸入時的算法復(fù)雜度最壞情況下的時間復(fù)雜度最好情況下的時間復(fù)雜度平均情況下的時間復(fù)雜度DN表示規(guī)模為Ｎ的合法輸入的集合,P(I)表示出現(xiàn)輸入I的概率例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析插入排序(升序排列):每次選取未排序數(shù)中的第一個數(shù),將其插入已排好序數(shù)列的合適位置代價執(zhí)行次數(shù)C1nC2n－1C3n－1C4sum(tj)C5sum(tj－1)C6sum(tj－1)C7n－1例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析插入排序的時間復(fù)雜度最好情況下:輸入數(shù)組已排好序,每次不進入while循環(huán),則有最好情況下:輸入數(shù)組逆序,A[i]必須與已排好序的元素逐一比較,因此tj=j,則有例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析插入排序的時間復(fù)雜度平均情況下:A[i]必須與已排好序的一半元素逐一比較,因此tj=j/2,則有例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析合并排序:將待排序元素分成大小大致相同的兩個子集合,然后分別將排好序的子集合合并成所要求的排好序的集合例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析合并排序:將待排序元素分成大小大致相同的兩個子集合,然后分別將排好序的子集合合并成所要求的排好序的集合假如n為2的冪次,遞歸算法要遞歸(log2n+1)層,每一層需要計算cn次,因此例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析插入排序與合并排序的比較最好情況下:插入排序的時間復(fù)雜性低于合并排序最壞和平均情況下:可以證明對于任意的a,b,c,d,總存在N使得當(dāng)n>N時,有an2+bn+c>dnlog2n+dn,即:合并排序的時間復(fù)雜性低于插入排序?qū)嵗嬎銠CA每秒執(zhí)行10億條指令,計算機B每秒執(zhí)行1千萬條指令.由A執(zhí)行插入排序,B執(zhí)行合并排序插入排序的T(n)簡化為c1n2,合并排序的T(n)簡化為c2nlog2n,并設(shè)c1=2,c2=50要排序100萬個數(shù),A機器需要2000秒,B機器大約需要100秒要排序1000萬個數(shù),A機器需要2.3天,B機器需要20分鐘隨著問題規(guī)模的增長,合并排序的相對優(yōu)勢更明顯例:插入排序和合并排序的復(fù)雜性分析課程介紹什么是算法算法的描述算法分析一般考察算法的最壞情況下的運行時間Tmax(n)是算法再任何輸入下的運行時間上界對于某些算法,最壞情況出現(xiàn)得相當(dāng)頻繁如在數(shù)據(jù)庫中檢索根本不存在的信息大致看來,

Tavg(n)通常與Tmax(n)一樣差知名學(xué)者課程介紹什么是算法算法的描述算法分析姚期智姚期智(AndrewChi-ChihYao),世界著名計算機學(xué)家,2000年圖靈獎得主,美國科學(xué)院院士,美國科學(xué)與藝術(shù)學(xué)院院士,中國科學(xué)院外籍院士,清華大學(xué)高等研究中心教授.1967年獲得臺灣大學(xué)物理學(xué)士學(xué)位,1972年獲得美國哈佛大學(xué)物理博士學(xué)位,1975年獲得美國伊利諾依大學(xué)計算機科學(xué)博士學(xué)位.1975年至1986年曾先后在美國麻省理工學(xué)院數(shù)學(xué)系、斯坦福大學(xué)計算機系、加利福尼亞大學(xué)伯克利分校計算機系任助教授、教授.1986年至2004年在普林斯頓大學(xué)計算機科學(xué)系擔(dān)任WiliamandEdnaMacaleer工程與應(yīng)用科學(xué)教授.2004年起在清華大學(xué)任全職教授.多年來,姚期智先生以其敏銳的科學(xué)思維,不斷向新的學(xué)術(shù)領(lǐng)域發(fā)起沖擊,在數(shù)據(jù)組織、基于復(fù)雜性、姚期智的偽隨機數(shù)生成理論、密碼學(xué)、通信復(fù)雜性乃至量子通信和計算等多個尖端科研領(lǐng)域，都做出了巨大而獨到的貢獻.他所發(fā)表的近百篇學(xué)術(shù)論文,幾乎覆蓋了計算復(fù)雜性的所有方面,并在獲圖靈獎之前,就已經(jīng)在不同的科研領(lǐng)域?qū)耀@殊榮,曾獲美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會喬治·波利亞獎和以算法設(shè)計大師克努特命名的首屆克努特獎,是計算機理論方面國際上最拔尖的學(xué)者.知名學(xué)者課程介紹什么是算法算法的描述算法分析陳國良陳國良任中國科學(xué)技術(shù)大學(xué)教授,博士生導(dǎo)師,現(xiàn)任中國科學(xué)技術(shù)大學(xué)軟件學(xué)院院長,國家高性能計算中心（合肥）主任,智能感知與圖像理解教育部重點實驗室（西安電子科技大學(xué)）學(xué)術(shù)委員會主任.中國計算機學(xué)會高性能計算專業(yè)委員會主任,享受國家政府特殊津貼.1973年起在中國科學(xué)技術(shù)大學(xué)任教.陳國良2003年當(dāng)選中國科學(xué)院院士,國家教育部高等學(xué)校計算機科學(xué)技術(shù)教學(xué)指導(dǎo)委員會副主任,全國首屆高等學(xué)校教學(xué)名師,安徽省計算機學(xué)會理事長,國際高性能計算（亞洲）常務(wù)理事.他是我國非數(shù)值并行算法研究的學(xué)科帶頭人,他圍繞著并行算法的教學(xué)與研究,逐漸形成了“算法理論－算法設(shè)計－算法實現(xiàn)－算法應(yīng)用”一套完整的并行算法學(xué)科體系,提出了“結(jié)構(gòu)－算法－編程”一體化的并行計算研究方法.他率先創(chuàng)建的我國第一個國家高性能計算中心是我國并行算法研究、環(huán)境科學(xué)與工程計算軟件等的科研與教學(xué)基地,在學(xué)術(shù)界和教育界有一定的影響和地位.知名學(xué)者課程介紹什么是算法算法的描述算法分析