算法分析與設(shè)計(jì)第 1章

1、算法設(shè)計(jì)與分析Design and Analysis of Algorithms 任課教師：張小東聯(lián)系方式：z_答疑地點(diǎn)：宋健研究院5178/9/20221教材、參考書(shū)與課時(shí)安排教材算法設(shè)計(jì)與分析呂國(guó)英 主編清華大學(xué)出版社8/9/2022 4:03 PM2Introduction to Algorithms（Second）Thomas H. CommonHIGHER EDUCATION PRESS參考資料計(jì)算機(jī)算法設(shè)計(jì)與分析（第2版）王曉東電子工業(yè)出版社8/9/2022 4:03 PM3Introduction to the Design and Analysis of AlgorithmsA

2、nany V.LevitinAddison-Wesley課時(shí)安排授課 ：32學(xué)時(shí)實(shí)驗(yàn) : 16學(xué)時(shí)作業(yè)要求以組為單位進(jìn)行算法設(shè)計(jì)，各有分工，且分工明確，獨(dú)立完成自己的工作，并進(jìn)行抽查實(shí)驗(yàn)要求以組為單位進(jìn)行算法設(shè)計(jì)，各有分工，且分工明確，各自完成自己的工作，獨(dú)立書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告8/9/2022 4:03 PM4主要內(nèi)容算法分析體系及計(jì)量算法基本工具及優(yōu)化技巧基本的算法策略迭代算法蠻力法分治算法貪婪算法動(dòng)態(tài)規(guī)劃圖的搜索算法廣度優(yōu)先搜索深度優(yōu)先搜索回溯法分支限界法算法設(shè)計(jì)實(shí)踐8/9/2022 4:03 PM5第1章 算法概述主要內(nèi)容算法描述現(xiàn)代常用算法概覽用計(jì)算機(jī)求解問(wèn)題與算法8/9/2022 4:03

3、 PM6學(xué)習(xí)目標(biāo)：用計(jì)算機(jī)求解問(wèn)題用計(jì)算機(jī)求解問(wèn)題與算法問(wèn)題求解人工智能的成就博奕模擬人類的智能去解決問(wèn)題用計(jì)算機(jī)求解問(wèn)題的步驟一、問(wèn)題分析（checklist）在原始表達(dá)中，所用術(shù)語(yǔ)都有準(zhǔn)確的定義？題目中提供了哪些信息？它們的作用？題目要求的結(jié)果是什么？是否有潛在的信息？判定求解結(jié)果所需要的中間結(jié)果有哪些？8/9/2022 4:03 PM7二、數(shù)學(xué)模型的建立最適合于此問(wèn)題的數(shù)學(xué)模型是什么？是否有已經(jīng)解決的類似問(wèn)題可以借鑒？注重對(duì)不同模型的分析與比較三、算法設(shè)計(jì)與選擇從數(shù)據(jù)結(jié)構(gòu)、模型等方面進(jìn)行考慮四、算法表示流程圖、盒圖、PAD圖和偽碼等五、算法分析時(shí)間與空間上的開(kāi)銷建立衡量算法優(yōu)劣的標(biāo)準(zhǔn)六、

4、算法實(shí)現(xiàn)七、程序調(diào)試選擇測(cè)試方法與測(cè)試實(shí)例八、文檔編制8/9/2022 4:03 PM8算法及其要素和特性算法定義算法的三要素操作控制結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法的基本性質(zhì)目的性、分步性、有序性、有限性、操作性算法的地位是計(jì)算機(jī)科學(xué)中最具有方法論性質(zhì)的核心概念基本特征有窮性、確定性、可行性、有輸入輸出8/9/2022 4:03 PM9算法設(shè)計(jì)及基本方法質(zhì)量指標(biāo)正確性、可讀性、健壯性、高效率與低存儲(chǔ)需求結(jié)構(gòu)化方法本書(shū)采用的方法自頂向下，逐步求精模塊化設(shè)計(jì)簡(jiǎn)單、獨(dú)立和完整模塊間的接口面象對(duì)象方法抽象化、封裝性、多態(tài)性、繼承性從算法到實(shí)現(xiàn)數(shù)據(jù)類型的選擇計(jì)算過(guò)程的差異結(jié)果的輸出格式測(cè)試、調(diào)試8/9/2022 4:

