算法設(shè)計(jì)與分析 課件 0-算法導(dǎo)論

信息工程大學(xué)算法設(shè)計(jì)與分析算法導(dǎo)論國家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版問題1：從課程名可以得到的課程信息有什么？算法設(shè)計(jì)算法分析問題2：可以從哪些方面評(píng)價(jià)一個(gè)應(yīng)用程序的好壞？安全性用戶體驗(yàn)正確性性能……問題3：算法有“好壞”之分嗎？算法有政治立場(chǎng)嗎？這是一門重要的，和工作生活息息相關(guān)的課程，是一門關(guān)注于性能的課程，即要能設(shè)計(jì)好的算法，也要能分析算法的性能。1.課程定位計(jì)算機(jī)相關(guān)專業(yè)的核心課程對(duì)培養(yǎng)計(jì)算思維和求解問題能力起到重要作用為學(xué)習(xí)其它專業(yè)課奠定扎實(shí)的基礎(chǔ)以算法分析方法和常用的算法設(shè)計(jì)策略的學(xué)習(xí)為主2.課程目標(biāo)從算法角度運(yùn)用數(shù)學(xué)工具分析問題和解決問題的基本能力；①能夠正確地分析并評(píng)價(jià)算法，進(jìn)一步設(shè)計(jì)出高效算法；配合實(shí)踐教學(xué)，理論聯(lián)系實(shí)際，理論指導(dǎo)實(shí)踐，規(guī)范完成作業(yè)，鞏固所學(xué)知識(shí)；②③能力素質(zhì)3.課程教材規(guī)劃教材理論實(shí)踐結(jié)合配有微課視頻課程思政典型應(yīng)用詳解代碼可直接運(yùn)行注：國家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)專業(yè)組規(guī)劃教材；教育部高等學(xué)校計(jì)算機(jī)專業(yè)教學(xué)指導(dǎo)委員會(huì)推薦教材。4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計(jì)與分析》1《算法設(shè)計(jì)與分析》微課4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計(jì)與分析》3麻省理工學(xué)院公開課《算法導(dǎo)論》CharlesLeiserson&ErikDemaine1《算法設(shè)計(jì)與分析》微課4.網(wǎng)絡(luò)助學(xué)資源2中國大學(xué)MOOC國家精品課程《算法設(shè)計(jì)與分析》3麻省理工學(xué)院公開課《算法導(dǎo)論》4國內(nèi)外知名的在線評(píng)測(cè)系統(tǒng)：POJ、洛谷等1《算法設(shè)計(jì)與分析》微課最終成績(jī)=平時(shí)成績(jī)(30%)+期末筆試(70%)平時(shí)成績(jī)=課前預(yù)習(xí)（5%）+課堂測(cè)試

(5%)+編程實(shí)踐

(20%)5.考核評(píng)價(jià)加入平時(shí)成績(jī)的構(gòu)成圖示■

課前預(yù)習(xí)5%20%■

編程實(shí)踐■

課堂測(cè)試5%總學(xué)時(shí)40，理論30+實(shí)踐10test.ctest_2.ctest_3.c總學(xué)時(shí)40，理論30+實(shí)踐10算法分析□算法分析準(zhǔn)則□時(shí)間復(fù)雜度分析方法□最優(yōu)性定義與證明□NP完全性理論算法設(shè)計(jì)□遞歸與分治□動(dòng)態(tài)規(guī)劃□貪心法□回溯法□分支限界法□概率算法實(shí)踐環(huán)節(jié)：算法設(shè)計(jì)策略的編程實(shí)踐2.課程重點(diǎn)難點(diǎn)1.每種算法設(shè)計(jì)策略的適用條件、求解步驟、分析方法和典型應(yīng)用的求解方法等。算法設(shè)計(jì)策略典型應(yīng)用遞歸與分治策略二分搜索、快速排序、歸并排序、棋盤覆蓋、大整數(shù)相乘、矩陣相乘、最接近點(diǎn)對(duì)、…動(dòng)態(tài)規(guī)劃矩陣連乘、0-1背包、最長(zhǎng)公共子序列、最大子段和、最優(yōu)二叉搜索樹、、…貪心活動(dòng)安排、單源最短路徑、哈夫曼編碼、背包問題、最小生成樹、最優(yōu)裝載、過河問題、…回溯N皇后、0-1背包、旅行售貨員、子集和、裝載問題、最大團(tuán)問題、圖的m著色、連續(xù)郵資問題…分支限界0-1背包、旅行售貨員、電路板排列、批處理作業(yè)調(diào)度、布線問題、裝載問題、最大團(tuán)問題、…分治動(dòng)態(tài)規(guī)劃貪心動(dòng)態(tài)規(guī)劃回溯分支限界2.不同算法設(shè)計(jì)策略之間的聯(lián)系與區(qū)別。1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個(gè)轉(zhuǎn)變1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個(gè)轉(zhuǎn)變問題：一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子？1.指導(dǎo)策略提升抽象分析能力看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個(gè)轉(zhuǎn)變問題：一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子？等價(jià)為：斐波那契數(shù)列1.指導(dǎo)策略提升抽象分析能力拓展計(jì)算思維能力直觀單一思路多種算法策略轉(zhuǎn)變看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個(gè)轉(zhuǎn)變十個(gè)藥瓶，裝有相同數(shù)量的藥，但其中有1瓶每一片藥都輕1毫克，給你一把秤，你需要用幾次秤，才能找到藥片輕一點(diǎn)的藥瓶？只能使用1次秤，你還能找到嗎？有問題的藥不確定有哪幾瓶，依然只能使用1次秤，你能一次全找到嗎？1.指導(dǎo)策略轉(zhuǎn)變只求可行方法擇優(yōu)選擇方法提升抽象分析能力拓展計(jì)算思維能力增強(qiáng)算法評(píng)價(jià)能力直觀單一思路多種算法策略轉(zhuǎn)變看懂直白題目厘清問題本質(zhì)轉(zhuǎn)變提升3種能力，完成3個(gè)轉(zhuǎn)變2.具體做法---上下結(jié)合，內(nèi)外延伸自主學(xué)習(xí)（課下xh）要點(diǎn)講解（課上60m）隨堂研討（課上25m）隨堂測(cè)試（課上5m）編程實(shí)踐（課下xh）提前給出學(xué)習(xí)內(nèi)容，課前反饋學(xué)習(xí)情況（集中反饋）：課前1天隨堂測(cè)試主要對(duì)自主學(xué)習(xí)內(nèi)容掌握情況進(jìn)行評(píng)估，成績(jī)計(jì)入平時(shí)成績(jī)編程實(shí)踐主要完成課后作業(yè)及課堂實(shí)踐針對(duì)實(shí)踐題目組織研討交流編程實(shí)現(xiàn)完成解題報(bào)告2.具體做法---怎么練在線評(píng)測(cè)系統(tǒng)和本地編程相結(jié)合569112471013812131415數(shù)字華容道：用盡量少的步數(shù)，盡量短的時(shí)間，將棋盤上的數(shù)字方塊，按照從左到右、從上到下的順序重新排列整齊。解題過程使用的方法是什么？設(shè)有n個(gè)城市，已知任意兩城市間距離不等，現(xiàn)有一情報(bào)員想從鄭州出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點(diǎn)，問如何找一條最短路徑。1.(2分)關(guān)于算法特征描述正確的有？A：

確定性B：

可行性C：

無窮性D：

有輸入E：

有輸出F: 有窮性2.(2分)分析算法的指標(biāo)有哪些？A：

正確性