




已閱讀5頁,還剩1頁未讀, 繼續(xù)免費閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
一、 Please answer T or F for each of the following statements to indicate whether the statement is true or false1. An algorithm is an instance, or concrete representation, for a computer program in some programming language. ( F )2. The following problem is a Decision Problem: What is the value of a best possible solution? ( F )3. The dynamic programming method can not solve a problem in polynomial time. ( F )4. Assume that there is a polynomial reduction from problem A to problem B. If we can prove that A is NP-hard, then we know that B is NP-hard. ( F ) 5. If one can give a polynomial-time algorithm for a problem in NP, then all the problems NP can be solved in polynomial time. ( F )6. In an undirected graph, the minimum cut between any two vertices a and b is unique. ( F )7. Linear programming can be solved in polynomial time, but integer linear programming can not be solved in polynomial time. ( T )8. We can solve the maximum independent set problem in a graph with at most 100 vertices in polynomial time. ( T )結(jié)論9. If an algorithm solves a problem of size n by dividing it into two subproblems of size n/2, recursively solving each subproblems, and then combine the solutions in linear time. Then the algorithm runs in O(nlogn) time. ( T )10. Neural Computation, Fuzzy Computation and Evolution Computing are the three research fields of Computational Intelligence. ( T )二、 Given the following seven functions f1(n) = n5 + 10n4, f2(n) = n2 + 3n, f3(n) = 210000, f4(n) = logn + (2logn)3, f5(n) = 2n+n!+ 5en, f6(n) = 3log(2n) + 5logn, f7(n) = 2nlogn+lognn. Please answer the questions:(a) Give the tight asymptotic growth rate (asymptotic expression with q) to each of them; (7分)(b) Arrange them in ascending order of asymptotic growth rate。 (3分)參考答案和評分標準:a)(1) n5 + 10n4 = q (n5) (1分,非最簡表達式或?qū)懗蒓或W不符合題意,不給分)(2) n2 +3n = q (3n) (1分,標準同上)(3) 210000 = q (n0.75) (1分,標準同上)(4) logn + (2logn)3 = q ( (logn)3) (1分,標準同上)(5) 2n+n!+ 5en = q (n!) (1分,標準同上)(6) 3log2n + 5logn = q (n) (1分,標準同上)(7) 2nlogn+lognn. = q (nn) (1分,標準同上)b)f4 f3 f6 f1 f2 f5 f7 (3分,每個錯誤位置扣0.5分,扣完為止)三、 Please answer the following questions:(a)。四、 In the interval scheduling problem, we are given n jobs each of which has a starting time s and a finishing time f, and the goal is to find a maximum set of mutually compatible jobs (two jobs are compatible if they dont overlap). Please answer the following questions:(a) Design a greedy algorithm for the interval scheduling problem and prove the correctness of it. (b) Assume that we are given 8 jobs with starting time and finishing time (s, t) being (0,2), (1,3), (8,9), (3,7), (7,8), (2,4),(6,9), (4,5). Use your algorithm to find a solution to this instance. 參考答案及評分標準:a)將所有工作(jobs)按其完成時間的先后進行排序; 在排好序的序列中用彈性法則,以此選取最小完成時間且和前面已選工作不沖突的工作。 證明用反證法,假設(shè)貪心算法不是最優(yōu)導出矛盾,課件中有證明。證明思路大體正確即可給全分。 b)答案是 (0,2),(2,4),(4,5),(7,8),(8,9). 五、 Find a minimum s-t cut in the following directed graph (the number beside the edge is the capacity of the edge). You are required to give the computation steps and show the cut and its size. (9分)參考答案: 18. 評分標準:說明計算該圖從s到T的最大流 (2分)給出第一個和增廣路徑 (2分)后面任意兩個增廣路徑 (1分一個)最后答案 18和這個cut (3分,任給一個cut即可,最后結(jié)果18錯誤則不給分) 六、 Prove that if we can check if a graph has a clique of size k in polynomial time then we can also find a clique of size k in polynomial time (a clique of a graph is a complete subgraph ). 參考答案及評分標準:設(shè)檢查算法為B,我們構(gòu)造一個找到解的算法A,該算法多項式次調(diào)用B。 (1分)算法A的步驟和思想:依次從圖中刪除一個點,再調(diào)用算法B來檢查是否還存在大小為k的clique,如果存在則直接從圖中刪除這個點 (2分);如果不存在,則將這個點放入解集,同時將圖中所有不和這個點相鄰的點全刪除,再刪除這個點本身,在剩余的圖中再檢查是否存在大小為k-1的clique。(3分)以上思想正確給全分,其它正確解法也給全分。七、 We know that finding a longest path in a graph is NP-hard. Please show that finding a longest path that passing through a given vertex is also NP-hard. (6分)參考答案及評分標準:將最長路徑問題歸約到通過某個點的最長路徑問題。思想如下:對于每個最長路徑問題G,我們對圖G中每個點得到一個通過這個點的最長路徑問題,總共得到n(n為G中點的個數(shù))個問題,如果后一個問題存在多項式算法,則前一個問題也存在。以上思想正確給全分,否則最多給3分。八、 In a supermarket, there are n different types of goods for sale. Each type of goods has a price of dollars and a value of . Now you are asked to buy some goods such that: for each type of goods, at most 2 pieces are bought, the total value of the goods is at least V and the total money used is minium. Use a dynamic programming algorithm to solve the above problem. (a) Please define your subproblem; (b) Give the recurrence relation based on your subproblems; (c) Solve the following instance showed in Table 1 by using the bottom-up method, where V=10. You are required to give the computation steps (the table used to store the solutions to the subporblems).
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 宣傳推廣部管理制度
- 家具廠車輛管理制度
- 庫房配料員管理制度
- 張作霖家庭管理制度
- 彩票店臺賬管理制度
- 律師會見室管理制度
- 德克士崗位管理制度
- 快時尚門店管理制度
- 急救培訓證管理制度
- 總監(jiān)級薪酬管理制度
- 尿崩癥診療規(guī)范內(nèi)科學診療規(guī)范診療指南2023版
- 老年法律法規(guī)體系初識 老年服務(wù)與管理法律法規(guī)概述
- 民航服務(wù)溝通PPT完整全套教學課件
- 【地方政府促進鄉(xiāng)村旅游發(fā)展研究文獻綜述3600字】
- 某工業(yè)安裝工程設(shè)備監(jiān)理實施細則
- 西安市商品住宅使用說明書
- 西部科學城重慶高新區(qū)引進急需緊缺人才38人模擬檢測試卷【共1000題含答案解析】
- 湖南2022年事業(yè)編招聘考試《職業(yè)能力傾向測驗》真題及答案解析【最全版】
- GB 1903.27-2022食品安全國家標準食品營養(yǎng)強化劑低聚半乳糖
- 帶傳動教學課件
- 新護士五年規(guī)范化培訓手冊
評論
0/150
提交評論