1算法設(shè)計(jì)與分析2學(xué)習(xí)要求1考勤(五次缺勤，取消考試資格)2作業(yè)(嚴(yán)禁抄襲，兩次取消考試資格)3課堂紀(jì)律4課堂提問三次不回答，算缺勤一次，此后每一次不回答，則計(jì)一次缺勤。5遲到3次算缺勤6平時(shí)20%，考試80%7嚴(yán)禁考試成績(jī)出來后要求修改成績(jī)3本門課程課時(shí)少注重介紹思想不考慮算法的實(shí)現(xiàn)細(xì)節(jié)每個(gè)算法均可上機(jī)實(shí)現(xiàn)3節(jié)上機(jī)課課程特點(diǎn)4存在的疑問什么是算法算法設(shè)計(jì)的整體過程為什么要引入算法(為什么要進(jìn)行算法設(shè)計(jì))算法分析要涉及那些方面（第二章內(nèi)容）5思考題假設(shè)有四種類型的硬幣，它們的面值分別為2角5分，1角，5分和1分?，F(xiàn)在要找給某顧客6角3分錢，如何找？（假設(shè)各種類型的硬幣足夠多）6四種類型的硬幣，它們的面值分別為2角5分，1角，5分和1分?，F(xiàn)在要找給某顧客6角3分錢，如何找？（假設(shè)各種類型的硬幣足夠多）拿出2個(gè)2角5分的硬幣，1個(gè)1角，3個(gè)1分拿出6個(gè)1角錢，3個(gè)1分錢第一種方法的考慮：首先選出一個(gè)面值不超過6角3分錢的最大硬幣，既2角5分錢；然后從6角3分中減去2角5分，剩下3角8分；再選出一個(gè)面值不超過3角8分的最大硬幣，既又一個(gè)2角5分，如此一直做下去。每次挑選的硬幣都是面值不超過找錢余額的最大硬幣。第二種方法的考慮：按照錢的單位來找。7結(jié)論對(duì)于一個(gè)問題我們都有相應(yīng)的解決方法一個(gè)問題有不同的方法各方法有不同的特點(diǎn)方法一的找?guī)艛?shù)量少于方法二（6個(gè)VS9個(gè)）方法二簡(jiǎn)單有助于理解前面提出的問題什么是算法－－解決問題的方法算法設(shè)計(jì)－－找出方法算法分析－－分析方法的特點(diǎn)，選擇合適方法8一什么是算法－概念算法是一系列解決問題的清晰指令，也就是說，能夠?qū)Ψ弦欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。簡(jiǎn)單的說，就是解決問題的一種方法或過程。9一什么是算法－特征（1）確定性算法的每一個(gè)步驟都必須清晰，明確，這是來不得半點(diǎn)含糊的。算法所處理的輸入的值域必須仔細(xì)定義。（2）多樣性算法的描述形式有多種?？赡艽嬖诮鉀Q同一問題的多種算法。針對(duì)同一個(gè)問題的算法可能會(huì)基于完全不同的解題思路，而且解題目速度也會(huì)有顯著不同。（3）有窮性：指令是有限的，每條指令的執(zhí)行包含有限的工作量，算法的整個(gè)指令序列的執(zhí)行會(huì)在有限時(shí)間內(nèi)結(jié)束；（4）輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；10二算法設(shè)計(jì)分析過程證明正確性分析算法設(shè)計(jì)程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法11二算法設(shè)計(jì)分析過程－理解問題問題:一個(gè)一般化的概念.例如:排序問題實(shí)例:問題的一個(gè)實(shí)際情況.例如,排序問題中待排序的量的個(gè)數(shù)、每個(gè)量的值構(gòu)成了問題的一個(gè)實(shí)例。

算法為問題而建立，但是算法不能為問題而運(yùn)行；算法只能為問題的實(shí)例而運(yùn)行。

不要對(duì)算法解題的第一步敷衍了事，否則就要冒返工的風(fēng)險(xiǎn)12二算法設(shè)計(jì)分析過程－理解問題任務(wù)1）透徹地理解需求分析（目標(biāo)與功能）；對(duì)問題進(jìn)行詳細(xì)的定義（包括清晰的處理步驟和輸入的值域范圍）。2）確定問題類型。3）考慮可采用的算法。13最重要的問題類型：排序查找串處理圖問題組合問題幾何問題數(shù)值問題二算法設(shè)計(jì)分析過程－理解問題14是否支持并行計(jì)算。計(jì)算速度。內(nèi)存容量。二算法設(shè)計(jì)分析過程－計(jì)算設(shè)備的性能15近似解法的適合情況1）存在精確解，但在可接受的時(shí)間內(nèi)，無法實(shí)現(xiàn)。2）問題本身不存在精確解3）一個(gè)近似算法是某個(gè)精確求解方案的一部分。

二算法設(shè)計(jì)分析過程－

精確解法或近似解法的抉擇16算法＋數(shù)據(jù)結(jié)構(gòu)＝程序1）有些問題必須使用精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)才能求解。2）算法與數(shù)據(jù)結(jié)構(gòu)相互依存。學(xué)過哪些數(shù)據(jù)結(jié)構(gòu)？線性圖樹集合與字典二算法設(shè)計(jì)分析過程－

確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)17窮舉法（蠻力法）、分治法、動(dòng)態(tài)規(guī)劃、貪心法、回朔法等。二算法設(shè)計(jì)分析過程－

算法設(shè)計(jì)技術(shù)18偽代碼流程圖二算法設(shè)計(jì)分析過程－

詳細(xì)表述算法的方法19

歸納法、反證法等。二算法設(shè)計(jì)分析過程－

證明算法的正確性201）算法設(shè)計(jì)依賴計(jì)算機(jī)的處理速度、吞吐量、峰值。2）算法分析為了便于算法之間的相互比較，獨(dú)立于計(jì)算機(jī)處理速度。二算法設(shè)計(jì)分析過程－

算法設(shè)計(jì)與算法分析的異同點(diǎn)21二算法設(shè)計(jì)分析過程－

為算法寫代碼程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。22三

為什么在計(jì)算機(jī)學(xué)科中引入算法

重用性－－尤指一種為在有限步驟內(nèi)解決問題而建立的可重復(fù)應(yīng)用的計(jì)算過程。

正確、高效專業(yè)的計(jì)算機(jī)軟件人員和發(fā)燒友的差別計(jì)算機(jī)科學(xué)的核心是算法23三

為什么在計(jì)算機(jī)學(xué)科中引入算法

–