基于二分技術(shù)的高效算法設(shè)計(jì)及其應(yīng)用.pdf

1、隨著計(jì)算方法的發(fā)展，幾乎所有的學(xué)科都走向定量化和精確化，從而產(chǎn)生了諸如計(jì)算數(shù)學(xué)、計(jì)算物理、計(jì)算生物學(xué)等一系列的計(jì)算科學(xué)。計(jì)算科學(xué)的發(fā)展促進(jìn)了學(xué)科之間的交叉和滲透，從而促進(jìn)了各個(gè)學(xué)科的發(fā)展，但各個(gè)學(xué)科的復(fù)雜性和非線性特征也日益明顯。復(fù)雜性科學(xué)與復(fù)雜系統(tǒng)研究逐漸成為熱點(diǎn)。演化分析是探索復(fù)雜科學(xué)的基本手段。王能超教授的一系列工作表明，二分技術(shù)可以刻畫自然演化的基本特征和機(jī)制，是演化分析的基本模式，是研制高效算法的強(qiáng)大平臺(tái)。本論文目的在于探討二

2、分技術(shù)在探索復(fù)雜性科學(xué)及高效算法設(shè)計(jì)中的應(yīng)用，考察了計(jì)算科學(xué)領(lǐng)域三類重要的復(fù)雜系統(tǒng)：Walsh函數(shù)系統(tǒng)，分形幾何以及生物信息學(xué)。 研究了Walsh函數(shù)系統(tǒng)理論，以Hadamard變換為例子，設(shè)計(jì)了二維Walsh變換的一個(gè)快速算法，其性能明顯優(yōu)于行列算法。 設(shè)計(jì)了空間填充曲線的三種算法：幾何算法，代數(shù)算法及幾何代數(shù)混合算法。基于演化思想，幾何算法通過(guò)基本元素的確定、變換和組合三個(gè)步驟完成了Peano空間填充曲線的生成。代數(shù)

3、算法將曲線數(shù)字化，采用矩陣復(fù)制方法，完成了Hilbert曲線的繪制，并進(jìn)一步應(yīng)用于基于Hilbert序的編碼解碼，使得該編碼解碼算法的時(shí)間復(fù)雜度小于相關(guān)算法且有更寬廣的適用范圍。混合算法考慮了Hilbert曲線的幾何特征，利用輔助代數(shù)矩陣完成了曲線的繪制，該算法比經(jīng)典的L系統(tǒng)算法提高了將近1倍的速度?；诖鷶?shù)算法的思想，對(duì)Hilbert曲線向三角域作了推廣。 通過(guò)對(duì)含有概率的迭代函數(shù)系統(tǒng)(IFS)的仿射變換系數(shù)進(jìn)行改造，將IFS