算法1-算法求解基礎(chǔ)(新版)

算法設(shè)計與分析費寧課前簡介課程學(xué)時：48學(xué)時(40+8)平時成績考核辦法：隨堂點名和提問 作業(yè)和補充練習(xí)實驗報告和上機表現(xiàn)考試時間、方式18周（之前），閉卷答疑時間、地點周四上午第5小節(jié)，教2-120學(xué)習(xí)要求：適當(dāng)預(yù)習(xí)積極動手實現(xiàn)代碼上課聽講時在書上作適當(dāng)?shù)臉?biāo)記和注釋按時完成作業(yè)并復(fù)習(xí)《算法分析與設(shè)計》先修課程：

高級語言程序設(shè)計、面向?qū)ο蟪绦蛟O(shè)計、數(shù)據(jù)結(jié)構(gòu)“算法”與“數(shù)據(jù)結(jié)構(gòu)”的關(guān)系：算法是數(shù)據(jù)結(jié)構(gòu)的靈魂——不了解施加于數(shù)據(jù)上的算法就無法決定如何構(gòu)造數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)——算法的結(jié)構(gòu)和選擇常常在很大程度上依賴于數(shù)據(jù)結(jié)構(gòu)。算法+數(shù)據(jù)結(jié)構(gòu)=程序算法課程學(xué)習(xí)目標(biāo)Learningtosolverealproblemsthatarisefrequentlyincomputerapplication ——學(xué)習(xí)計算機應(yīng)用中求解實際問題的有效算法Learningthebasicprinciplesandtechniquesusedforansweringthequestion:“Howgood,or,howbadisthealgorithm” ——學(xué)習(xí)評價算法好/壞的基本原理和技巧Gettingtoknowagroupof“verydifficultproblems”categorizedas“NP-Complete”——學(xué)習(xí)NP-Complete問題的相關(guān)理論和算法了解各種算法——在遇到問題時能靈活的應(yīng)用所掌握的方法技巧；研究算法設(shè)計技術(shù)——當(dāng)沒有現(xiàn)成可用的算法時，能夠創(chuàng)造出問題的求解方法。前者很實際，后者很重要。Ch1算法問題求解基礎(chǔ)Ch2算法分析基礎(chǔ)（算法復(fù)雜度概念）算法設(shè)計策略、算法分析和證明:Ch5分治法Ch6貪心法Ch7動態(tài)規(guī)劃法Ch8回溯法Ch9分枝限界法Ch10NP完全問題Ch13密碼算法課程章節(jié)內(nèi)容課程參考書ClassicsDonaldE.Knuth.TheArtofComputerProgramming(TAOCP)Vol.1FundamentalAlgorithms——基本算法Vol.2SeminumericalAlgorithms——半數(shù)字化算法Vol.3SortingandSearching——排序與搜索PopulartextbooksThomasH.Cormen,etc.IntroductiontoAlgorithmsAlfredV.Aho,JohnE.Hopcroft,JeffreyD.Ullman.TheDesignandAnalysisofComputerAlgorithms(DACA)UdiManber.IntroductiontoAlgorithms-ACreativeApproachRobertSedgewick.AlgorithmsinC/C++/Java(withdifferentversionsusingdifferentprogramminglanguages)AdvancedmathematicaltechniquesGraham,Knuth,etc.ConcreteMathematics:AFoundationforComputerScience——具體數(shù)學(xué)（連續(xù)數(shù)學(xué)+離散數(shù)學(xué)）其他參考書

[1]王曉東.計算機算法設(shè)計與分析.電子工業(yè)出版社，2001. [2]JonBentley著，黃倩,錢麗艷譯，編程珠璣（第2版）.人民郵電出版社，2008. [3]盧開澄，計算機算法導(dǎo)引——設(shè)計與分析.清華大學(xué)出版社，1996. [4]JonKleinberg,EvaTardos著，張立昂，屈婉玲譯，算法設(shè)計.清華大學(xué)出版社，2007.網(wǎng)上學(xué)習(xí)資料

