計算機算法設(shè)計與分析（第4版）王曉東編著電子工業(yè)出版社周德華tzhoudh@教學(xué)支配1.課時支配講授課（含探討課第5周后）3×16=48學(xué)時1-16周試驗課（周三）2×9=18學(xué)時1-16周總復(fù)習(xí)及答疑17-18周2.成果總評期末考試60％平常成果40％點名及課堂表現(xiàn)(10%)平常作業(yè)及探討(15%)試驗及報告（15%）3.前導(dǎo)課程C/C++程序設(shè)計數(shù)據(jù)結(jié)構(gòu)教學(xué)支配3.習(xí)題探討課本學(xué)期內(nèi)任選一道習(xí)題或試驗題講解自己的算法，要求：主動報講解題號（至少提前一周）講主要思路和創(chuàng)新點有ppt5分鐘以內(nèi)多人講同一道題留意突出與別人的差別講完后相關(guān)文檔、程序或demo提交服務(wù)器算法在計算機科學(xué)中的地位Computerscienceisthestudyofalgorithms,including:1.Theirformalandmathematicalproperties2.Theirhardwarerealizations3.Theirlinguisticrealizations4.TheirapplicationsGibbs,N.E.,andTucker,A.B.“AModelCurriculumforaLiberalArtsDegreeinComputerScience,”Comm.oftheACM,vol.29,no.3(March1986).課程目標(biāo)和內(nèi)容設(shè)計算法表示算法分析算法實現(xiàn)算法測試算法確認(rèn)算法駕馭算法困難性和常用算法的基本理論學(xué)問駕馭算法分析和設(shè)計的基本方法熬煉邏輯思維實力，培育運用算法理論解決實際問題的實力課程目標(biāo)和內(nèi)容算法概述遞歸與分治策略動態(tài)規(guī)劃貪心算法回溯法分支限界法隨機化算法8.近似算法課程參考書目《算法設(shè)計與分析》（第2版）王曉東編著清華高校出版社（Java描述）《算法導(dǎo)論》（第2版）ThomasH.Cormer,CharlesE.Leiserson等著潘金貴顧鐵成等譯機械工業(yè)出版社第1章算法概述學(xué)習(xí)要點:理解算法的概念。理解什么是程序，程序與算法的區(qū)分和內(nèi)在聯(lián)系。駕馭算法的計算困難性概念。駕馭算法漸近困難性的數(shù)學(xué)表述。駕馭用C++語言描述算法的方法。了解NP類問題的基本概念。第1章算法概述1.1基本概念1.2算法困難性分析1.3用c++描述算法1.4算法分析方法1.5NP完全性理論1.1基本概念--算法(Algorithm)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入：有外部供應(yīng)的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。1.1基本概念--程序(Program)程序是算法用某種程序設(shè)計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)。例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統(tǒng)的各種任務(wù)可看成是單獨的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。該子程序得到輸出結(jié)果后便終止。Algorithm+DataStructure=Program--NikiklausWirth1.1基本概念--問題求解(ProblemSolving)證明正確性分析算法設(shè)計程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計策略設(shè)計算法1.2算法困難性分析算法困難性=算法所須要的計算機資源算法的時間困難性T(n)；算法的空間困難性S(n)。其中n是問題的規(guī)模（輸入大?。?。1.2.1算法的時間困難性（1）最壞狀況下的時間困難性Tmax(n)=max{T(I)|size(I)=n}（2）最好狀況下的時間困難性Tmin(n)=min{T(I)|size(I)=n}（3）平均狀況下的時間困難性Tavg(n)=其中I是問題的規(guī)模為n的實例，p(I)是實例I出現(xiàn)的概率。算法漸近困難性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近困難性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項留下的主項。它比T(n)簡潔。漸近分析的記號在下面的探討中，對全部n，f(n)0，g(n)0。（1）漸近上界記號OO(g(n))={f(n)|存在正常數(shù)c和n0使得對全部nn0有：0f(n)cg(n)}比如：3N+10=O(N),4N2+3N-1=O(N2),logN=O(N)（2）漸近下界記號(g(n))={f(n)|存在正常數(shù)c和n0使得對全部nn0有：0cg(n)f(n)}比如：3N+10=(1),4N2+3N-1=(N2),NlogN=(logN)（3）非緊上界記號oo(g(n))={f(n)|對于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對全部nn0有：0f(n)<cg(n)}等價于f(n)/g(n)0，asn。比如：3N+1000=o(N2),NlogN=o(N2)（4）非緊下界記號(g(n))={f(n)|對于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對全部nn0有：0cg(n)<f(n)}等價于f(n)/g(n)，asn。f(n)(g(n))g(n)o(f(n))比如：4N2+3N-1=(N),N!=(N2)（5）緊漸近界記號(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對全部nn0有：c1g(n)f(n)c2g(n)}比如：4N2+3N-1=(N2),logN2+2=(logN)定理1：(g(n))=O(g(n))(g(n))f(n)=(g(n))的準(zhǔn)確意義是：f(n)(g(n))。一般狀況下，等式和不等式中的漸近記號(g(n))表示(g(n))中的某個函數(shù)。例如：2n2+3n+1=2n2+(n)表示2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某個函數(shù)。等式和不等式中漸近記號O,o,和的意義是類似的。漸近分析記號在等式和不等式中的意義漸近分析中函數(shù)比較f(n)=O(g(n))ab;f(n)=(g(n))ab;f(n)=(g(n))a=b;f(n)=o(g(n))a<b;f(n)=(g(n))a>b.漸近分析記號的若干性質(zhì)（1）傳遞性：f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；f(n)=o(g(n))，g(n)=o(h(n))

