算法設(shè)計(jì)中的若干前沿問題.pdf

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

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

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

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

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

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