リスト上の最大マーク付け問題を解く並列プログラムの導出
スポンサーリンク
概要
- 論文の詳細を見る
最大マーク付け問題とは,入力として与えられたデータに対し,ある記述を満たし,かつ,重み和が最大となる要素集合を求める問題である.多くの最適化問題は最大マーク付け問題として定式化できることが知られている.本稿では,このうち,データがリスト構造を持つ場合を対象とする.リスト上の最大マーク付け問題の例としては,最大部分列和問題なとが知られている.本稿では,最大マーク付け問題における述語の仕様から並列プログラムを導出する手法を提案する.並列プログラムの導出においては,並列計算においてよく利用される処理を抽象化した並列スケルトンを利用する.並列スケルトンを用いた並列プログラムの導出法についてはこれまでにも多くの研究がなされており,それらを利用する.本稿ではさらに,述語の仕様から並列プログラムのコードを生成するシステムについても述べる.
- 一般社団法人情報処理学会の論文
- 2008-03-15
著者
-
胡 振江
東京大学大学院情報理工学系研究科
-
武市 正人
東京大学大学院情報理工学系研究科
-
胡 振江
国立情報学研究所アーキテクチャ科学研究系
-
武市 正人
電気通信大学電気通信学部計算機科学科
-
武市 正人
東京大学
-
武市 正人
東京大学工学部
-
松崎 公紀
東京大学大学院情報理工学系研究科
-
Takeichi Masato
Department Of Mathemetical Engineering And Information Physics Faculty Of Engineering University Of
-
Takeichi Masato
Department Of Computer Science The University Of Electro-communications
関連論文
- 少数キーを用いた日本語入力
- 3M-5 Bidirectional XML Transformation with Bi-X
- 3M-4 依存関係記述スキーマによる双方向XMLアプリケーションの開発(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 3M-3 双方向変換に基づくウェブパブリッシング支援システムVu-X(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 神経系の双方向マルチスケールシミュレーションと100時間ワークショップ : 東京大学21世紀COEプログラム「情報科学技術戦略コア」
- 2. 情報科学技術戦略コア(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 情報科学技術戦略コア
- 5-2-1 東京大学「情報科学技術戦略コア」(5-2 情報・電気・電子分野の21世紀COE,3プロジェクトの拠点リーダーより)(5.大学での研究プロジェクト : 21世紀COEプログラム)(グローバル化時代の教育と研究)
- 1.マルチコア計算機と基本的な並列化技法(マルチコアを活かすお手軽並列プログラミング)
- インターネットを用いた複数経路データ伝送方式の性能評価
- 「計算機科学」は死語?
- 4.並列計算パターン(スケルトン)による並列プログラミング(マルチコアを活かすお手軽並列プログラミング)
- モデル検査技術を利用したプログラム解析器の生成ツール
- 並列プログラムの候補生成と適合性検査による並列化
- 多地点テレビ会議における通信品質のばらつきが主観品質に及ぼす影響
- 複数経路を用いてIPパケット転送するマルチルートゲートウェイの実装と評価
- 5U-2 複数経路を用いてIPパケット転送するマルチルートゲートウェイの実装と評価
- 5U-1 TCP/IPパケットを複数経路に分配して通信する方式の性能評価
- B-11-2 複数のTCP通信にDRRを適用する場合の通信品質の評価
- B-11-1 最低保証帯域を設定したTCP通信品質の評価
- B-7-51 複数経路を用いたTCP通信に関する一検討
- B-11-14 電子商取引に帯域制御を適用する場合の通信品質の検討
- B-7-78 インターネットを用いた複数経路データ転送方式に関する一検討
- IPパケット損失がMPEG1音声・画像品質に及ぼす影響の評価
- IPパケット損失がMPEG1音声・画像品質に及ぼす影響の評価
- MPEG1総合品質に対する音声パケット損失及び画像フレムレートの影響の評価
- IPパケット損失がMPEG1画像品質に及ぼす影響の評価
- TCP通信を帯域保証する場合の問題点の分析
- TCP通信を帯域保証する場合の問題点の分析
- TCP通信を帯域保証する場合の問題点の分析
- 複数のTCP通信にWFQを適用する場合の通信品質の検討
- TCP通信を帯域保証する場合の問題点の分析
- 補関数の生成による複製機能付きプログラムの自動双方向化
- 6.双方向変換による高信頼構造化文書処理(第1部:高い生産性を持つ高信頼ソフトウェア作成技術の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- Generator-of-generators に基づく Fortress ライブラリ
- リスト上の最大マーク付け問題を解く並列プログラムの導出
- 木スケルトンによるXPathクエリの並列化とその評価
- 東京大学 情報理工学系研究科 創造情報学専攻の紹介(ラボラトリー)
- 木上の双方向変換を利用したファイルマネージャの実現
- 木上の双方向変換を利用したファイルマネージャの実現
- データマイニングのアルゴリズム記述を容易にする拡張行列演算の提案
- 閻魔 Webインタフェースによるプログラミング教育支援システム
- 決定論的2階パターンとプログラム変換への応用
- 少数キー入力に基づくエディターの紹介(福祉と言語処理/一般)
- 歴代理事長座談会「日本ソフトウェア科学会の20年とこれから」(20周年記念特集)
- 特集「自己反映計算(リフレクション)」の編集にあたって (自己反映計算(リフレクション))
- 少数キー入力に基づくエディターの紹介(福祉と言語処理/一般)
- 少数キーを用いた日本語入力(自然言語)(コラボレーションアートとネットワークエンターテイメント)
- ユーザ文書を用いた個別かな漢字変換支援
- 携帯電話における日本語入力 : 子音だけで日本語が入力できるか
- PPM法を用いたかな漢字変換の学習モデル
- 利得の最適連想規則を求める線形時間アルゴリズムの導出
- 最大重み和問題の線形時間アルゴリズムの導出
- ACM PLI 2000会議報告
- ナップサック問題およびその発展問題の統一的解法
- 完全遅延評価に適した関数プログラムの共有解析
- 関数プログラムのコンパイラにおける型情報を用いた効率的な共有解析の実現
- プログラム融合変換の実用的有効性の検証
- HYLOシステムによるプログラム融合変換の実現
- 関係代数によるUNITYループの意味づけ
- 再帰的に定義された関係からのアルゴリズムの導出
- 満足化原理に基づく強化学習のための確率的探査戦略
- 木変換言語の双方向化に関する事例研究(サイバー増大ページ論文概要,新しいソフトウェアの実現,サイバー増大号)
- 編集にあたって(研究会推薦博士論文速報)
- 編集にあたって(研究会推薦博士論文速報)
- 編集にあたって(研究会推薦博士論文速報)
- 「不惑」の中国若手研究リーダーたち
- スケルトン並列プログラミング
- 最適化機構を持つC++並列スケルトンライブラリ(サイバー増大ページ論文概要,サイバー増大号)
- Joseph E. Stoy : Denotational Semantic: The Scott-Strachey Approach to Programming Language Theory, MIT Press, 1977(20世紀の名著名論)
- 関数型言語の投機的実行と負荷分散
- 学術の今日と明日 情報学分野の今日と明日
- R.M.Burstall and J.Darlington : A Transformation System for Developing Recursive Programs, J.ACM(1977)(20世紀の名著名論)
- しりとりゲームの数理的解析(ゲームプログラミング)
- MK-5 戦略ソフトウェア創造人材養成プログラム(大型プロジェクト紹介,学術系企画)
- 変換戦略の記述に基づくプログラムの自動生成システムの実装
- 最小属性値を持つ多次元探索木の提案.
- 蓄積引数を持つ関数プログラムの融合変換
- 関数プログラムのプロモーション変換のための二手法の関係
- 擬データと関数による並行プロセス群の記述
- 擬データと関数による並行プロセス群の記述
- フジアで情報学の「梁山泊」を造る
- 平面上の矩形和の最大値問題の並列プログラムの導出
- 領域限定言語に基づく最適経路問合せ
- Catamorphismに基づく関数プログラムの変換
- Catamorphismに基づく関数プログラムの変換
- 数理工学への誘い プログラム運算の数理--数式運算による並列プログラミング
- グラフの探索関数の再帰的定義と変換(特集●プログラミング及びプログラミング言語)
- ソフトウェア科学の世紀に向けて(特集・新世紀フォーラム)
- Calculating a New Data Mining Algorithm for Market Basket Analysis (Program Transformation, Symbolic Computation and Algebraic Manipulation)
- プログラム運算による発展的プログラミング (特集 ソフトウェア発展)
- 関数プログラミング (特集 いま欲しいブレークスルー)
- 小特集「プログラミング言語 : PascalとAda」の編集にあたって
- Pascal総説 (プログラミング言語 : PascalとAda)
- 疎結合並列計算機上の遅延評価型関数型言語処理系の性能評価
- 関数型言語処理系におけるデータ構成子のunbox化
- FPGAによる関数型言語向きアーキテクチャを持つプロセッサの実装
- 分散環境における文書の協同作成支援システムの設計と試作
- 情報学分野の今日と明日
- プログラム運算による並列プログラミング(特集・新世紀フォーラム)