f(n)=o(h(n))；f(n)=(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；（2）反身性：f(n)=(f(n))；f(n)=O(f(n))；f(n)=(f(n)).（3）對稱性：f(n)=(g(n))

g(n)=(f(n)).（4）互對稱性：f(n)=O(g(n))

g(n)=(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；（5）算術(shù)運算：O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=

O(f(n))。規(guī)則O(f(n))+O(g(n))=O(max{f(n),g(n)})的證明：對于隨意f1(n)O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對全部nn1，有f1(n)c1f(n)。類似地，對于隨意g1(n)O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對全部nn2，有g(shù)1(n)c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對全部的nn3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n))c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).1.2.3算法漸近困難性分析中常用函數(shù)（1）單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)f(n);單調(diào)遞減：m

n

f(m)f(n);嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n);嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n).（2）取整函數(shù)x：不大于x的最大整數(shù)；x：不小于x的最小整數(shù)。取整函數(shù)的若干性質(zhì)

x-1<xxx<x+1；

n/2

+n/2=n;

對于n

0，a,b>0，有：

n/a/b=n/ab;n/a/b=n/ab;a/b(a+(b-1))/b;a/b(a-(b-1))/b;

f(x)=x,g(x)=x為單調(diào)遞增函數(shù)。（3）多項式函數(shù)

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=(nd);

f(n)=O(nk)f(n)多項式有界；f(n)=O(1)

f(n)

c;

kdp(n)=O(nk);kdp(n)=(nk);k>

dp(n)=o(nk);k<dp(n)=(nk).（4）指數(shù)函數(shù)對于正整數(shù)m,n和實數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1an為單調(diào)遞增函數(shù);a>1nb=o(an)ex

1+x;|x|11+xex

1+x+x2;

ex

=1+x+(x2),asx0;（5）對數(shù)函數(shù)logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);fora>0,b>0,c>0|x|1forx>-1,foranya>0,

logbn=o(na)（6）階乘函數(shù)1.2.4算法分析中常見的困難性函數(shù)小規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)1.3用c++描述算法（1）選擇語句：（1.1)if語句：（1.2)？語句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等價于：

if(x>9)y=100;elsey=200;switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}（1.3)switch語句：（2）迭代語句：（2.1)for循環(huán)：for(init;condition;inc)statement;（2.2)while循環(huán)：while(condition)statement;（2.3)do-while循環(huán)：

