算法設(shè)計與分析簡介首先思考幾個問題？2計算機(jī)科學(xué)并不只是關(guān)于計算機(jī)，就像天文學(xué)并不只是關(guān)于望遠(yuǎn)鏡一樣。

——EdsgerDijkstra首先思考幾個問題？計算機(jī)科學(xué)到底是不是科學(xué)？計算機(jī)科學(xué)的核心是什么？3首先思考幾個問題？41974年圖靈獎獲得者《計算機(jī)程序設(shè)計的藝術(shù)》Tex排版系統(tǒng)之父算法+數(shù)據(jù)結(jié)構(gòu)=程序！首先思考幾個問題？計算機(jī)科學(xué)到底是不是科學(xué)？計算機(jī)科學(xué)的核心是什么？計算機(jī)的能力是否有局限？算法（計算）的本質(zhì)和數(shù)學(xué)定義是什么？5課程主要內(nèi)容在計算機(jī)應(yīng)用中經(jīng)常遇到的問題和求解的算法設(shè)計算法基本原理、技巧以及算法復(fù)雜性分析分治法動態(tài)規(guī)劃法貪心法網(wǎng)絡(luò)流搜索近似算法NP-完全性隨機(jī)算法在線算法6課程目的具備抽象描述、解決實際問題的能力學(xué)會運(yùn)用算法設(shè)計與分析的典型方法進(jìn)行算法的設(shè)計具備分析算法效率的能力。7算法的重要性有超過1/3的Turing獎獲獎?wù)撸涑晒c算法有關(guān)圖靈獎于1966年開始設(shè)立，是ACM(美國計算機(jī)協(xié)會)在計算機(jī)科學(xué)技術(shù)領(lǐng)域中所授予的最高獎項8圖靈獎獲得者1972，EdsgerW.Dijkstra求最短路徑的Dijkstra算法,PV操作,解決了“哲學(xué)家聚餐”問題第一個Algol60編譯器結(jié)構(gòu)化程序設(shè)計,“goto有害”等9圖靈獎獲得者1974，DonaldE.Knuth(stanford)算法最早的奠基人之一(計算機(jī)程序設(shè)計藝術(shù))現(xiàn)代“算法”與“數(shù)據(jù)結(jié)構(gòu)”名詞及內(nèi)涵的提出，KMP算法，LR(k)文法，Tex編輯器等10圖靈獎獲得者1976，MichaelO.Rabin(以色列)

