第1章 算法引論

1、1課程概述 一、算法分析與設計介紹 二、學習目標 三、參考教材 四、課程特點和學習的注意事項 五、主要內(nèi)容 六、考核方式一、算法分析與設計介紹 算法算法即演算法，出自即演算法，出自周髀算經(jīng)周髀算經(jīng)，英文名稱，英文名稱Algorithm,算法是計算機科學的核心主題之一。算法是計算機科學的核心主題之一?！八惴ㄋ惴ā痹瓰樵瓰閍lgorismalgorism，意思是阿拉伯數(shù)字的運算，意思是阿拉伯數(shù)字的運算法則，在法則，在1818世紀演變?yōu)槭兰o演變?yōu)閍lgorithmalgorithm。歐幾里得算法歐幾里得算法被人們認為是史上第一個算法。被人們認為是史上第一個算法。第一次編寫程序是第一次編寫程序是Ada

2、 ByronAda Byron于于18421842年為巴貝奇分析年為巴貝奇分析機編寫求解伯努利方程的程序。機編寫求解伯努利方程的程序。2020世紀的英國數(shù)學家世紀的英國數(shù)學家圖靈圖靈提出了著名的圖靈論題，并提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機圖靈機。圖靈機的出現(xiàn)解決了算法定義的難題圖靈機的出現(xiàn)解決了算法定義的難題一、算法分析與設計介紹（續(xù)） 計算機算法指解題方案的準確而完整的描述，是一系計算機算法指解題方案的準確而完整的描述，是一系列解決問題的清晰指令。列解決問題的清晰指令。算法代表著用系統(tǒng)的方法描述解決問題

3、的策略機制，即：能算法代表著用系統(tǒng)的方法描述解決問題的策略機制，即：能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。開發(fā)高效軟件的前提和基礎。開發(fā)高效軟件的前提和基礎。 算法中的指令算法中的指令描述的是一個計算，當其運行時能從一描述的是一個計算，當其運行時能從一個個初始狀態(tài)初始狀態(tài)和（可能為空的）和（可能為空的）初始輸入開始初始輸入開始，經(jīng)過，經(jīng)過一一系列有限而清晰定義的狀態(tài)系列有限而清晰定義的狀態(tài)，最終，最終產(chǎn)生輸出并停止于產(chǎn)生輸出并停止于一個終態(tài)一個終態(tài)。一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移不一定是確定的。一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移不一定是確定的

4、。隨機化算法在內(nèi)的一些算法，包含了一些隨機輸入。隨機化算法在內(nèi)的一些算法，包含了一些隨機輸入。一、算法分析與設計介紹（續(xù)） 形式化算法形式化算法的概念部分源自嘗試解決希爾伯特提出的概念部分源自嘗試解決希爾伯特提出的判定問題，并在其后嘗試定義有效計算性或者有的判定問題，并在其后嘗試定義有效計算性或者有效方法中成形。這些嘗試包括：效方法中成形。這些嘗試包括： 庫爾特庫爾特哥德爾、哥德爾、Jacques Herbrand和斯蒂芬和斯蒂芬科爾科爾克萊尼分別于克萊尼分別于1930年、年、1934年和年和1935年提出的遞歸函年提出的遞歸函數(shù)數(shù) 阿隆佐阿隆佐邱奇于邱奇于1936年提出的年提出的演算演算 1

5、936年年Emil Leon Post的的Formulation 1 艾倫艾倫圖靈圖靈1937年提出的圖靈機。年提出的圖靈機。一、算法分析與設計介紹（續(xù)）算法分析與設計算法分析與設計是計算機科學與技術類（計算機應用、軟件）研究生的是計算機科學與技術類（計算機應用、軟件）研究生的一門重要專業(yè)學位課程。一門重要專業(yè)學位課程?！八惴ㄔO計與分析算法設計與分析”很有用很有用算法是計算機科學的核心主題之一。算法是計算機科學的核心主題之一。從就業(yè)來看，算法基礎是許多名企面試必考的內(nèi)容。從就業(yè)來看，算法基礎是許多名企面試必考的內(nèi)容。從科學研究來看，算法設計與分析是計算機科學諸多領域研究中必須的技從科學研究來看