do{statement;}while(condition);（3）跳轉(zhuǎn)語句：（3.1)return語句：returnexpression;（3.2)goto語句：

gotolabel;

label:（4）函數(shù)：return-typefunctionname(para-list){bodyofthefunction}intmax(intx,inty){returnx>y?x:y;}template<classType>Typemax(Typex,Typey){returnx>y?x:y;}inti=max(1,2)；doublex=max(1.0,2.0)；（5）模板template

：（6）動態(tài)存儲安排（6.1）運算符new運算符new用于動態(tài)存儲安排。new返回一個指向所安排空間的指針。例：intx；y=newint；y=10；也可將上述各語句作適當(dāng)合并如下：inty=newint；y=10；或inty=newint(10)；或inty；y=newint(10)；（6.2）一維數(shù)組為了在運行時創(chuàng)建一個大小可動態(tài)變更的一維浮點數(shù)組x，可先將x聲明為一個float類型的指針。然后用new為數(shù)組動態(tài)地安排存儲空間。例：floatx=newfloat[n]；創(chuàng)建一個大小為n的一維浮點數(shù)組。運算符new安排n個浮點數(shù)所需的空間，并返回指向第一個浮點數(shù)的指針。然后可用x[0]，x[1]，…，x[n-1]來訪問每個數(shù)組元素。（6.3）運算符delete當(dāng)動態(tài)安排的存儲空間已不再須要時應(yīng)剛好釋放所占用的空間。用運算符delete來釋放由new安排的空間。例：deletey；delete[]x；分別釋放安排給y的空間和安排給一維數(shù)組x的空間。（6.4）動態(tài)二維數(shù)組創(chuàng)建類型為Type的動態(tài)工作數(shù)組，這個數(shù)組有rows行和cols列。template<classType>voidMake2DArray(Type**&x,introws,intcols){x=newType*[rows];for(inti=0;i<rows;i++)x[i]=newType[cols];}當(dāng)不再須要一個動態(tài)安排的二維數(shù)組時，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所安排的空間。然后釋放為行指針安排的空間。釋放空間后將x置為0，以防接著訪問已被釋放的空間。template<classType>void

