仕事・時間量について最適なPRAM上のkマージアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
要素数が合計がnのソートされたk個の列をマージして新しいソート列を求める問題をkマージ問題と呼ぶ。本論文では、単純で仕事・時間量が最適な3つのPRAM上のkマージ問題を解くアルゴリズムを示す。まず、EREW-PRAM上で、O(logn)時間で仕事量がO(nlogk)のkマージアルゴリズムと、CREW-PRAMとCRCW-PRAM上でO(loglogn+logk)時間で仕事量がO(nlogk)のkマージアルゴリズムを示す。また、これらのアルゴリズムが仕事量がO(nlogk)である限り、高速化はできないことを示す。
- 一般社団法人情報処理学会の論文
- 1996-09-13
著者
-
林 達也
京都大学大学院人間・環境学研究科
-
林 達也
名古屋工業大学電気情報工学科
-
中野 浩嗣
北陸先端科学技術大学院大学情報科学研究科
-
中野 浩嗣
北陸先端科学技術大学院大学
-
中野 浩嗣
名古屋工業大学電気情報工学科
-
オラリウ ステファン
オールドドミニオン大学 計算機科学科
-
オラリウ スラファン
オールドドミニオン大学 計算機科学科
-
林 達也
名古屋工業大学大学院情報工学専攻
関連論文
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 教育用・小規模組込みシステム用の超小型プロセッサと言語処理系
- 生体のゆらぎ現象から心身相関を探る : 心拍変動から評価した自律神経活動動態と月経前症候群・月経前不快気分障害との関連(第6回池見賞受賞論文)
- 小型組込みシステムと教育のためのFPGA向けTiny Processing System(応用2)
- COMP2000-24 マルチホップパケット無線ネットワーク上のブロードキャストの確率アルゴリズム
- FPGAを用いたコラッツ予想の検証(応用3)
- 長期間の経過観察が可能であった先天性脂肪萎縮性糖尿病の1例
- ヒト4型メラノコルチン受容体(MC4R)の新規遺伝子異常により発症した肥満症
- SLEの増悪に伴って著明な高トリグリセライド血症を呈した一例 抗リポ蛋白リパーゼ抗体による自己免疫性 高トリグリセライド血症が疑われた症例の病態に関する考察
- 不明熱と高血圧を合併した肥満症の一例 - 高レプチン血症の意義に関する考察 -
- ロジックエレメントを節約したFPGAラベリング(応用1)
- FPGAを用いたk-Concaveな二値画像に対するラベリング
- 2. 老化および不活動が骨格筋の乳酸生成・輸送・酸化能力に与える影響について(第22回日本体力医学会近畿地方会)
- 運動時におけるリアルタイムでの心拍変動解析に基づく至適運動強度の決定
- 405. 椅子座位から立位へ段階的に強度を上げた介護予防事業における運動教室の効果について(生活・健康,第62回日本体力医学大会)
- ゆらぎの科学と女性心身医学 : 月経周期に伴う心とからだの変化と自律神経活動との関連(Niles Newton-Award受賞講演,第15回国際女性心身医学会および第36回日本女性心身医学会学術集会報告)
- 1.若年女性における月経周期に伴う心身不快症状と自律神経活動動態との関連(シンポジウム 日本における女性心身医学の現況,2006年国際サイコセラピー会議イン・ジャパンおよび第3回アジア国際サイコセラピー会議)
- 1.月経前症候群の発現に関与する生理・心理学的要因 : 黄体後期における自律神経活動動態と不定愁訴との関連(パネルディスカッション,第39回 日本心身医学会近畿地方会演題抄録,地方会抄録,学会報告)
- 1-3 黄体後期における自律神経活動動態と身体的・精神的不快症状との関連(第1群)(第31回日本女性心身医学会学術集会)
- 518.筋電気刺激を利用した生活習慣病治療の可能性
- 有酸素運動における脳波・血中β-エンドルフィンの動態
- 7. 自律神経ブロックが脚運動開始時の換気応答に及ぼす影響
- 51.低酸素吸入による神経筋活動の変化
- D-8-19 情報取得能力の多様化による複数種生物の共存と進化の研究
- カラーペトリネットによるオブジェクトマイグレーションの振舞いモデリング
- ニューラルネットワークを用いた作曲支援
- 仮想世界, 仮想生物を用いた越冬, 冬眠に関する研究
- 多面的オブジェクトに対するオブジェクトマイグレーションの枠組み
- ペトリネットによるオブジェクトマイグレーション振舞いモデリング
- ニューラルネットを利用した日本語係り受け解析 : 係り受け解析の数値問題としての取扱いについて
- 多面的オブジェクト指向データモデルMAORI
- 実体の多面性を表現するためのデータモデル
- 多面的オブジェクト指向データベースにおけるオブジェクトマイグレーションの枠組み
- オブジェクト指向データモデルGROOM-IIにおける属性文法によるメソッドの形式化
- エージェントモデルによるオブジェクトの多面性表現
- 多面的オブジェクト指向データモデル
- 共同文書作成支援システムについての考察と実装
- エージェントを用いたオブジェクトの多面性表現に関する一考察
- ニューラルネットワークを用いた日本語係り受け解析
- ニューラルネットに基づく日本語係り受け解析
- ニューラルネットに基づく日本語係り受け解析
- Xilinx Virtex-5 FPGAのDSP48Eブロックを用いたコラッツ予想の検証の効率的実装(システムアーキテクチャ)
- FPGAを用いたCKYパージングの高速化
- シングルホップ・シングルチャネル無線ネットワーク上の時間と電力消費について最適な確率的ルーティング
- シングルホップ無線ネットワーク上の省電力初期化アルゴリズム
- ワイヤレスセンサーネットワーク上の基本プロトコル
- ワイヤレスセンサーネットワーク上の省電力初期化アルゴリズム
- アドホック無線ネットワーク上の省電力初期化アルゴリズム
- マルチホップパケット無線ネットワーク上のブロードキャストの確率アルゴリズム
- COMP2000-25 アドホック無線ネットワーク上の省電力初期化アルゴリズム
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- FPGAのDSPブロックを最大限利用するRSA暗号ハードウェアアルゴリズム(一般:情報通信基礎サブソサイエティ合同研究会)
- COMP2000-23 マルチスレッドアーキテクチャへの高級言語を用いた並列アルゴリズムのインプリメント
- PRAMアルゴリズムのマルチスレッドアーキテクチャへのインプリメントと評価
- 再構成メッシュ上の並列アルゴリズムの視覚化ツール
- 再構成メッシュ上でO((loglog n)^2)時間で凸包を求めるアルゴリズム
- 重みのある場合とない場合に, k 個のソートされた列に対する選択問題を解くアルゴリズム
- エージェントモデルEAMMOとその記述言語に関する一考察
- 近接点を見つける最適な並列アルゴリズムとその応用
- 組合せ論理回路に対するイベント駆動による再評価
- 11.筋出力伝達におけるミオシン重鎖アイソフォーム組成比と筋細胞膜タンパクとの関わり(一般講演,第21回日本体力医学会近畿地方会)
- 肥満症の運動療法
- 座位を基本とした有酸素運動・レジスタンストレーニングの臨床的有用性(ファストスポーツからスロースポーツへ)
- 肥満症運動療法に何を期待するのか : 有酸素運動vs. レジスタンス運動
- 運動による骨格筋 5'AMP-activated protein kinase 活性化と糖取り込みの促進
- 多面的オブジェクト指向データベースにおけるオブジェクトマイグレーションの枠組み
- 復元画像の最適化によるハーフトーン化 : ハードウェアによる高速化を含めた新しい手法
- さまざまなスクリーニング法 (特集:プリンティング・テクノロジー2008)
- Juraj Hromkovic, 和田幸一, 増澤利光, 元木光雄 訳, 計算困難問題に対するアルゴリズム理論, Algorithmics for Hard Problems, シュプリンガーフェアラーク東京, 2005年
- FPGAを用いた画像検索システム
- FPGAを用いた画像検索システム
- kチャンネル放送通信モデル上の時間と消費電力について最適なリストランキングアルゴリズム
- 無線ネットワーク上のユニフォームなリーダ選択プロトコル
- 衝突検出のない無線ネットワーク上のリーダ選択プロトコル
- 衝突検出できない無線ネットワーク上の省電力初期化プロトコル
- 動的可変バスをもつ並列計算機上の定数時間アルゴリズム
- 二分決定木を用いた論理関数の質問処理
- 仕事・時間量について最適なPRAM上のkマージアルゴリズム
- 基本再構成メッシュ上の行最小値計算のための効率よいアルゴリズム
- An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh
- 急性運動時の内分泌代謝変動 : 分子生物学的観点より ; 運動による骨格筋糖取り込み速度増強の機序
- 生活習慣病改善のためのチェア・エクササイズ「すわろビクス」
- 生活習慣を改善しなくてよい時代が来てほしい
- 筋電気刺激(EMS)を利用した生活習慣病改善の可能性
- マルチスーパースカラパイプラインによるブロック並列実行方式
- スーパースカラパイプラインによるブロック並列実行方式
- ニューラルネットワークを用いた作曲支援
- 共同文書作成支援システムの研究
- FFT向け並列計算機
- 糖尿病の運動療法 : 3. レジスタンストレーニングの位置づけ
- An FPGA Implementation for 3-layer Perceptron with the FDFM Processor Core Approach (リコンフィギャラブルシステム)
- バリア同期付き非同期メモリマシンモデル
- バリア同期付き非同期メモリマシンモデル
- SF-025-4 肝細胞癌切除後再発予測因子としてのcytoskeleton associated protein 2の検討(SF-025 サージカルフォーラム(25)肝 基礎-1,第112回日本外科学会定期学術集会)
- FDFMアプローチを用いた3層パーセプトロンのFPGA実装(数値計算と高速化)
- オブジェクト指向データモデルのメソッドに対する属性文法による形式化
- 文法表現によるオブジェクト指向データモデル
- GPU向けメモリマシンモデル上の最適な並列接頭部和アルゴリズム(GPGPU,2012年並列/分散/協調処理に関する『鳥取』サマー・ワークショップ(SWoPP鳥取2012))
- FPGAのDSPブロックとブロックRAMを用いたハフ変換の実装(ハードウェア,クラウド、ネットワーク及び一般)