中國科學(xué)院大學(xué)計算機學(xué)院計算機算法劉玉貴期末題庫習(xí)題答案-考試復(fù)習(xí)大綱2020

考試復(fù)習(xí)大綱常用函數(shù)的階、比較階的大小。了解算法設(shè)計、時間復(fù)雜度分析。了解：主定理證明、最接近點對、改進的劃分選擇算法貪心算法設(shè)計、正確性證明了解：單機作業(yè)調(diào)度算法的排序、改進算法，正確性證明；Huffman編碼證明。算法設(shè)計、最優(yōu)子結(jié)構(gòu)性質(zhì)證明了解：0/1背包優(yōu)化動態(tài)規(guī)劃算法，流水作業(yè)調(diào)度的Johnson改進算法；最優(yōu)二叉搜索樹最優(yōu)子結(jié)構(gòu)證明。讀懂算法、回溯算法設(shè)計。讀懂算法；掌握剪枝的技術(shù)、最小成本函數(shù)構(gòu)造。了解：博弈樹、TSP簡約矩陣計算檢索、比較問題下界(結(jié)論，了解證明)，證明一個問題∈NP,簡單的NP-C問題證明，如0/1背包問題，習(xí)題八之2、3、5，6（即Hamilton圈多項式變換到TSP問題）等。記住常見NP-C問題(不證明)。了解：判定問題與語言、圖靈機、除0/1背包問題外所有的NP-c證明?；靖拍?，看練習(xí)了解：素數(shù)判定算法基本概念、常見問題的可近似性結(jié)論(證明：了解)，多機調(diào)度的2(要求證明)或3/2近似算法、頂點覆蓋問題的近似算法、0/1背包問題近似算法（了解：近似算法的證明，除指明外）。了解：除上述，另加：子集和問題證明、集合覆蓋問題證明。鄰域、算法基本步驟、算法實現(xiàn)的關(guān)鍵技術(shù)問題(什么問題)了解：不要求記憶算法實現(xiàn)中關(guān)鍵技術(shù)問題的解決建議。說明：練習(xí)中打*的只要求了解，其它類似上述難度的練習(xí)只要求了解。要求了解的內(nèi)容基本不是考試內(nèi)容。經(jīng)典算法要求讀懂算法。怎么考察？如給一個算法要求改寫一、兩個地方；給出一個實例，畫出算法運行的解空間搜索樹、搜索過程；給出算法中關(guān)鍵操作的實現(xiàn)，如如何剪枝的？如何估計搜索成本的？等等。各章要求了解的內(nèi)容對理解各種算法設(shè)計思想是非常重要的內(nèi)容，如分治算法最接近點對問題和改進的劃分選擇算法，對理解分治技術(shù)的關(guān)鍵問題：如何減小子問題規(guī)模、如何降低合并子問題解難度是非常好的例子。這些對象，有的因為算法難度大一些，有的因為使用了特殊的數(shù)據(jù)結(jié)構(gòu)，有的因為使用了特殊技巧(如作業(yè)調(diào)度Johnson算法)，有的因為證明難度過大而被要求了解。但對于算法學(xué)習(xí)，切不可認為他們不重要，其實很多被劃掉的問題是精髓，請同學(xué)們將復(fù)習(xí)分成兩個層次：(1)算法設(shè)計與分析知識與能力的學(xué)習(xí)訓(xùn)練;(2)準(zhǔn)備考試。最近一周可偏重于考試復(fù)習(xí)，但對于因時間緊來不及全面復(fù)習(xí)、習(xí)題做得不夠充分的同學(xué)，希望試后把課程內(nèi)容全面復(fù)習(xí)一遍；所有同學(xué)，有些案例和習(xí)題，特別是啟發(fā)式算法，應(yīng)上機實現(xiàn)運行一下。考試結(jié)束了，算法學(xué)習(xí)不能結(jié)束！考試后作業(yè)：上機實現(xiàn)TSP的模擬退火算法，隨機生成一定規(guī)模的數(shù)據(jù)或用通用數(shù)據(jù)集比較其它人的結(jié)果，分析算法的性能，摸索實現(xiàn)中技術(shù)問題的解決。上機實現(xiàn)0/1背包問題的遺傳算法，同上。上機實現(xiàn)Lasvegas算法結(jié)合分枝限界算法解決電路板布線問題，分析算法性能。上述作業(yè)是自愿