算法分析初學(xué)了解.ppt

1、Introduction to Algorithms,授課教師：宋玲 E-Mail: song_ 手機：山東建筑大學(xué)計算機學(xué)院(2014年3月),本課程的教學(xué)目的及要求(1/2),分析算法的漸進效率；掌握最壞，平均及最好情況下復(fù)雜性的分析； 敘述分治法的模式和解釋當(dāng)什么情況算法設(shè)計會需要它，練習(xí)使用此模式的算法，實現(xiàn)并推導(dǎo)出分治法的遞歸描述； 敘述動態(tài)規(guī)劃的模式和解釋當(dāng)什么情況算法設(shè)計會需要它，練習(xí)使用此模式的算，實現(xiàn)并分析動態(tài)規(guī)劃算法。,敘述貪心算法的模式和解釋當(dāng)什么情況算法設(shè)計會需要它，練習(xí)使用此模式的算法，實現(xiàn)并分析貪心算法； 實現(xiàn)圖論算法和使用圖論計算為關(guān)鍵的

2、算法，分析它們，以及如何使用圖來模擬工程問題；,本課程的教學(xué)目的及要求(2/2),一定要擁有一本教材！,教材的重要性,教材內(nèi)容： 第一部分（Part I） 基礎(chǔ)（Foundations）第一章 計算中算法的角色（The Role of Algorithms in Computing）第二章 開始（Getting Started）第三章 函數(shù)的增長率（Growth of Functions）第四章 遞歸（Recurrences）第五章 概率分析與隨機化算法（Probabilistic Analysis and Randomized Algorithms）第二部分（Part II） 排序與順序統(tǒng)計

3、（Sorting and Order Statistics）第六章 堆排序（Heapsort）第七章 快速排序（Quicksort）第八章 線性時間中的排序（Sorting in Linear Time）第九章 中值與順序統(tǒng)計（Medians and Order Statistics）,第三部分（Part III） 數(shù)據(jù)結(jié)構(gòu)（Data Structures）第十章 基本的數(shù)據(jù)結(jié)構(gòu)（Elementary Data Structures）第十一章 散列表（Hash Tables）第十二章 二叉查找樹（Binary Search Trees）第十三章 紅-黑樹（Red-Black Trees）第十四

4、章 擴充的數(shù)據(jù)結(jié)構(gòu)（Augmenting Data Structures）第四部分（Part IV） 高級的設(shè)計與分析技術(shù)（Advanced Design and Analysis Techniques）第十五章 動態(tài)規(guī)劃（Dynamic Programming）第十六章 貪婪算法（Greedy Algorithms）第十七章 分攤分析（Amortized Analysis）,第五部分（Part V） 高級的數(shù)據(jù)結(jié)構(gòu)（Advanced Data Structures）第十八章 B-樹（B-Trees）第十九章 二項式堆（Binomial Heaps）第二十章 斐波納契堆（Fibonacci H

5、eaps）第二十一章 不相交集的數(shù)據(jù)結(jié)構(gòu)（Data Structures for Disjoint Sets）第六部分（Part VI） 圖算法（Graph Algorithms）第二十二章 基本的圖算法（Elementary Graph Algorithms）第二十三章 最小生成樹（Minimum Spanning Trees）第二十四章 單源最短路徑（Single-Source Shortest Paths）第二十五章 全對的最短路徑（All-Pairs Shortest Paths）第二十六章 最大流（Maximum Flow）第七部分（Part VII） 精選的主題（Selected

6、Topics）第二十七章 排序網(wǎng)絡(luò)（Sorting Networks）,本課程的難點和學(xué)習(xí)方法,雙語學(xué)習(xí) 較多的數(shù)學(xué)知識和推倒(第一部分) 預(yù)習(xí)-上課認真聽講-復(fù)習(xí)（重點詞匯） 預(yù)備的數(shù)學(xué)知識(p51-57) 本次課和下節(jié)課所講重點內(nèi)容在教材上劃出。,教材 Introduction to Algorithms(Second Edition)，（美）Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein，高等教育出版社 參考教材 1、算法設(shè)計與分析 王曉東 清華大學(xué)出版社 2、算法分析與設(shè)計 （美）Michael T.

7、 Goodrich Roberto Tamassia 著人民郵電出版社 3、算法設(shè)計技巧與分析（沙特） M.H. Alsuwaiyel 著 電子工業(yè)出版社 4、算法設(shè)計與分析 鄭宗漢 清華大學(xué)出版社 5、算法導(dǎo)論， Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein著， 潘金貴等譯， 機械工業(yè)出版社,教輔用書,在學(xué)期中將會指定多次作業(yè)。要求同學(xué)上交并給出成績，作為部分期末成績。 作業(yè)的目的是讓同學(xué)有練習(xí)掌握課堂內(nèi)容的機會。因此，鼓勵同學(xué)們合作解題。 在上課過程中鼓勵課上大膽討論，根據(jù)表現(xiàn)記入平時成績。,作業(yè)和討論

