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

• Item type: Trans(1)
• 公開日: 2010-09-22
• タイトル: データ列に関するアルゴリズムの逆変換に基づく導出
• タイトル / 言語: en
• タイトル: Derivation of Various Algorithms for Lists Based on Inverse Conversion
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 株式会社日本電気航空宇宙システム
• 著者所属(英): en
• 著者所属(英): NEC Aerospace Systems, Ltd.
• 著者名: 森本, 真一
• 著者名(英): Shin-ichi, Morimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，最長上昇部分列（LUS），最長上昇部分列（LCS）やソート列のように，入力データ列からある条件を満たすデータ（目的データという）を求めるアルゴリズムを逆変換として導出する方法を述べる．変換が関数として表現できる（入力に対して出力が一意に定まる）場合でも，逆変換は関数として表現できない場合がある．そこで本発表では，変換と逆変換を同様に記述するため入力データ列と目的データの対応を関数でなく関係（入出力関係という）として表現する．そして入出力関係の入力データ列に関する再帰的定義から目的データの分解処理（入力データ列に対応する目的データから入力データ列の構成要素に対応する目的データをトップダウンに求める処理）を導出する．さらにこの分解処理に対して逆変換である目的データの合成処理（目的データを求める処理）が満たす条件を示す．またLCS，LUS，ソート列のように目的データ列の要素が入力データ列の要素であり，分解処理がある条件を満たす場合は合成処理を分解処理の記述から具体的に構成できることを示す．逆変換は関数として表現できない場合があるので，本方式では目的データの合成処理をテーブルを利用して記述する．これは合成処理を動的計画法により記述することに相当する．さらに本発表では，合成処理の計算量を減少できる条件を入出力関係から特徴づけ，この特徴づけと動的計画法における既存の最適化手法（greedy定理，thinning定理）との関係を述べる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this presentation, we derive various algorithms for data sequences such as LCS (Longest Common Subsequences), LUS (Longest Up Subsequences) and sorting algorithms as inverse conversions. In our method, correspondence between input data and target data are represented as relations not as functions, because an inverse conversions of a function may not be a function. We derive the decomposition process of target data from the recursive definition of this relation. We state conditions for the composition process of target data as the inverse of the decomposition process. For target data whose elements are elements of input data such as LCS, LUS and sorting, we can derive the concrete composition process. In our method, composition process is described by using a table because the inverse conversion may not be a function. It means that the composition process is a kind of dynamic programming. We also state conditions to reduce time complexities of the composite processes and correspondence between these conditions and current optimization methods of dynamic programming such as greedy theorem and thinning theorem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 3, 号 4, p. 68-68, 発行日 2010-09-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会