算法設計中的若干前沿問題.pdf

1、在這篇論文中,我們詳細地研究了數(shù)據(jù)流模型、計算幾何、擴展圖理論和計算生物學領域中的若干算法設計的前沿問題.
　　 數(shù)據(jù)流模型是伴隨著互聯(lián)網(wǎng)技術和大規(guī)模數(shù)據(jù)庫的應用而日益受到重視的算法設計理論.自1996年N.Alon等人的開創(chuàng)性工作后,這一理論受到了廣泛的關注.在本文中,我們將探討如下三個問題:
　　 在區(qū)間有效的零次頻率矩估測問題的研究中,我們系統(tǒng)地改進了2002年Z.Bar-Yossef等人和2005年A.Pavan

2、等人的工作,給出了這一問題的目前最優(yōu)實現(xiàn)算法.依賴于數(shù)據(jù)流問題的規(guī)約技術,我們給出了最大支配范數(shù)的時間復雜度更低的算法.
　　 在XML流相關性的研究中,針對樹編輯距離這一測度的非直觀性,我們定義了兩個樹之間的Hamming測度這一直觀的比較方法.依賴于N.Nisan偽隨機數(shù)發(fā)生器理論和穩(wěn)態(tài)分布,我們給出了在數(shù)據(jù)流模型下計算這一測度的算法.實驗結果表明Hamming測度能夠很好地表示不同XML文檔的相似性.
　　 針對互

3、聯(lián)網(wǎng)應用中選舉問題的需要,并結合已有的冰川、頻繁出現(xiàn)元素等統(tǒng)計信息的局限,我們在第四章定義了真實冰川的概念.運用誤差函數(shù)、Count-Min摘要技術和Loglog計數(shù)摘要,我們給出了數(shù)據(jù)流模型下計算真實冰川的概率算法.
　　 論文的第二部分探討最小Manhattan網(wǎng)絡的計算復雜度和近似算法.這一問題于1999年由J.Gudmundsson等人提出.在那篇被廣泛引用的文獻中,J.Gudmundsson提出了這一領域的三個最重要的

4、問題:(1)這一問題是否是NP.完全的;(2)這一問題是否存在PTA$算法;(3)這一問題是否存在2-近似算法.
　　 在論文的第五章中,我們首次回答了J.Gudmundsson的第一個問題:最小Manhattan網(wǎng)絡問題是強NP-完全的.在同一章中,我們將詳細探討將3-SAT問題規(guī)約到最小Manhattan網(wǎng)絡問題的證明細節(jié).
　　 在第六章中,我們給出時間復雜度為O(nlogn)的2-近似最小Manhattan網(wǎng)絡構

5、造算法.與已有的基于動態(tài)規(guī)劃或線性規(guī)劃的2-近似算法相比,本章證明了貪心策略即可以給出問題的2-近似算法.
　　 在擴展圖這一部分中,我們分析Ramanujan圖的構造算法.基于Ramanujan猜想,G.A.Margtflis等人在二十世紀70年代首次運用數(shù)論的方法給出了譜擴展參數(shù)達到最優(yōu)的擴展圖——Ramanujan圖.此后的一系列構造大多基于高深的數(shù)論和拓撲理論.隨著理論計算機科學中退隨機和編碼理論的需要,人們希望運用組合

6、數(shù)學的方法構造任意正則的Ramanujan圖.在論文的第九章,我們首先定義了標準Z-積的一個自然推廣.其次,結合A.Ben-Aroya等人在2008年的工作,我們給出了構造近-Ramanujan圖的組合算法.
　　 本文的最后一部分考察了計算生物學領域中的DNA序列編碼問題.與傳統(tǒng)的編碼理論不同,DNA序列的編碼不僅需要滿足傳統(tǒng)意義上的Hamming距離約束,而且由于DNA序列需要滿足特定的熱力學性質等生物約束,從而使得對這一問