二叉樹旋轉(zhuǎn)和DFA化簡并行算法的研究.pdf

1、由于計算機硬件的元器件、集成度、工藝和體系結(jié)構(gòu)的發(fā)展幾乎到了極限,因此,并行處理技術(shù)成為提高計算機性能的重要手段。并行程序設(shè)計和并行編譯技術(shù)是并行處理技術(shù)的關(guān)鍵,所以并行數(shù)據(jù)結(jié)構(gòu)、并行編譯和優(yōu)化技術(shù)成為計算機科學與理論研究領(lǐng)域重要研究課題之一?；诰仃嚹Ｐ捅硎镜腄FA的極小化和二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法是編譯系統(tǒng)和數(shù)據(jù)結(jié)構(gòu)中的關(guān)鍵技術(shù)。本課題主要研究基于矩陣模型表示的DFA的并行化簡和二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法的并行處理。這些工作對并行計算理論、并行數(shù)

2、據(jù)結(jié)構(gòu)算法設(shè)計研究有一定的理論和實踐意義。
　　 本文首先敘述了與本課題研究有關(guān)的基礎(chǔ)理論以及相關(guān)并行模型和并行數(shù)據(jù)結(jié)構(gòu);重點做了兩方面的研究:其一,對PRAM模型下二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法進行較為深入的研究、提出了一種PRAM模型下二叉樹旋轉(zhuǎn)轉(zhuǎn)換算法的并行處理方法。其基本思想是:引入層次矩陣,通過對二叉樹和層次矩陣的等價轉(zhuǎn)換,把對二叉樹的操作轉(zhuǎn)換成對層次矩陣的操作;由于對矩陣的并行處理技術(shù)已經(jīng)非常成熟,所以借助矩陣這個“橋梁”,最終