データ列に関するアルゴリズムの逆変換に基づく導出

概要

論文の詳細を見る
本発表では,最長上昇部分列(LUS),最長上昇部分列(LCS)やソート列のように,入力データ列からある条件を満たすデータ(目的データという)を求めるアルゴリズムを逆変換として導出する方法を述べる.変換が関数として表現できる(入力に対して出力が一意に定まる)場合でも,逆変換は関数として表現できない場合がある.そこで本発表では,変換と逆変換を同様に記述するため入力データ列と目的データの対応を関数でなく関係(入出力関係という)として表現する.そして入出力関係の入力データ列に関する再帰的定義から目的データの分解処理(入力データ列に対応する目的データから入力データ列の構成要素に対応する目的データをトップダウンに求める処理)を導出する.さらにこの分解処理に対して逆変換である目的データの合成処理(目的データを求める処理)が満たす条件を示す.またLCS,LUS,ソート列のように目的データ列の要素が入力データ列の要素であり,分解処理がある条件を満たす場合は合成処理を分解処理の記述から具体的に構成できることを示す.逆変換は関数として表現できない場合があるので,本方式では目的データの合成処理をテーブルを利用して記述する.これは合成処理を動的計画法により記述することに相当する.さらに本発表では,合成処理の計算量を減少できる条件を入出力関係から特徴づけ,この特徴づけと動的計画法における既存の最適化手法(greedy定理,thinning定理)との関係を述べる.
2010-09-22

著者

森本真一
株式会社日本電気航空宇宙システム

データ列に関するアルゴリズムの逆変換に基づく導出

スポンサーリンク

概要

著者

関連論文

スポンサーリンク