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

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

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

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