8、,當(dāng)被指定“用一個算法”來解決某個問題。應(yīng)該提供以下部分： 1. 算法的描述：偽代碼(pseudocode)。2. 最少以一個工作例子或圖表來更明確的顯示你的算法是怎樣工作的。3. 算法正確性的一個證明（或表示）（*）。4. 算法執(zhí)行時間的分析。,作業(yè)以及實驗報告中算法描述要求,相關(guān)事項,教學(xué)方式：理論(32學(xué)時)，實踐(16學(xué)時) 最終的評分會基于作業(yè)、平時表現(xiàn)、實驗報告和期末考 先修課程：離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)值分析C語言程序設(shè)計 作業(yè)：每個部分交一次 答疑時間：周四下午2：30 答疑地點：XX305,Grading policy:,Homework: 8% Experiment Run Re

9、sults: 8% Experiment Paper: 8% Arrival: 6% Final Exam: 70%,古城哥尼斯堡，景致迷人，碧波蕩漾的普瑞格爾河橫貫其境。普瑞格爾河的兩岸及河中的兩個美麗的小島，由七座橋連接組成了這座秀色怡人的城市（如圖）。市民們喜歡四處散步，于是便產(chǎn)生這樣的問題：是否可以設(shè)計一種方案，使得人們從自己家里出發(fā)，經(jīng)過每座橋恰好一次，最后回到家里。這便是著名的“哥尼斯堡七橋問題”。熱衷于這個有趣的問題的人們試圖解決它，但一段時間內(nèi)竟然沒有人能給出答案。后來，問題傳到了著名數(shù)學(xué)家歐拉那里，居然也激起了他的興趣。他從人們尋求路線屢遭失敗的教訓(xùn)中敏銳地領(lǐng)悟到，也許這樣的

10、方案根本就不存在。歐拉經(jīng)過悉心的研究，1736年，年方29歲的歐拉終于解決了這個問題，并向圣彼得堡科學(xué)院遞交了一份題為哥尼斯堡的七座橋的論文。論文不僅僅是解決了這一難題，而且引發(fā)了一門新的數(shù)學(xué)分支圖論的誕生。,應(yīng)用與科學(xué)問題的發(fā)現(xiàn)與求解,七橋問題,18世紀(jì)的七橋問題穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。 Euler1736年證明了不可能存在這樣的路線。,Euler 定理,Knigsberg橋?qū)?yīng)的圖,定義（歐拉圖） 通過無向連通圖G的每條邊一次且僅有一次的回路稱為歐拉回路。具有歐拉回路的圖為歐拉圖。 定義包含多重圖在內(nèi)，即歐拉回路中允許頂點重復(fù)出現(xiàn)。,歐拉圖, 定理

11、 G是無向連通圖，則G是歐拉圖G中所有頂點度數(shù)都是偶數(shù)。 定義 如果無向連通圖G的每條邊一次且僅一次的通路稱為圖G的歐拉通路。 定理 具有一條連接頂點vi和vJ的歐拉通路的充分條件是vi和vJ是G中僅有的具有奇數(shù)度的頂點。,圖一 “棋盤騎士問題”的一個解法,哈密頓圖,哈密頓圖,一. 哈密頓道路問題： 年發(fā)明的一種游戲。 在一個實心的正十二面體，20個頂點標(biāo)上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。 這就是“繞行世界”問題。即找一條經(jīng)過所有頂點（城市）的基本道路（回路）。,THE ICOSIAN GAME,哈密頓圖,定義 通過圖G的每個頂點一次且僅一次的回路

12、稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖。哈密頓通路是通過圖G的每個頂點一次且僅一次的通路。 注： 歐拉道路未必是哈密頓道路，因為歐拉道路可以經(jīng)過同一頂點多次。 哈密頓道路未必是歐拉道路，因為哈密頓道路不一定要經(jīng)過中所有的邊。,哈密頓圖,貨郎擔(dān)問題,一個貨郎要去若干城鎮(zhèn)賣貨，然后回到出發(fā)地，給定各城鎮(zhèn)之間所需的旅行時間后，應(yīng)怎樣計劃他的路線，使他能去每個城鎮(zhèn)恰好一次而且總時間最短？ 實質(zhì)：無向加權(quán)圖，尋找最短的回路的問題。,貨郎擔(dān)問題,德國人很喜歡精確的數(shù)學(xué)，在1978年，波恩大學(xué)有一位數(shù)學(xué)家想要知道在西德的120個有鐵路穿過的城市要安排一個最短路程的回路，應(yīng)該怎么樣跑。他從鐵路局找到了

13、準(zhǔn)確的城市間鐵路的長度，整個問題變成一個有7140個變數(shù)，120個方程及96個不等式的線性規(guī)劃問題，用電子計算機去算得到最短的回路是6942公里。,貨郎擔(dān)問題,用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，找出一個具有最小權(quán)的Hamilton 圈（包含圖G的每個頂點的圈)。 這個問題目前還沒有有效的算法。 30！=265,252, 859,812,191,058,636 308,480,000,000 有興趣的同學(xué)編程序?qū)崿F(xiàn)，看你能解決多大規(guī)模的問題。,四色問題,著名的世界難題“四色猜想” ：一張地圖，用一種顏色對一個地區(qū)著色，那么一共只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同。,四色問題,18

