サイズが8n log 2 nで深さがO (log n) のセレクション・ネットワーク

• Item type: SIG Technical Reports(1)
• 公開日: 1990-09-28
• タイトル: サイズが8n log 2 nで深さがO (log n) のセレクション・ネットワーク
• タイトル / 言語: en
• タイトル: Selection Networks with 8n log 2 n Size and O (log n) Depth
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学工学部
• 著者所属: 東北大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tohoku University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Tohoku University
• 著者名: 神保秀司; 丸岡, 章
• 著者名(英): Shuji, Jimbo; Akira, Maruoka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n個の要素の中の小さい方からn/2番目までの要素を選び出すコンパレータ・ネットワークの効率的な構成方法を示す．コンパレータ・ネットワークとは，2つの要素を大きさの順に並べ換える比較素子から構成される回路である．これまでに，O（ log ）サイズでO(g ）深さのコンパレータ・ネットワークが既に得られている．この結果は，ソーティング・ネットワークはコンパレータ・ネットワークでもあるので，[AKS83b][AKS83a]のO（ log ）サイズでO(g ）深さのソーティング・ネットワークより直ちに得られる．この論文では，8n log_2 nサイズでO(g ）深さのコンパレータ・ネットワークを構成する．このネットワークは，[AKS83b][AKS83a]の構成と比較して構成がより単純でかつサイズの係数が大幅に改良されたものである（[AKS83b][AKS83a]の構成を改良した回路[Pat]でも係数が1000は下らないことが知られている）．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Selection networks, consisting of comparators, that select n/2 smallest elements from n inputs are investigated, and such networks with 8n log_2 n size and O(n log n) depth are constructed. This result improves [AKS83b][AKS83a] in constant factor of size and in simplicity of construction, and [Pip90] in order of depth, in which selection networks with 2n log_2 n size and O((log n)^2) depth are constructed.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 79(1990-AL-017), p. 105-114, 発行日 1990-09-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会