中國科學院大學計算機學院計算機算法劉玉貴期末題庫習題答案-考試復習大綱2020

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