14、52年，剛從倫敦大學(xué)畢業(yè)的Francis Guthrie提出了四色猜想。 1878年著名的英國數(shù)學(xué)家Cayley向數(shù)學(xué)界征求解答。 此后數(shù)學(xué)家 Heawood 花費了畢生的精力致力于四色研究，于1890年證明了五色定理（每個平面圖都是5頂點可著色的）。 直到1976年6月，美國數(shù)學(xué)家 K. Appel與 W. Haken，在3臺不同的電子計算機上，用了1200小時，才終于完成了“四色猜想”的證明，從而使四色猜想成為了四色定理。,棋盤覆蓋,在一個2k2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨

15、牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。,Longest Common Subsequence (LCS),Application: comparison of two DNA strings Ex: X= A B C B D A B , Y= B D C A B A Longest Common Subsequence: X = A B C B D A B Y = B D C A B A Brute force algorithm would compare each subsequence of X with the symbols in Y,Fra

16、ctional knapsack problem?,1 The Role of Algorithms in Computing,1 what are algorithms? 2 why is the study of algorithms worthwhile? 3 what is the role of algorithms?,An algorithm is said to be correct if, for every input instance, it halts with the correct output,The problem of sorting,Input: sequen

17、ce of numbers. Output: permutation such that a 1 a 2 a n . Example: 解釋什么是實例？ Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,Time Is Important,“Time is important for everybody, especially for the computer scientist who studies algorithms.” J. S. Yu,What kinds of problems are solved by algorithms? Levels of H

18、ardness 1. There is no method to solve the problem in finitely many steps. 2. Theoretically, there is an algorithm, but the running time increases too much with the size of input, even to the universe age（NPC problems）. 3. Among the good algorithms, there is still a hierarchy of running time.,多項式算法：

19、把漸近復(fù)雜性與規(guī)模N的冪同階的這類算法稱為多項式算法。 指數(shù)型算法：把漸近復(fù)雜性與規(guī)模N的指數(shù)同階的這類算法稱為指數(shù)型算法。 這兩種算法在效率上有質(zhì)的區(qū)別的內(nèi)在原因是算法漸近復(fù)雜性的階的區(qū)別?？梢?，算法的漸近復(fù)雜性的階對于算法的效率有著決定性的意義。 多項式算法是有效的算法。很多問題都有多項式算法。但也有一些問題還未找到多項式算法，只找到指數(shù)型算法。,Homework,思考題：1.1-3,1.2 Algorithms as a technology,Suppose computers were infinitely fast and computer memory was free. Woul

20、d you have any reason to study algorithms? Compare the running time of insert sort and merge sort(P11).,let us pit a faster computer (computer A) running insertion sort against a slower computer (computer B) running merge sort.,Efficiency,Why study algorithms andperformance?, Algorithms help us to u

21、nderstand scalability. Performance often draws the line between what is feasible and what is impossible. Algorithmic mathematics provides a language for talking about program behavior., Performance is the currency of computing. The lessons of program performance generalize to other computing resourc

22、es. Speed is fun!,2 Getting Started,Analysis of Algorithms Insertion Sort Merge Sort,The problem of sorting,Input: sequence of numbers. Output: permutation such that a 1 a 2 a n . Example: Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij

23、= i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,10,40,20,1,2,3,4,i = j = key = Aj = Aj+1 = ,An Example: Insertion Sort,InsertionSort(A, n) for i =

24、2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,10,40,20,1,2,3,4,i = 2j = 1key = 10Aj = 30 Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j =

25、1key = 10Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 1key = 10Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;wh

26、ile (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 0key = 10Aj = Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,30,30,40,20,1,2,3,4,i = 2j = 0key = 10Aj = Aj+1 = 30,An Exa

27、mple: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 2j = 0key = 10Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj =

28、j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 10Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 40Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A

29、, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 0key = 40Aj = Aj+1 = 10,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4

30、,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij

31、= i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 3j = 2key = 40Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 2key = 40Aj = 30

32、Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj

33、 key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 20,An Example: Inser

34、tion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,20,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 20,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+

35、1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A,

36、n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 3key = 20Aj = 40 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,

37、4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,40,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 40,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij

38、 = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 2key = 20Aj = 30 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 2key = 20Aj = 30

39、 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (A

40、j key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,30,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 30,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,20,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 20,An Example: Insertion Sort,InsertionSort(A, n) for i = 2 to n key = Aij = i - 1;while (j 0) and (Aj key) Aj+1 = Ajj = j - 1Aj+1 = key ,10,20,30,40,1,2,3,4,i = 4j = 1key = 20Aj = 10 Aj+1 = 20,Done!,Animating Insertion Sort,Try i