文献

J-GLOBAL ID：200902231729671073   整理番号：09A0289515

ツリーに関する第三準同形定理 下向きと上向きが分割統治に導く

The Third Homomorphism Theorem on Trees: Downward & Upward Lead to Divide-and-Conquer

著者 (4件)： MORIHATA Akimasa (Univ. Tokyo) ,  MATSUZAKI Kiminori (Univ. Tokyo) ,  HU Zhenjiang (National Inst. of Informatics) ,  TAKEICHI Masato (Univ. Tokyo)
資料名： ACM SIGPLAN Notices (Association for Computing Machinery. Special Interest Group on Programming Languages)  (ACM SIGPLAN Notices (Association for Computing Machinery. Special Interest Group on Programming Languages))
巻： 44  号： 1  ページ： 177-185  発行年： 2009年01月 
JST資料番号： D0915A  ISSN： 0362-1340  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Gibbonsの第三準同形定理は,もし2つの逐次プログラムが同じリストを左向きと右向きにそれぞれ繰り返し,同じ値を計算するならば,同じ値を逐次プログラムとして計算する分割統治並列プログラムが存在することを述べている。リストに関する研究は多数報告されているが,ツリー上の並列プログラムを特性化,開発する研究はほとんどない。本論文では,2つの逐次プログラムがツリー上のスケーラブルな分割統治並列プログラムを誘導する,体系的な構築方法を開発した。リストに関する多数の研究が活用できるように,ツリーよりはパスに注目し,結合則がツリー上のスケーラブルな分割統治並列プログラムに対する良い特性化を与えることを実証した。さらに第三準同形定理を,リストからツリーに一般化した。この結果は,すべての多項式データ構造に対し良好に成立する。

シソーラス用語： シーケンシャル処理 ,  計算機プログラム ,  ツリー構造 ,  準同形写像 ,  分割統治法 ,  スケーラビリティ【計算機】 ,  データ構造 ,  キャラクタリゼーション ,  プログラム変換 ,  *関数プログラミング ,  存在性 ,  二分木
準シソーラス用語： *並列プログラミング ,  リスト構造

分類 (1件)： 計算機システム開発  (JD02010R)

タイトルに関連する用語 (2件)： 定理 ,  統治