第1章 算法引論

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

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

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

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

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

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

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

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

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

10、的能力。 通過進(jìn)一步閱讀相關(guān)英文文獻(xiàn)資料，鞏固了學(xué)習(xí)成果、拓寬了思通過進(jìn)一步閱讀相關(guān)英文文獻(xiàn)資料，鞏固了學(xué)習(xí)成果、拓寬了思路，了解領(lǐng)域前沿。路，了解領(lǐng)域前沿。11五、主要內(nèi)容介紹 算法設(shè)計(jì)與分析領(lǐng)域的經(jīng)典內(nèi)容，并介紹了算法設(shè)計(jì)的發(fā)展趨勢(shì)。內(nèi)容主要包括非常經(jīng)典的算法設(shè)計(jì)技術(shù)，例如遞歸與分治、動(dòng)態(tài)規(guī)劃、貪心、回溯、分支限界、圖算法，也包括了一些高級(jí)的算法設(shè)計(jì)主題，例如網(wǎng)絡(luò)流和匹配、啟發(fā)式搜索、線性規(guī)劃等?；A(chǔ)篇基礎(chǔ)篇 第1章算法引論 第2章遞歸與分治策略 第3章動(dòng)態(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 六、考核與成績(jī)?cè)u(píng)定（*） 學(xué)生出勤：10% 課堂表現(xiàn)：10% 作業(yè)完成：10% 實(shí)驗(yàn)、實(shí)訓(xùn)： 10% 期末成績(jī)：60% 課程論文課程論文15第1章 算法引論 1.1 算法與程序 1.2 從問題到程序 1.3 表達(dá)算法的抽象機(jī)制 1.4 描述算法 1.5 算法復(fù)雜性分析本章主要知識(shí)點(diǎn)：161.1 算法與程序 算法（algorithms）的研究是計(jì)算機(jī)科學(xué)的核心課題之一 。 算法是解決某一特定類型問題的有限運(yùn)算序列 。從數(shù)據(jù)表示的觀點(diǎn)來看

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

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

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

15、的證明和復(fù)雜性的分析。 22采用Java語言、類C語言等描述算法。1.1.JavaJava程序結(jié)構(gòu)程序結(jié)構(gòu) 1.4描述算法例如，JavaJava語言的若干重要特性如下。 （1）Java程序的兩種類型：應(yīng)用程序和appletapplet區(qū)別：應(yīng)用程序的主方法為main，其可在命令行中用命令語句 java 應(yīng)用程序名 來執(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對(duì)兩種數(shù)據(jù)類型的不同處理方式： 對(duì)基本數(shù)據(jù)類型：在聲明一個(gè)具有基本數(shù)據(jù)類型的變量時(shí)，自動(dòng)建立該數(shù)據(jù)類型的對(duì)象（或稱實(shí)例）。如:int k;對(duì)非基本數(shù)據(jù)類型：語句 String s; 并不建立具有數(shù)據(jù)類型String的對(duì)象，而是建立一個(gè)類型String的引用對(duì)象，數(shù)據(jù)類型為String的對(duì)象可用下面的new語句建立。 s = new StringString(“Welco

17、me”);StringString s = new StringString(“Welcome”);241.4描述算法3.3.方法方法在Java中，執(zhí)行特定任務(wù)的函數(shù)或過程統(tǒng)稱為方法(methods) 。例如，java的MathMath類類給出的常見數(shù)學(xué)計(jì)算的方法如下表所示：方法方法功能功能方法方法功能功能abs(x)x的絕對(duì)值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的自然對(duì)數(shù)tan(x)x的正切

18、251.4描述算法3.3.方法方法 2baba計(jì)算表達(dá)式 值的自定義方法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í)通過實(shí)際參數(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算法復(fù)雜性分析 算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。 一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，則有： T=T(N,I)和S=S(N,I) 。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中） 281.5算法復(fù)雜性分析算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、o 設(shè)f(N)和g(N)是

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

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

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