6、，算法設計與分析是計算機科學諸多領域研究中必須的技能。能。“算法設計與分析算法設計與分析”很有趣很有趣算法給了我們一個看待世界和看待生活的新方式，從中學到的不僅是讓計算法給了我們一個看待世界和看待生活的新方式，從中學到的不僅是讓計算機做事情的方式，還有算機做事情的方式，還有“遞歸遞歸”、“分治分治”“”“優(yōu)化優(yōu)化”、“剪枝剪枝”等等一等等一系列可能改變生活的思維方法。系列可能改變生活的思維方法。一、算法分析與設計介紹（續(xù)）課程名稱課程名稱 算法分析與設計算法分析與設計課程學時課程學時/學分學分 講授：講授：51/3開課時間：周五開課時間：周五3-5開課地點：開課地點：C512學習方法：理論學習

7、方法：理論+實踐實踐二、學習目標 通過對算法分析與設計課程的學習：通過對算法分析與設計課程的學習：研究研究, ,理解和掌握算法設計的理解和掌握算法設計的主要方法主要方法培養(yǎng)學生培養(yǎng)學生對算法的計算復雜性進行正確分對算法的計算復雜性進行正確分析的能力析的能力為為獨立設計算法獨立設計算法和和對給定算法進行復雜性對給定算法進行復雜性分析分析奠定堅實的理論基礎。奠定堅實的理論基礎。三、參考教材 算法設計與分析算法設計與分析，王曉東，清華大學出版社，王曉東，清華大學出版社 算法設計與分析算法設計與分析，張德富，國防工業(yè)出版社，張德富，國防工業(yè)出版社，2009-8-1。 Introduction to A

8、lgorithms, Second Edition , Thomas H.Cormen 算法導論算法導論，譯者，譯者: 潘金貴。潘金貴。 算法設計與分析基礎算法設計與分析基礎，(美美)萊維丁，清華大學出版社。萊維丁，清華大學出版社。 算法分析與設計算法分析與設計，古德里奇、塔瑪西亞編著，人民郵電，古德里奇、塔瑪西亞編著，人民郵電出版社出版社 算法設計技巧與分析算法設計技巧與分析， M.H.Alsuwaiyel，電子工業(yè)出版社，電子工業(yè)出版社，2010-10-1。 四、課程特點和學習的注意事項 課程特點課程特點是一門重視能力的課程，理論是一門重視能力的課程，理論+ +實踐實踐學習算法設計與分析既

9、需要像數(shù)學課一樣的證明、又需要像學習算法設計與分析既需要像數(shù)學課一樣的證明、又需要像程序設計語言一樣的寫碼，因而需格外的努力才可學得好。程序設計語言一樣的寫碼，因而需格外的努力才可學得好。需具備數(shù)據(jù)結(jié)構、離散數(shù)學的基礎，以及需具備數(shù)據(jù)結(jié)構、離散數(shù)學的基礎，以及CC+CC+、JavaJava等語言等語言編程能力，熟悉編程能力，熟悉MATLABMATLAB等仿真工具。等仿真工具。 注意事項：注意事項： 勤于思考、積極動手實踐。勤于思考、積極動手實踐。 善于應理論聯(lián)系實際問題，在提高本領域知識的能力的同時，提善于應理論聯(lián)系實際問題，在提高本領域知識的能力的同時，提高獨立解決問題的能力。高獨立解決問題

10、的能力。 通過進一步閱讀相關英文文獻資料，鞏固了學習成果、拓寬了思通過進一步閱讀相關英文文獻資料，鞏固了學習成果、拓寬了思路，了解領域前沿。路，了解領域前沿。11五、主要內(nèi)容介紹 算法設計與分析領域的經(jīng)典內(nèi)容，并介紹了算法設計的發(fā)展趨勢。內(nèi)容主要包括非常經(jīng)典的算法設計技術，例如遞歸與分治、動態(tài)規(guī)劃、貪心、回溯、分支限界、圖算法，也包括了一些高級的算法設計主題，例如網(wǎng)絡流和匹配、啟發(fā)式搜索、線性規(guī)劃等?；A篇基礎篇 第1章算法引論 第2章遞歸與分治策略 第3章動態(tài)規(guī)劃12五、主要內(nèi)容介紹（續(xù)） 第4章貪心算法 第5章回溯法 第6章分支限界法 第7章概率算法* 第8章NP完全性理論* 第9章近似算

11、法* 第10章算法優(yōu)化策略*13五、主要內(nèi)容介紹（續(xù)）提高篇提高篇 蟻群算法 遺傳算法 常用工具：常用工具： CC+、Java等開發(fā)工具 MATLAB SPSS 六、考核與成績評定（*） 學生出勤：10% 課堂表現(xiàn)：10% 作業(yè)完成：10% 實驗、實訓： 10% 期末成績：60% 課程論文課程論文15第1章 算法引論 1.1 算法與程序 1.2 從問題到程序 1.3 表達算法的抽象機制 1.4 描述算法 1.5 算法復雜性分析本章主要知識點：161.1 算法與程序 算法（algorithms）的研究是計算機科學的核心課題之一 。 算法是解決某一特定類型問題的有限運算序列 。從數(shù)據(jù)表示的觀點來看

