選択問題の面積時間複雑度
スポンサーリンク
概要
- 論文の詳細を見る
選択問題は,n個の整数の集合の中でl番目に小さな要素を見つける問題である。逐次計算モデルの上では, ソーティングに較べ選択問題は真に少ない計算量で解けることが知られている。ここでは,VLSIモデル上での選択問題の面積時問複雑度について考え,並列計算においても選択問題がソーティングよりも少ない計算量で解けることを示す。
- 一般社団法人情報処理学会の論文
- 1986-10-01
著者
関連論文
- 連想メモリを利用したハードウェア向き単一化アルゴリズム
- 連想メモリを利用した高速単一化アルゴリズム
- 入力制約監視機能をもつ会話型シミュレーション・システムISS
- 同期式順序回路の機能情報抽出について
- FINES:組合せ回路の機能情報抽出システム
- 算術演算回路の機能情報抽出
- 論理関数のグラフ表現を利用した組合せ回路の機能情報抽出
- 入力制約を用いた論理回路の形式的検証について(計算機科学の基礎理論)
- 記憶階層のもとでの結合操作について (数理情報科学の基礎理論と応用)
- 40. VLSI用の正規集合認識法 (アルゴリズムの最近の動向)
- ハードウェアアルゴリズムの記述法について (形式言語理論とオートマトン理論)
- ベクトル計算機上でのソーティング手法
- 組合せ論理回路のハザード検出問題の計算複雑さについて(計算アルゴリズムと計算量の基礎理論)
- 選択問題の面積時間複雑度
- UDL/Iのセマンティクス定義に基づく処理系の試作
- 論理シミュレーションの精度に関する考察
- ハードウェア記述言語の厳密な意味定義のための非決定的動作モデルシミュレータの試作
- 4. 各種のハードウェアアルゴリズム 4.2 ソーティングのハードウェアアルゴリズム : VLSIモデル上での計算複雑度 (VLSI向きハードウェアアルゴリズム)