MIT

OpenCourseWareIntroductiontoAlgorithms

【課程推薦參考文獻：Miller,Bradley,andDavidRanum.

ProblemSolvingwithAlgorithmsandDataStructuresUsingPython.2nded.Franklin,Beedle&Associates,2011.】課件資料下載http://計算機學(xué)院軟件工程系算法分析與設(shè)計

選課密鑰：sf2015上機安排——B140501~04班分治策略——第7周周一（4月2日）第3~4節(jié)動態(tài)規(guī)劃法——第9周周一（5月7日）第3~4節(jié)回溯法——第11周周一（5月28日）第3~4節(jié)密碼算法——第13周周一（6月25日）第3~4節(jié)地點：教2-316（軟件與信息安全實驗室）每次算法實驗，選擇當(dāng)次算法的一個最有代表性的、最有趣的實例實現(xiàn)，并將該算法寫進實驗報告，同時提交實驗代碼。上機安排——B130412~14班分治策略——第5周周五（4月3日）第1~2節(jié)動態(tài)規(guī)劃法——第10周周五（5月8日）第8~9節(jié)回溯法——第13周周五（5月29日）第1~2節(jié)密碼算法——第17周周五（6月26日）第8~9節(jié)地點：教2-316（軟件與信息安全實驗室）每次算法實驗，選擇當(dāng)次算法的一個最有代表性的、最有趣的實例實現(xiàn)，并將該算法寫進實驗報告，同時提交實驗代碼。第1章算法問題求解基礎(chǔ)學(xué)習(xí)要點：理解算法的概念。理解程序與算法的區(qū)別和內(nèi)在聯(lián)系。章節(jié)內(nèi)容：1.1算法概述1.3算法設(shè)計與分析1.1算法概述Analgorithmisaprecisedescriptionoftheprocessofsolvingaproblem,consistingoffinitenumberofinstructionswhichcanbeexecutedmechanicallyandproduceadeterministicresult.——算法是對某個問題求解方案的完整而明確的描述，是指令的有限序列。算法的五個重要特征Finiteness——有窮性（算法必須總能在執(zhí)行有限步之后終止）Definiteness——確定性（組成算法的每一條指令都是清晰，無歧義的）Input——輸入（算法有零個或多個外部提供的輸入量）Output——輸出（算法至少產(chǎn)生一個輸出量）Effectiveness——可行性（算法的每一條指令必須足夠基本，能夠通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)）算法描述描述一個算法可以用自然語言、流程圖、偽代碼和程序設(shè)計語言。算法與程序

程序(Program)是算法用某種程序設(shè)計語言的具體實現(xiàn)。

算法必須可終止，程序卻沒有這一限制。 即：程序可以不滿足算法的性質(zhì)(5)—“有窮性”。

例如： 操作系統(tǒng)是一個在無限循環(huán)中執(zhí)行的程序，卻不是算法。因此操作系統(tǒng)是使用計算機語言描述的一個計算過程，而不是一個算法。經(jīng)典算法舉例

歐幾里德算法（輾轉(zhuǎn)相除法）：

求兩整數(shù)m和n的最大公約數(shù)(0≤m<n)

歐幾里德算法mnr①輸入m

和n；②求n除以m的余數(shù)r；③若r等于0，則m為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將m的值放在n中，將r的值放在m中；⑤重新執(zhí)行第②步。自然語言描述：N開始輸入m和nr=n%mr=0n=m；m=r

輸出m結(jié)束Y流程圖描述：偽代碼描述：1.r=n%m;2.循環(huán)直到r等于02.1n=m;2.2m=r;2.3r=n%m;3.輸出m;intRGcd(intm,intn)//歐幾里德遞歸算法{ if(m==0)returnn;//終止條件

