バタフライネットワークによる確率的な選択ネットワーク

• Item type: SIG Technical Reports(1)
• 公開日: 1993-05-28
• タイトル: バタフライネットワークによる確率的な選択ネットワーク
• タイトル / 言語: en
• タイトル: A PROBABILISTIC SELECTION NETWORK WITH BUTTERFLY NETWORKS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学理学部情報科学科
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, The University of Tokyo
• 著者名: 池田, 崇博
• 著者名(英): Takahiro, Ikeda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 選択・整列ネットワークの分野では、これまでに大きさO（ log ）・段数O(g ）のものが発表されている。しかし、それらは存在性のみを考慮したものばかりであり、比例定数がかなり大きかった。最近になって、実装の容易なバタフライネットワークを用いた段数7．44log n+O(g log ）の確率的な整列ネットワークが発表された。これは確率アルゴリズムの概念に添って構築されており、注目に値するものである。本研究はとの手法を選択ネットワークに適用し、大きさ0．5n log n+O（^<0．822>log ）・段数5．62log n+O(g log ）の確率的な選択ネットワークを構築する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Selection and sorting networks with size O(n log m), depth O(log n) have been proposed. However, only their existence is considered in their construction and their constant factors of size and depth bound are enormous. Recently, a probabilistic sorting network with small 7.44log n+O(log log n) based on the utilization of butterfly networks which can be easily implemented has been proposed. This network is remarkable in the point that it is constructed along the concept of probabilistic algorithms. This paper constructs a probabilistic selection network with size 0.5n log n+O(n^<0.822>log n) and depth 5.62log n+O(log log n) with applying the same approach of above research.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 48(1993-AL-033), p. 41-48, 発行日 1993-05-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会