Abstract
廣播通訊模式乃是由一些處理器及通訊用的通道所組成。如果僅有一個通道，則稱為單通道廣播通訊模式；若有超過一個以上的通道，則稱為多通道廣播通訊模式。在此篇論文中，我們探討究竟有哪些問題可於此種模式之下解決。我們提出了幾個計算方法來解決圖形問題及排序問題。在單通道模式之下，我們解決了下述的圖形問題：t-opological ordering ，critical path ，connected component ，breadth-firstsearch，breadth-first spanning tree ，depth-fist search ，depth-first spa-nning tree ，cutpoint，bridge，biconnected component ，fundamental cycle，Iowest common ancestor，minimum spanning tree 。解決minimrm spanning tre-e 的計算方法，在使用n 個處理器的情況下，平均而言，需要O （n ）個成功的廣播。其他所有的計算方法，在使用n 個處理器的情況下，都需要O （n ）個成功的廣播。在單通道廣播通訊的模式之下，我們提出了一個最佳無碰爭的排序方法，於使用 p個處理器對n 個數字做排序的情況下，費時O （n╱p）log （n╱p）＋n ）。於多通道廣播通訊模式之下，我們也提出國一個無碰爭的排序方法，假設有k 個通道及p 個處理器對n 個數字做排序，在此情況下，此方法費時O （n╱p）log （n╱p）＋（ n╱k ）log□k）。