returnRGcd(n%m,m);}尾遞歸intGcd(intm,intn){ if(m>n)Swap(m,n); returnRGcd(m,n);}程序1-1歐幾里德算法（遞歸）voidSwap(int&a,int

&b){ intc=a;a=b;b=c; }程序設(shè)計語言描述（遞歸）：程序1-2歐幾里德算法（迭代）voidSwap(int&a,int&b){ intc=a;a=b;b=c; }intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; if(m>n)Swap(m,n);

while(m>0) {intc=n%m; n=m;m=c; } returnn;}程序設(shè)計語言描述（迭代）：程序1-3連續(xù)整數(shù)檢測intGcd(intm,intn){ if(m==0)returnn; if(n==0)returnm; intt=m>n?n:m;

while(m%t||n%t)t--; returnt;}程序設(shè)計語言描述（連續(xù)整數(shù)檢測）：可見：一個問題可以設(shè)計不同的算法來求解。同一個算法可采用不同的形式來表示。小思考

若不事先比較m和n的大小，如何實現(xiàn)歐幾里德算法？intGcd(intm,intn){while(m!=0&&n!=0){

if(m>n)m%=n; elsen%=m;}returnm+n;}小思考

m*n/Gcd(m,n)如何求最小公倍數(shù)？Algorithmiseverywhere!ApplicationsHumanGenomeProject:e.g.determiningthesequencesofthe3billionchemicalbasepairsthatmakeuphumanDNAanddevelopingtoolsfordataanalysis.（卡普Karp->華盛頓）Internetservice:e.g.routingthedataElectroniccommerce:public-keycryptographyanddigitalsignaturesSystemsHardwareOperatingsystemsCompilers（克努特Knuth-LR(k)文法）假設(shè)某一負責(zé)人交給你一個很難的任務(wù)，幾天后詢問你問題解決了沒有?？赡軙l(fā)生如下圖這樣的情況：問：“交給你的問題，解決方案設(shè)計出來了嗎？”答：“我找不到一個有效的算法來解決它，沒能完成任務(wù)?！盫ariousproblemofalgorithm問：“交給你的問題，解決方案設(shè)計出來了嗎？”答：“我找不到一個有效的算法來解決它，因為這樣的算法是不存在的?！币C明一個問題不存在有效算法，往往跟尋找有效算法一樣難。問：“交給你的問題，解決方案設(shè)計出來了嗎？”答：“我找不到一個有效的算法來解決它，但不是我不行，因為所有這些名人也都找不到解決它的有效算法。”PhilosophyofproblemsolvingTodealwiththosewhichcan’tbesolved,wecompromise；Todealwiththosewhichcanbesolved,wetryourbest；Todistinguishbetweenthetwoclasses,weuseourwit.算法與圖靈獎

——超過1/3的Turing獎與算法有關(guān)1974-DonaldKnuth(Stanford):“TheArtofComputerProgramming”1976-MichaelRabin(Hebrew)&DanaScott(Oxford):NondeterministicFiniteStateAutomata(NDFSA)1982-StephenCook(Toronto):SatisfiabilityofPropositionCalculusisNP-complete1985-RichardKarp(UCBerkley):Branch-and-BoundMethod1986-JohnHopcroft(Cornell)&RobertTarjan(Princeton):Graphalgorithms1993-JurisHartmanis(Cornell)&RichardStearns(SUNYAlbany):ComputationalComplexityTheory1995-ManualBlum(UCBerkeley):Complexityofrecursivefunctionsanditsapplicationininformationsecurity2000-StephenYau(Princeton):Randomalgorithm,complexityofcommunication2002–RonaldRivest(MIT),AdiShamir(Weizmann),LeonardAdleman(USC):RSAalgorithm算法與圖靈獎

——超過1/3的Turing獎與算法有關(guān)有趣的算法問題背包問題1（物品可分割）：

