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

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

(5%)+編程實踐

(20%)5.考核評價加入平時成績的構(gòu)成圖示■

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

編程實踐■

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

確定性B：

可行性C：

無窮性D：

有輸入E：

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

正確性