12、，算法是指對數(shù)據(jù)結(jié)構施加的一些操作，例如對一個線性表進行檢索、插入、刪除等操作。17 輸 入：有零個或多個外部量作為算法的輸入。 輸 出：算法產(chǎn)生至少一個量作為輸出。 確定性：組成算法的每條指令清晰、無歧義。 有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。 可行性：算法中要執(zhí)行的每一個計算步驟都是可以在有限時間內(nèi)做完的。可行性、有窮性和確定性是相容的。是算法用某種程序設計語言的具體實現(xiàn)。 程序可以不滿足算法的性質(zhì)(4)即有限性。 是滿足下述性質(zhì)的指令序列。算法：程序：181.2 從問題到程序 要用計算機解決問題，必須首先用簡明、嚴格的方式將問題表述清楚 ，所以算法形式的最初解

13、法建立數(shù)學模型 ，可以依據(jù)這一模型求解。 19 算法設計和分析的步驟可概括: （1）問題的陳述。 （2）模型的選擇。 （3）算法的設計。 （4）算法的程序?qū)崿F(xiàn)。 （5）算法分析。 201.從機器語言到高級語言的抽象1.3表達算法的抽象機制高級程序設計語言的主要好處是：（4）把繁雜瑣碎的事務交給編譯程序，所以自動化程度高，開發(fā)周期短，程序員可以集中時間和精力從事更重要的創(chuàng)造性勞動，提高程序質(zhì)量。（1）高級語言更接近算法語言，易學、易掌握，一般工程技術人員只需 要幾周時間的培訓就可以勝任程序員的工作；（2）高級語言為程序員提供了結(jié)構化程序設計的環(huán)境和工具，使得設計出來的程序可讀性好，可維護性強，可

14、靠性高；（3）高級語言不依賴于機器語言，與具體的計算機硬件關系不大，因而所寫出來的程序可植性好、重用率高；212.抽象數(shù)據(jù)類型1.3表達算法的抽象機制 抽象數(shù)據(jù)類型是算法的一個數(shù)據(jù)模型連同定義在該模型上并作為算法構件的一組運算。 抽象數(shù)據(jù)類型帶給算法設計的好處有： （1）算法頂層設計與底層實現(xiàn)分離；（2）算法設計與數(shù)據(jù)結(jié)構設計隔開，允許數(shù)據(jù)結(jié)構自由選擇；（3）數(shù)據(jù)模型和該模型上的運算統(tǒng)一在ADT中，便于空間和時間耗費的折衷；（4）用抽象數(shù)據(jù)類型表述的算法具有很好的可維護性；（5）算法自然呈現(xiàn)模塊化；（6）為自頂向下逐步求精和模塊化提供有效途徑和工具；（7）算法結(jié)構清晰，層次分明，便于算法正確性

15、的證明和復雜性的分析。 22采用Java語言、類C語言等描述算法。1.1.JavaJava程序結(jié)構程序結(jié)構 1.4描述算法例如，JavaJava語言的若干重要特性如下。 （1）Java程序的兩種類型：應用程序和appletapplet區(qū)別：應用程序的主方法為main，其可在命令行中用命令語句 java 應用程序名 來執(zhí)行；applet的主方法為init，其必須嵌入HTML文件，由Web瀏覽器或applet閱讀器來執(zhí)行。（2）包：java程序和類可以包(packages)的形式組織管理。 （3）import語句：在java程序中可用import語句加載所需的包。例如，import java.io

16、.*;語句加載java.io包。 231.4描述算法2.2.JavaJava數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型 基本數(shù)據(jù)類型：詳見下頁表1-1 非基本數(shù)據(jù)類型：如 Byte, Integer, Boolean, String等。 Java對兩種數(shù)據(jù)類型的不同處理方式： 對基本數(shù)據(jù)類型：在聲明一個具有基本數(shù)據(jù)類型的變量時，自動建立該數(shù)據(jù)類型的對象（或稱實例）。如:int k;對非基本數(shù)據(jù)類型：語句 String s; 并不建立具有數(shù)據(jù)類型String的對象，而是建立一個類型String的引用對象，數(shù)據(jù)類型為String的對象可用下面的new語句建立。 s = new StringString(“Welco

17、me”);StringString s = new StringString(“Welcome”);241.4描述算法3.3.方法方法在Java中，執(zhí)行特定任務的函數(shù)或過程統(tǒng)稱為方法(methods) 。例如，java的MathMath類類給出的常見數(shù)學計算的方法如下表所示：方法方法功能功能方法方法功能功能abs(x)x的絕對值max(x,y)x和y中較大者ceil(x)不小于x的最小整數(shù)min(x,y)x和y中較小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整數(shù)sqrt(x)x的平方根log(x)x的自然對數(shù)tan(x)x的正切

