跳到主要內容

臺灣博碩士論文加值系統

(44.200.194.255) 您好!臺灣時間:2024/07/22 00:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蘇德宙
研究生(外文):Su, Te Chou
論文名稱:在平行環境下探討堆積結構的運算
論文名稱(外文):Manipulating a Heap in Parallel
指導教授:王家祥
指導教授(外文):Wang, Jia Shung
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1994
畢業學年度:82
語文別:中文
中文關鍵詞:堆積平行演算法理論下界
外文關鍵詞:HeapParallel algorithmLower bound
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著電腦硬體技術的突飛猛進及高速計算的需求,一部擁有多個微處理機
的電腦或是分散式系統已從理論中的環境漸漸變為實際可行,而平行演算
法的重要性正因為它是在此種環境下發展軟體的基礎。本篇論文將在
PRAM (Parallel Random Access Machine) Model 下探討有關堆積(Heap)
結構上的一些運算。堆積(Heap)結構在演算法中佔有極為重要的角色,在
此結構中,無論是加入資料或是從結構內的資料中找尋極值的問題,基本
上它都提供了非常有效率的方法。因此,無論在圖形演算法,排序或搜尋
的問題上常常利用此一結構而達到高效率的演算法。故其重要性是不可忽
略的。在本篇論文中,我們將會探討數個運算的演算法並證明其執行時間
的理論下界(Lower bound)。假設在一個堆積 (Heap)中有n 個元素,對傳
統從堆積(Heap)中加入或刪除一個元素的運算而言,我們在 CREW 和
EREW PRAM上提出了執行時間分別為θ(1)和θ(loglogn)的演算法。除了
傳統的運算外,我們也討論如何從堆積(Heap)中同時加入 r個元素與刪除
其值落在某一個範圍 (l,u)內的元素。在堆積(Heap)中加入 r個元素的運
算中,我們提出了在 CREW PRAM 上執行時間為θ(logr) 的演算法並且其
成本(Cost)為 O(rlogr+logn)。針對刪除某個特殊範圍,也就是其值小
於 u,內的元素的運算,我們提出的演算法可以在θ(logr+loglogn)的時
間內完成,並且其成本(Cost)為 q(n),其中r是將被刪除的元素並且 r
小於 n/logr。除此之外,我們在 CREW PRAM下證明了若針對一般範圍中
刪除元素的運算其執行時間的下界(Lower bound)是 Ω(logn),這時間相
當於重建一個堆積 (Heap) 所花的時間。因此,我們只好在 CRCW PRAM
上討論此一運算了。在此環境下,我們提出一個時間為 O(logr+loglogn)
而其成本(Cost)為 θ(n)的演算法,其中 r 是將被刪除的元素並且 r 小
於 n/logr。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top