Delete2DArray(Type**&x,introws){for(inti=0;i<rows;i++)delete[]x[i];delete[]x;x=0;}1.4算法分析方法例：依次搜尋算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}（1）Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）在平均狀況下，假設(shè)：(a)搜尋成功的概率為p(0p1)；(b)在數(shù)組的每個位置i(0i<n)搜尋成功的概率相同，均為p/n。1.4算法分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計算時間*全部循環(huán)次數(shù)；（3）依次語句各語句計算時間相加；（4）if-else語句if語句計算時間和else語句計算時間的較大者。template<classType>voidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}在最好狀況下，ti=1,for1i<n;在最壞狀況下，tii+1,for1i<n;對于輸入數(shù)據(jù)a[i]=n-i(逆序),i=0,1,…,n-1，算法insertion_sort達(dá)到其最壞情形。因此，由此可見，Tmax(n)=(n2)最優(yōu)算法問題的計算時間下界為(f(n))，則計算時間困難性為O(f(n))的算法是最優(yōu)算法。例如，排序問題的計算時間下界為(nlogn)，計算時間困難性為O(nlogn)的排序算法是最優(yōu)算法。堆排序算法是最優(yōu)算法。遞歸算法困難性分析intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}遞歸的蒙娜麗莎1.5.1 P類與NP類問題易處理的問題:可由多項式時間算法求解的問題難處理的問題:須要超多項式時間才能求解的問題不行解問題：任何計算機無論耗費多少時間也不能解決的問題例如：“圖靈停機問題”“Keyboardnotfound...pressF1tocontinue”有很多問題，從表面上看似乎并不比排序或圖的搜尋等問題更困難，然而至今人們還沒有找到解決這些問題的多項式時間算法，也沒有人能夠證明這些問題須要超多項式時間下界。在圖靈機計算模型下，這類問題的計算困難性至今未知。1.5NP完全性理論圖靈機1.5NP完全性理論圖靈機M的時間困難性T(n)是它處理全部長度為n的輸入所需的最大計算步數(shù)。假如對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。圖靈停機問題(TheHaltingProblem)存在一些不行解問題：圖靈停機問題(TheHaltingProblem)圖靈機停機問題的不行判定性:能否給出一個推斷隨意一個圖靈機是否停機的一般方法?答案是NO.這個問題事實上是問:是否存在一臺"萬能的"圖靈機H,把隨意一臺圖靈機M輸入給H,它都能判定M最終是否停機,輸出一個明確的"yes"或"no"的答案?可以利用反證法來證明這樣的H不行能存在.假定存在一個能夠判定隨意一臺圖靈機是否停機的萬能圖靈機H(M),假如M最終停機,H輸出"halt";假如M不停機,H輸出"loop".我們把H當(dāng)作子程序,構(gòu)造如下程序P:functionP(M){if(H(M)=="loop")return"halt";elseif(H(M)=="halt")while(true);//loopforever}因為P本身也是一臺圖靈機,所以我們可以把P輸入給它自己,然后問P(P)是否停機.依據(jù)程序P的流程,假如P不停機無限循環(huán),那么它就停機,輸出"halt";假如P停機,那么它就無限循環(huán),不停機;這樣無論如何我們都將得到一個沖突,所以假設(shè)前提不成立,即不存在這樣的H.或者說,圖靈機停機問題是不行判定的(undecidable).圖靈停機問題(TheHaltingProblem)另外還有兩個本質(zhì)上相像的悖論：理發(fā)師悖論：村子里有個理發(fā)師，這個理發(fā)師有條原則是，對于村里全部人，當(dāng)且僅當(dāng)這個人不自己理發(fā)，理發(fā)師就給這個人理發(fā)。假如這個人自己理發(fā)，理發(fā)師就不給這個人理發(fā)。無法回答的問題是，理發(fā)師給自己理發(fā)么？停機測試悖論：計算機里有個測試程序，這個測試程序的原則是，對于計算機里全部程序，當(dāng)且僅當(dāng)這個程序不遞歸調(diào)用自己(輸出停機)，測試程序就調(diào)用它(對應(yīng)不停機)。假如這個程序遞歸調(diào)用自己（對應(yīng)不停機），測試程序就不調(diào)用它（對應(yīng)停機）。無法回答的問題是，測試程序遞歸調(diào)用自己么？圖靈停機問題(TheHaltingProblem)1.5.1 P類與NP類問題非確定性問題：有些問題的答案無法干脆計算得到，只能通過間接的“猜算”來得到結(jié)果。而這些問題的通常有個算法，它不能干脆告知你答案是什么，但可以告知你，某個可能的結(jié)果是正確的答案還是錯誤的。這個可以告知你“猜算”的答案正確與否的算法，假如可以在多項式時間內(nèi)算出來，就叫做多項式非確定性問題。而假如這個問題的全部可能答案，都是可以在多項式時間內(nèi)進(jìn)行正確與否的驗算的話，就叫完全多項式非確定問題。旅行售貨員問題

（TravelingSalesmanProblem

）最優(yōu)化形式的TSP問題：

判定形式的TSP問題：對于給定的帶權(quán)圖G=(V,E)的一個正數(shù)d，要求判定圖G中是否存在總費用不超過d的周游路途。101234302065410設(shè)G=(V,E)是一個帶權(quán)圖。圖中各邊的費用（權(quán)）為正數(shù)。圖的一條周游路途是包括V中的每個頂點在內(nèi)的一條回路。TSP要求在圖G中找出費用最小的周游路途。——較難——較易P類問題：可以在多項式時間內(nèi)求解的判定問題。確定性計算模型下的易解問題類。非確定性算法：將問題求解分為揣測和驗證兩個階段。揣測：給出問題的一個揣測—非確定性驗證：驗證揣測階段給出解的正確性—確定性NP類問題：非確定性多項式時間可解的判定問題。非確定性計算模型下的易驗證問題類。非確定性圖靈機計算模型NDTM(NondeterministicTuringMachine)：在NDTM模型下，很多問題可以在多項式時間內(nèi)求解—NP問題(NondeterministicPolynomial)1.5.1P類與NP類問題P\NP\NPC\NP-Hard關(guān)系P：可以在多項式時間解決的問題NP：目前沒有多項式時間解決的算法，但是假如給出一個候選答案，可以在多項式時間里驗證這個答案是不是正確的。NPC：滿足兩特性質(zhì)：1.可在多項式時間驗證候選答案（是NP問題）；2.任何一個NP問題可在多項式時間內(nèi)規(guī)約到該問題。NP-Hard：任何一個NP問題可在多項式時間內(nèi)規(guī)約到該問題，但無法證明問題本身是NP問題。NP-Hard至少和NP問題一樣難。1.5.2 NP完全問題（NPC）PNP。直觀上看，P類問題是確定性計算模型下的易解問題類，而NP類問題是非確定性計算模型下的易驗證問題類。大多數(shù)的計算機科學(xué)家認(rèn)為NP類中包含了不屬于P類的語言，即P≠NP。NP完全問題有一種令人驚異的性質(zhì)，即假如一個NP完全問題能在多項式時間內(nèi)得到解決，那么NP中的每一個問題都可以在多項式時間內(nèi)求解，即P=NP。目前還沒有一個NP完全問題有多項式時間算法。邏輯電路問題--給定一個邏輯電路，問是否存在一種輸入使輸出為True。一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和導(dǎo)線組成。1.5.3一些典型的NP完全問題存在輸出不行能為True的邏輯電路：1.5.3一些典型的NP完全問題邏輯電路問題明顯屬于NP問題，并且可以干脆證明全部的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不行逾越的困難）。證明過程相當(dāng)困難，其或許意思是說隨意一個NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計算機內(nèi)部也不過是一些0和1的運算），因此對于一個NP問題來說，問題轉(zhuǎn)化為了求出滿足結(jié)果為True的一個輸入（即一個可行解）。1.5.3一些典型的NP完全問題定理8-7(Cook定理)：布爾表達(dá)式的可滿足性問題SAT是NP完全的。--第一個NPC問題證明：SAT的一個實例是k個布爾變量，…，的m個布爾表達(dá)式，…，若存在各布爾變量(1≤i≤k)的0，1賦值，使每個布爾表達(dá)式(1≤i≤m)都取值1，則稱布爾表達(dá)式…是可滿足的。

SAT∈NP是很明顯的。對于任給的布爾變量，…，的0，1賦值，容易在多項式時間內(nèi)驗證相應(yīng)的…的取值是否為1。因此，SAT∈NP?，F(xiàn)在只要證明對任意的L∈NP有L∝pSAT即可（略）1.5.3一些典型的NP完全問題1.5.3一些典型的NP完全問題部分NP完全問題樹布爾表達(dá)式的可滿足問題合取范式的可滿足問題三元合取范式的可滿足問題哈密頓回路問題旅行售貨商問題團(tuán)問題頂點覆蓋問題子集和問題65（1）合取范式的可滿足性問題（CNF-SAT）問題描述：給定一個合取范式α，判定它是否可滿足。如果一個布爾表達(dá)式是一些因子和之積，則稱之為合取范式，簡稱CNF(ConjunctiveNormalForm)。這里的因子是變量或。例如：就是一個合取范式，而就不是合取范式。（2）3元合取范式的可滿足性問題（3-SAT）問題描述：給定一個3元合取范式α，判定它是否可滿足。1.5.3一些典型的NP完全問題66（3）團(tuán)問題（CLIQUE）問題描述：給定一個無向圖G=(V，E)和一個正整數(shù)k，判定圖G是否包含一個k團(tuán)，即是否存在，V’V，|V’|=k，且對隨意u，w∈V’有(u，w)∈E。（4）頂點覆蓋問題（VERTEX-COVER）問題描述：給定一個無向圖G=(V，E)和一個正整數(shù)k，判定是否存在V’V，|V’|=k，使得對于隨意(u，v)∈E有u∈V’或v∈V’。假如存在這樣的V’