計(jì)算機(jī)的計(jì)算能力ppt課件(參考版)
2025-05-06 07:14本頁面
【正文】 P=？ NP 1． P類問題 is in NP類問題： P ? NP 即 : P類問題一定也是 NP類問題； 2. NP類問題 is in P類問題？ NP ? P ?不知道！ 計(jì)算機(jī)理論假設(shè)： NP類問題 is not in P類問題！ 即 P≠NP 關(guān)鍵科學(xué)問題： 大量重要的生物組合計(jì)算問題是 NP難解問題 ? 生物數(shù)據(jù)的海量性（人類基因組包含超過三十億個堿基對）和生物結(jié)構(gòu)的復(fù)雜性 ? 生物結(jié)構(gòu)的多態(tài)性和生物數(shù)據(jù)的非精確性 ? 生物計(jì)算問題的高計(jì)算復(fù)雜性（大量重要的生物計(jì)算問題是NP難解問題） 傳統(tǒng)計(jì)算技術(shù)在生物計(jì)算中的局限性 ? 如何解決生物計(jì)算中的 NP難解問題已成為生物信息學(xué)中最重要的課題之一 ? 常規(guī)算法：無法克服高復(fù)雜計(jì)算 ? 近似算法：不能達(dá)到所要求的精度 ? 啟發(fā)式算法：無法保證計(jì)算問題的完成 ? 概率算法：無法確定生物數(shù)據(jù)的分布 研究思路 參數(shù)計(jì)算理論 生物基礎(chǔ)問題參數(shù)化模型 參數(shù)化算法設(shè)計(jì)與分析方法 生物軟件的開發(fā)與應(yīng)用 生物計(jì)算基礎(chǔ)問題 生物計(jì)算問題結(jié)果 生物計(jì)算問題參數(shù)化求解及應(yīng)用過程 生物基礎(chǔ)問題求解技術(shù)應(yīng)用 計(jì)算智能、數(shù)據(jù)挖掘 生物計(jì)算熱點(diǎn)問題 參數(shù)計(jì)算理論與技術(shù) 許多 NP難解問題在實(shí)際應(yīng)用中存在一個在小范圍中變化的參數(shù) k ，對這類問題，我們尋求時間復(fù)雜度為 f(k)nc 的算法 ? 這種算法不違反 P ? NP 的假設(shè) ? 有這種算法的問題稱為 小參數(shù)可解 的 ? 當(dāng) k 值較小時， 小參數(shù)可解 算法是實(shí)際可行的 ? 沒有這種算法的問題稱為 小參數(shù)難解 的（為計(jì)算難解性研究提供了新技術(shù)） n k nc f(k) input putation time output 參數(shù)計(jì)算理論與算法技術(shù) 在生物計(jì)算中的應(yīng)用 ? 生物問題數(shù)學(xué)建模中引入?yún)?shù) ? 許多生物計(jì)算問題中所含參數(shù)的值只在小范圍中變化 ? 避開 NP難解問題的困境 例：當(dāng) n = 106, k = 60 時 , 常規(guī)算法時間復(fù)雜度： nk = 10360 參數(shù)算法時間復(fù)雜度： +n ? ? 實(shí)際有效的精確算法解決生物計(jì)算問題 。 ?難解的問題！ 比如： SAT, VC, CLIQUE, IS, TSP, ……… ?不可解的問題！ 即：任何計(jì)算機(jī)不論耗費(fèi)多少時間也不能解的問題。 設(shè) f = 1%, p =∞，則 Acc_Speed =100 結(jié)論：一個問題的求解若有 1%的串行度，則 無論有多少臺計(jì)算機(jī)并行計(jì)算 ，其計(jì)算速度至多是單臺計(jì)算機(jī)計(jì)算同一個問題的 100倍！ 易難 /難解 /不可解問題 從時間復(fù)雜性分析來說，許多問題的算法時間復(fù)雜性是 O(nc)的，其中 n是問題的規(guī)模， c是常量。 算法： //給定圖 G =V,E,其中 |V| =n， |E| =m 第一步：枚舉出 V中所有的子集： 子集總數(shù) = (n1) + (n2) +(n3) +…+ (nn) =2n 第二步：判斷每個子集是否是圖 G的頂點(diǎn)覆蓋：for i =1 to m do…… 算法時間復(fù)雜性： O(2n*m) ?可計(jì)算否？ 例 : ? 假設(shè) n=56, 在一臺運(yùn)行速度為 億次級每秒的計(jì)算機(jī)里用枚舉法求解 VC問題，須花時多少？ ? 計(jì)算：我們假設(shè)該機(jī)器每秒鐘可判斷一億種的方案是否正確！則有： ? 2^56種方案 /1億種每秒 /60/60/24/365 =(年 )！ 結(jié)論：對于 O(2n)的算法，當(dāng) n足夠大時，全世界現(xiàn)有的計(jì)算機(jī)都無法在可接受的時間內(nèi)求解。 ? Give k DNA sequences,find a pattern of length 15 that is similar to a subsequence in each sequence. ? Give a kpartile graph,find a set of vertices,one from each row,such that all these k vertices are connected.（ 最大團(tuán)） ? 計(jì)算量為 nk=202220NPhard! ? 改進(jìn)： n5Xn5=n10 2n10 =4n5 n5Xn5=n10 5行 n5 5行 5行 n5 5行 是不是什么問題都是單計(jì)算機(jī)可解的？ 例一：求圖 G的最小頂點(diǎn)覆蓋問題： 問題描述：無向圖 G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集 V的一個子集 V’ ? V， 使得若 (u,v)是 G的一條邊，則 v∈ V’或 u∈ V’。 ? 子串相似性的定義：在串中間插、刪、改的次數(shù)不超過 6次，使得兩個子串相同。 – 在圖中找到 60個點(diǎn)后就沒有邊了，系統(tǒng)可用 – 如果超過 60個點(diǎn)還有邊，系統(tǒng)不可用 ? 問題等價于： Give a graph ,can you find 60 vertices whose remove makes the graph has no edge? ? Vertex cover(點(diǎn)覆蓋 ):Give a graph, can you find k vertices such that each edge has at least one end in these k vertices? ? 另一種說法： ? Give a graph G of n vertices , decide if there are k vertices whose remove makes the graph edgeless. ? Try any subset of 60 vertices and check if it make a vertex cover(點(diǎn)覆蓋 ) ? 圖中每 60個點(diǎn)拿出來試一試：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1