5、03 PM10算法描述算法描述簡(jiǎn)介自然語(yǔ)言流程圖盒圖PAD圖偽代碼程序設(shè)計(jì)語(yǔ)言（不是很適合算法描述）PYNABWHILE pSS1S2S3P=P1P=P2P=Pn8/9/2022 4:03 PM11算法描述約定（類C）3種基本控制結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)模塊及模塊間的接口方式的描述其他說(shuō)明運(yùn)算符采用較通用的形式mod、邏輯運(yùn)算法表示整除；/帶小數(shù)的除不等號(hào)注釋用/input/print庫(kù)函數(shù)的使用8/9/2022 4:03 PM12一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)程數(shù)據(jù)處理要求問(wèn)題邏輯結(jié)構(gòu)基本功能數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu)算法實(shí)現(xiàn)性能文檔評(píng)價(jià)問(wèn)題分析算法設(shè)計(jì)算法分析例1-1求兩個(gè)正整數(shù)的最大公約數(shù)數(shù)學(xué)模型：a、b0,求c。c能

6、整除a、b，且a/c與b/c互質(zhì)算法設(shè)計(jì)：“短除法”。找出兩數(shù)的所有公約數(shù)，累乘。main（）int a,b,i,t=1; input(a,b);for(i=2;i=a and i=b;i=i+1) while(a mod i=0 and b mod i=0) t=t*i;a=a/i;b=b/i;print(a,b,”maximal divisor is”,t);算法分析：算法中的主要操作是比較和累乘。由于算法是盲目地嘗試可能的因數(shù)，比較操作次數(shù)較多，算法效率不高。8/9/2022 4:03 PM13現(xiàn)代常用算法概覽壓縮算法概念：采用特殊的編碼方式來(lái)保存數(shù)據(jù)，使數(shù)據(jù)占用的存儲(chǔ)空間比較小。應(yīng)用：

7、文字、圖形、圖像分類：（非）即時(shí)壓縮、數(shù)據(jù)和文件壓縮、無(wú)損（2：15：1）與有損壓縮壓縮原理：冗余、頻度、相關(guān)性壓縮算法無(wú)損壓縮：Huffman、字典壓縮等有損壓縮：脈沖編碼調(diào)制（PCM）、線性預(yù)測(cè)（LPC）、矢量量化（VQ）離散小波變換（DWT）等8/9/2022 4:03 PM14加密算法概述：信息安全的核心技術(shù)加密/解密算法其它加密方法人工智能算法概念：人類智能的計(jì)算機(jī)模擬研究方法：仿生學(xué)、計(jì)算機(jī)數(shù)學(xué)、心理學(xué)等現(xiàn)狀與未來(lái)：實(shí)現(xiàn)了人類左腦的邏輯推理；將來(lái)仿人類右腦的模糊處理能力和整個(gè)大腦的并行化處理并行算法概念：把一個(gè)事物的行為看成是多個(gè)事物互相作用的結(jié)果目的：提高計(jì)算速度；解決傳統(tǒng)計(jì)算機(jī)無(wú)法解決的問(wèn)題劃分、子問(wèn)題交互、映射8/9/2022 4:03 PM15其它實(shí)用算法數(shù)值算法Maple、MATLAB、Mathematica等運(yùn)籌學(xué)相關(guān)算法統(tǒng)計(jì)分析算法 SPSS、SAS網(wǎng)絡(luò)搜索引擎算法提高搜索引擎對(duì)用戶檢索提問(wèn)的理解對(duì)檢索結(jié)果進(jìn)處理基于鏈接評(píng)價(jià)的搜索引擎（Google）基于大眾性搜索引擎（Direct Hit