有一旅行者要從n種物品中選取不超過b公斤重的行李隨身攜帶，要求總價值最大。 例：設(shè)背包的容量為50千克。物品1重10千克，價值60元；物品2重20千克，價值100元；物品3重30千克，價值120元。求總價值最大。背包問題2（物品不可分割）：①設(shè)有n=8個體積分別為54，45，43，29，23，21，14，1的物體和一個容積為C=110的背包，問選擇哪幾個物體裝入背包可以使其裝的最滿。②設(shè)有n=4個容積分別為9，5，12，8，價值分別為12，3，6，4的物體，和一個容積為C=18的背包，問選擇哪幾個物體裝入背包可以使其裝的最滿。有趣的算法問題約瑟夫環(huán)（Josephuscycle）

編號為1，2，3，……，n的n個人按順時針方向圍坐一圈。任選一個正整數(shù)作為報數(shù)上限m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列。從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直到最后圈中只剩下最后一個人（勝利者）。請設(shè)計程序輸出勝利者。

①一般解法：用鏈表實現(xiàn)②數(shù)學(xué)解法：voidmain(){

intn,m,i,s=0;

scanf("%d%d",&n,&m);

for(i=2;i<=n;i++)s=(s+m)%i;

printf("Thewinneris%d\n",s+1);

}有趣的算法問題皇后問題（回溯法經(jīng)典問題）

這是高斯1850年提出的一個著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在n×n格的棋盤上如何能擺上n個皇后而使她們都不能互相吃。 設(shè)n=4，試一試？

對于n=8現(xiàn)已知此問題共有92種解，但只有12種是獨立的，其余的都可以由這12種利用對稱性或旋轉(zhuǎn)而得到。 當(dāng)n很大時，問題很難。有趣的算法問題平面圖的四色猜想問題（近代三大數(shù)學(xué)難題之一,與費馬定理、哥德巴赫猜想并稱近代數(shù)學(xué)三大難題。

）

在1852年，由畢業(yè)于倫敦大學(xué)的弗南西斯-古德里（FrancisGuthrie)進行地圖著色時提出:一個平面圖是否用四種顏色就可使相鄰的區(qū)域顏色都不相同？——這是第一個主要由計算機證明的理論。1976年，KennethAppel與WolfgangHaken，美國伊利諾斯大學(xué)，兩臺計算機1200小時、100億次判斷。將地圖上的無限種可能情況減少為1476種狀態(tài)，由計算機挨個的進行檢查。并由不同的計算機和程序獨立的進行復(fù)檢。有趣的算法問題旅行售貨員問題（最小哈密頓回路，NPC問題） 設(shè)有n個城市（完全無向圖），已知任意兩城市間距離，現(xiàn)有一推銷員想從某一城市出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點，問如何找一條最短路徑。若距離矩陣為，求最短路徑。adbchefg有趣的算法問題

若對復(fù)雜的圖求解最小哈密頓回路：算法問題的求解過程(ProblemSolving)理解問題選擇算法設(shè)計策略（確定數(shù)據(jù)結(jié)構(gòu)）設(shè)計算法正確性證明分析算法編寫程序代碼1.3算法設(shè)計與分析1.3算法設(shè)計與分析如何設(shè)計算法——選擇算法設(shè)計策略 所求問題符合某種算法設(shè)計策略處理的問題特性。如何表示算法——描述算法 自然語言、流程圖、偽代碼、程序設(shè)計語言。本書中使用C/C++語言描述。如何確認算法——正確性證明 對于所有合法的輸入，能在有限時間內(nèi)輸出正確的結(jié)果，稱算法是正確的。確認一個算法是否正確的活動，稱為算法確認；（大多數(shù)情況下，人們通過程序測試和調(diào)試來排錯進行算法的正確性證明）使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明；（常用的算法正確性證明方法為數(shù)學(xué)歸納法。如：P9證明程序1-1的正確性）如何分析算法算法分析指對算法的執(zhí)行時間和所需空間的估算。設(shè)計出復(fù)雜性盡可能低的算法，或?qū)ΜF(xiàn)有的算法進行改進；（設(shè)計算法）從解決同一問題的多種算法中選出復(fù)雜性最低者。（選擇算法）程序1-1歐幾里德算法（遞歸）voidSwap(int&a,int

&b){ intc=a;a=b;b=c; }intGcd(intm,intn){ if(m>n)Swap(m,n); returnRGcd(m,n);}intRGcd(intm,intn)//歐幾里德遞歸算法{ if(m==0)returnn;//終止條件