18、251.4描述算法3.3.方法方法 2baba計算表達式 值的自定義方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法參數(shù)：Java中所有方法的參數(shù)均為值參數(shù)。上述方法ab中，a和b是形式參數(shù)，在調(diào)用方法時通過實際參數(shù)賦值。 （2）方法重載：Java允許方法重載，即允許定義有不同簽名的同名方法。上述方法ab可重載為： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 261.4描述算法4.

19、4.通用方法通用方法 下面的方法swapswap用于交換一維整型數(shù)組a的位置i和位置j處的值。 public static void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 該方法只適用于該方法只適用于整型數(shù)組整型數(shù)組該方法具有通用性，適用該方法具有通用性，適用于于ObjectObject類型及其所有子類型及其所有子類類 以上方法修改如下：以上

20、方法修改如下：271.5算法復雜性分析 算法復雜性是算法運行所需要的計算機資源的量，需要時間資源的量稱為時間復雜性時間復雜性，需要的空間資源的量稱為空間復雜性空間復雜性。這個量應該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復雜性，那么，應該有C=F(N,I,A)。 一般把時間復雜性和空間復雜性分開，并分別用T和S來表示，則有： T=T(N,I)和S=S(N,I) 。（通常，讓A隱含在復雜性函數(shù)名當中） 281.5算法復雜性分析算法復雜性在漸近意義下的階：漸近意義下的記號：O、o 設f(N)和g(N)是

21、定義在正數(shù)集上的正函數(shù)。 O O的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。 291.5算法復雜性分析 的定義的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當NN0時有f(N)Cg(N)，則稱函數(shù)f(N)當N充分大時下有界，且g(N)是它的一個下界，記為f(N)=(g(N)。即f(N)的階不低于g(N)的階。 的定義的定義：定義f(N)= (g(N)當且僅當f(N)=O(g(N)且f(N)= (g(N)。此時稱f(N)與g(N)同階。3

22、0小結(jié) 掌握算法的特性 學會算法描述的基本方法 能夠?qū)λ惴◤碗s度進行有效分析 討論及作業(yè)討論及作業(yè)31 附：附： C中的標準數(shù)據(jù)類型中的標準數(shù)據(jù)類型 整型數(shù)的幾種類型整型數(shù)的幾種類型 數(shù)據(jù)類型 字長（字） 范圍 說明 signed short int 2-3276832767 有符號短整型數(shù)，簡寫為short或int signed long int 4-21474836482147483647 有符號長整型數(shù)，簡寫為long unsigned short int 2065535 無符號短整型數(shù)，簡寫為unsigned int unsigned long int 404294967295 無符號

23、長整型數(shù)，簡寫為unsigned long 32 附：C中的標準數(shù)據(jù)類型中的標準數(shù)據(jù)類型 2. 浮點型（float） 數(shù)據(jù)類型 字長（字） 數(shù)值范圍 說明 float43.410-38E3.410+38E 單浮點數(shù) double 81.710-308E1.710+308E 雙浮點數(shù) 33 附：附：C中的標準數(shù)據(jù)類型中的標準數(shù)據(jù)類型 3. 字符型（char） 字符在計算機中以其ASCII碼方式表示，其長度為1個字節(jié)，有符號字符型數(shù)取值范圍為-128127，無符號字符型數(shù)取值范圍為0255。34附：附：C中的標準數(shù)據(jù)類型中的標準數(shù)據(jù)類型 指針型（*） 根據(jù)所指的變量類型不同，可以是整型指針（int *）、浮點型指針（float *）、字符型指針（char *）、結(jié)構指針（struct *）和聯(lián)合指針（union *） 35 附：附：C中的標準數(shù)據(jù)類型中的標準數(shù)據(jù)類型 5. 無值型（void） 無值型字節(jié)長度為0，主要有兩個用途：一是明確地表示一個函數(shù)不返回任何值；一是產(chǎn)生一