DanaS.Scott(英)師兄弟(導(dǎo)師A.Church)非確定有窮自動機(jī)的提出、判定問題等Rabin：計算復(fù)雜性概念的雛形、隨機(jī)算法的思想奠定、尋找及判定素數(shù)算法，單向函數(shù)等Scott:語義學(xué)等。11圖靈獎獲得者1978，RobertW.Floyd(美)求最短路徑的Floyd算法，Heap-sort算法等編譯及優(yōu)化（優(yōu)先文法等）程序正確性證明等12圖靈獎獲得者1980，C.AnthonyR.Hoare(英)1983年ACM評出的1/4世紀(jì)最有影響的25篇論文中，Hoare與Dijkstra有兩篇入選(其余人只有一篇)算法的代表作：Quick-sort算法，程序設(shè)計(CASE、While語句等)，數(shù)據(jù)通信等13圖靈獎獲得者1982，StevenA.Cook(加Toronto大學(xué))“NP-完全”概念的提出與理論的奠定，算法復(fù)雜性14圖靈獎獲得者1984，NiklausWirth(瑞士蘇黎世高工)“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，結(jié)構(gòu)化程序設(shè)計創(chuàng)始人“Pascal之父”,數(shù)據(jù)結(jié)構(gòu)，ExtendedBNF等15圖靈獎獲得者1985，RichardM.Karp(UC-Berkeley)：分枝限界法的創(chuàng)始人（與Held），Rabin-Karp子串匹配算法，求網(wǎng)絡(luò)最大流的Edmonds-Karp算法，NP-完全理論（Karp規(guī)約等），隨機(jī)算法，并行算法等16圖靈獎獲得者1993，JurisHartmanis(Cornell)&RichardE.Stearns(Albany)計算復(fù)雜性理論的主要奠基人Hartmanis：Hartmanis矩陣乘法，Hartmanis快速離散傅立葉變換Stearns：首先提出將上下文無關(guān)文法理論應(yīng)用于編譯器設(shè)計等17圖靈獎獲得者2000，AndrewYao(姚期智)唯一華裔圖靈獎獲得者計算復(fù)雜性，量子計算，密碼學(xué)(e.g.單向函數(shù))、通信理論等18圖靈獎獲得者2002，RonaldL.Rivest，AdiShamir，LeonardM.Adelman：公共密鑰算法(RSA算法是當(dāng)前在互聯(lián)網(wǎng)傳輸、銀行以及信用卡產(chǎn)業(yè)中被廣泛使用的安全基本機(jī)制)19算法的相關(guān)概念是對特定問題求解步驟的一種描述，是指令的有限序列。具有下列5個特性：有窮性：算法有限步結(jié)束，指令有限時間完成確定性：每條指令都是明確的、無二義的可行性：每條指令都能夠被執(zhí)行輸入：有0個或多個輸入量輸出：有1個或多個輸出量20算法的正確性分析一個算法是正確的，如果它對于每一個輸入都最終停止,而且產(chǎn)生正確的輸出不正確算法：不停止(在某個輸入上)對所有輸入都停止，但對某輸入產(chǎn)生不正確結(jié)果近似算法對所有輸入都停止產(chǎn)生近似正確的解或產(chǎn)生不多的不正確解調(diào)試程序

程序正確性證明程序調(diào)試只能證明程序有錯，不能證明程序無錯誤!21算法好壞的衡量尺度最初，用所需計算時間來衡量算法的好壞但不同的機(jī)器相互之間無法比較故需要用獨立于具體計算機(jī)的客觀衡量標(biāo)準(zhǔn)問題的規(guī)模基本運(yùn)算算法的計算量函數(shù)22算法好壞的衡量尺度時間復(fù)雜度基本運(yùn)算（原子操作）執(zhí)行次數(shù)空間復(fù)雜度需要的存儲空間大小23算法好壞的衡量尺度問題的規(guī)模一個或多個整數(shù)，作為輸入數(shù)據(jù)量的測度數(shù)組的長度(數(shù)據(jù)項的個數(shù))問題：在一個數(shù)組中尋找X矩陣的最大維數(shù)(階數(shù))問題：求兩個實矩陣相乘的結(jié)果輸入規(guī)模通常用n來表示也可有兩個以上的參數(shù)，如圖中的頂點數(shù)和邊數(shù)(圖論中的問題)24算法好壞的衡量尺度基本運(yùn)算解決給定問題時占支配地位的運(yùn)算在一個表中尋找數(shù)據(jù)元素xx與表中的一個項進(jìn)行比較兩個實矩陣的乘法實數(shù)的乘法(及加法)C=AB則cij=∑aik*bkj將一個數(shù)組進(jìn)行排序數(shù)組中的兩個數(shù)據(jù)項進(jìn)行比較25算法好壞的衡量尺度基本運(yùn)算通常情況下，討論一個算法優(yōu)劣時，我們只討論基本運(yùn)算的執(zhí)行次數(shù)因為它是占支配地位的，而其它的運(yùn)算可以忽略不計26算法好壞的衡量尺度算法的計算量函數(shù)用輸入規(guī)模的某個函數(shù)來表示算法的基本運(yùn)算量該函數(shù)稱為算法的時間復(fù)雜性(度)，一般用T(n)或T(n,m)等表示T(n)=5n，T(n)=3n*logn，T(n)=4n3，T(n)=2n，T(n,m)=2(n+m)27最壞情況時間復(fù)雜性規(guī)模為n的所有輸入中，基本運(yùn)算執(zhí)行次數(shù)最多的時間復(fù)雜性在一個順序表中尋找數(shù)據(jù)元素