returnRGcd(n%m,m);}如何設(shè)計算法——選擇算法設(shè)計策略 所求問題符合某種算法設(shè)計策略處理的問題特性。如何表示算法——描述算法 自然語言、流程圖、偽代碼、程序設(shè)計語言。本書中使用C/C++語言描述。如何確認算法——正確性證明 對于所有合法的輸入，能在有限時間內(nèi)輸出正確的結(jié)果，稱算法是正確的。確認一個算法是否正確的活動，稱為算法確認；（大多數(shù)情況下，人們通過程序測試和調(diào)試來排錯進行算法的正確性證明）使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明；（常用的算法正確性證明方法為數(shù)學(xué)歸納法。如：P9證明程序1-1的正確性）如何分析算法算法分析指對算法的執(zhí)行時間和所需空間的估算。設(shè)計出復(fù)雜性盡可能低的算法，或?qū)ΜF(xiàn)有的算法進行改進；（設(shè)計算法）從解決同一問題的多種算法中選出復(fù)雜性最低者。（選擇算法）1.3算法設(shè)計與分析那么，如何證明算法是不正確的？1.3.2如何設(shè)計算法使用計算機的問題求解策略主要指算法設(shè)計策略（algorithmdesignstrategy）。如果所求問題符合某種算法設(shè)計策略處理的問題特性，就可使用該算法設(shè)計策略設(shè)計算法、求解問題。比如，最小代價生成樹，符合貪心法求解問題的策略，就用貪心法設(shè)計策略設(shè)計算法；快速排序：分治法。1.3.3如何表示算法算法描述方法自然語言流程圖偽代碼程序設(shè)計語言本書使用C/C++語言描述1.3.4如何確認算法算法確認(algorithmvalidation):

確認一個算法是否正確的活動。算法證明(algorithmproof):

使用數(shù)學(xué)方法證明算法的正確性。程序測試(programtesting):

