最大部分和問題に対する高速プログラムの合成

NEDUNURI Srinivas; COOK William R.

文献

J-GLOBAL ID：201002259166124049 整理番号：10A0941472

最大部分和問題に対する高速プログラムの合成

Synthesis of Fast Programs for Maximum Segment Sum Problems

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=10A0941472&from=J-GLOBAL&jstjournalNo=D0915A") }}

著者 (2件)： ,
資料名：
巻： 45 号： 2 ページ： 117-125 発行年： 2010年02月
JST資料番号： D0915A ISSN： 0362-1340 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

生成的プログラミングでは,仕様からアルゴリズムの効率的実装を導出するというアイデアがある。その一つの技法として,仕様通りに動作する単純であるが非効率的なプログラムから始め,次に効率を改善するためにプログラム変換を適用するという技法がある。この技法は,最大部分和問題の幾つかの派生形を解決するためのプログラムを導出するために用いられてきた。この手法による問題の一つは,それぞれの問題の派生形ごとに新しい変換セットが必要であるということである。Smithらにより開拓されたプログラム合成に対する代わりの手法は,問題のプレ/ポスト条件仕様を,一般的な問題解決知識を捉える高位のアルゴリズム理論に結び付ける。本稿では,この手法がどのようにしてHaskellで実装され,そして制約充足問題を解くために適用されうるかを示した。3つの異なる最大重み和問題に対するプログラムを導出することによりこの技法を説明した。さまざまなプログラムの導出は類似しており,また,結果のプログラムは変換により創成されたプログラムよりも実際面では漸近的により高速である。

, , , , , ,
,

計算理論

前のページに戻る