是指對程序模塊或程序總體，輸入事先準備好的樣本數(shù)據(jù)（稱為測試用例，testcase），檢查該程序的輸出，來發(fā)現(xiàn)程序存在的錯誤及判定程序是否滿足其設(shè)計要求的一項積極活動。1.3.5如何分析算法算法分析（algorithmanalysis）:是指對算法的執(zhí)行時間和所需空間的估算。程序的性能測量(performancemeasure-ment):在算法寫成程序后，便可使用樣本數(shù)據(jù)，實際測量一個程序所消耗的時間和空間。補充：數(shù)學(xué)歸納法（例1）證明：平面上任意條直線構(gòu)成的區(qū)域可以僅使用兩種顏色進行著色。證明：顯然，直線數(shù)目n=1時可以僅需兩種顏色進行著色。假設(shè)平面上小于n條直線構(gòu)成的區(qū)域能僅用兩種顏色來著色。那么考慮n條直線時的情況，在添加第n條直線后如何對原著色方案進行修改：根據(jù)區(qū)域位于第n條直線的哪一側(cè)，可以把這些區(qū)域分成兩組，保留其中一組區(qū)域的顏色，反轉(zhuǎn)另一組區(qū)域的顏色。如何證明該方案為有效著色？補充：數(shù)學(xué)歸納法（例1）證明：平面上任意條直線構(gòu)成的區(qū)域可以僅使用兩種顏色進行著色?，F(xiàn)證該方案為有效著色：考察兩個相鄰區(qū)域R1和R2。如果這兩個區(qū)域都在第n條直線的同側(cè)，那么根據(jù)歸納假設(shè)，它們在添上第n條直線之前顏色就不同。雖然它們可能需要改變著色，但無論如何它們的顏色仍然是不同的。如果這兩個區(qū)域的公共邊是第n條直線的一部分，那么在添上第n條直線前它們屬于同一區(qū)域。既然反轉(zhuǎn)了其中一個區(qū)域的顏色，那么現(xiàn)在它們的顏色一定不同。補充：數(shù)學(xué)歸納法（例2）證明下面猜想：下面三角形中第i行的和是i3。11=538=+971127=++1315191764=+++2927252123125=++++思路：要證明第i行的和是i3，只需證明第(i+1)行和第i行的差是(i+1)3-i3。補充：數(shù)學(xué)歸納法（例2）11=538=+971127=++1315191764=+++2927252123125=++++證明：由于這些數(shù)都是按序排列的奇數(shù)，且第i行有i個數(shù)。所以第(i+1)行第1個數(shù)和第i行第1個數(shù)相差2i。同樣，第2個數(shù)，第3個數(shù)，第4個數(shù)均是這樣......一共有i個差，每個差2i。另外，第(i+1)行末尾的最后一個數(shù)，不與上一行的任何一個數(shù)相匹配。因此，這兩行的差就是2i2加上第(i+1)行的最后一個數(shù)。因此僅需證明第(i+1)行的最后一個數(shù)值為(i+1)3-i3-2i2=i2+3i+1導(dǎo)出命題（將一個求和的問題規(guī)約成了求某一項的問題）補充：數(shù)學(xué)歸納法（例2）11=538=+971127=++1315191764=+++2927252123125=++++證明：上述命題對i=1時成立。則只要證明第（i+1）行的最后一個數(shù)和第i行的最后一個數(shù)之差等于[i2+3i+1]-[(i-1)2+3(i-1)+1]=2i+2即可。而我們已經(jīng)得到第(i+1)行和第i行的對應(yīng)項的差是2i。因此第(i+1)行最后一個數(shù)與第i行的最后一個數(shù)的差是2i+2，猜測成立，證明完成。證明嵌套的歸納假設(shè)：第（i+1）行的最后一個數(shù)是i2+3i+1。補充：數(shù)學(xué)歸納法（例3）證明（歐拉公式）：任意一張連通平面圖的節(jié)點數(shù)(V)、邊數(shù)(E)和面數(shù)(F)的關(guān)系可由公式V+F=E+2表示。又如：上圖包含11個節(jié)點、19條邊和10個面。如：正方形包含4個節(jié)點、4條邊和2個面。補充：數(shù)學(xué)歸納法（例3）證明（歐拉公式）：任意一張連通平面圖的節(jié)點數(shù)(V)、邊數(shù)(E)和面數(shù)(F)的關(guān)系可由公式V+F=E+2表示。證明：■首先考察只有一個面的圖。這樣的圖不包含回路，否則，回路至少構(gòu)成一個面，回路以外構(gòu)成另一個面。這種連通無回路的圖被稱為樹，現(xiàn)證明對任意樹V+1=E+2成立：（也即只需證明：有V個頂點的樹有V-1條邊即可。）證明：顯然，有1個頂點的樹有0條邊。假設(shè)有n個頂點的樹有n-1條邊成立，則考察有n+1個節(jié)點的樹：至少存在一個節(jié)點，與樹中其他節(jié)點間只有一條邊相連。（否則若所有節(jié)點都與至少2條邊相連，則一定會有回路存在，與樹的定義矛盾。）將該節(jié)點連同與之相連的一條邊從樹上移走，得到的圖仍是一棵樹（只不過少了一個節(jié)點和一條邊）。根據(jù)歸納假設(shè)條件此時滿足V