二分木の辞書順のランク計算の効率的なクリーン可逆シミュレーション

柴田 心太郎  横山 哲郎  

誌名
電子情報通信学会論文誌 D   Vol.J102-D   No.3   pp.130-140
発行日: 2019/03/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2018PDP0021
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
可逆プログラム,  クリーン可逆シミュレーション,  ランク,  二分木,  Janus,  

本文: PDF(1.2MB)
>>論文を購入


あらまし: 
可逆システム上で非可逆プログラムの可逆シミュレーションを実現するとき,既知の一般解法を用いると,元の入出力の走査回数と,元の入出力用以外のメモリ使用量が増え,元の出力以外を出力してクリーンでなくなってしまうという問題が起こる.しかし,非可逆なアルゴリズムに対して,経験と勘を元に個別の非可逆プログラムの効率的なクリーン可逆シミュレーションが実現されてきている.本論文では,可逆計算システムで用いる可逆アルゴリズムとして,二分木の列挙,二分木の辞書順のランク計算,及び辞書順における次の二分木の生成の効率的なクリーン可逆シミュレーションの構築をする.これらは基礎的な可逆アルゴリズムであるので,他の可逆アルゴリズムの一部として使用されたり,可逆アルゴリズムの構築法が利用されたりすることが期待される.また,二分木のランク計算に関する効率的な可逆プログラムの整備を進めることで類似するランク計算や更には現時点では困難な一般の効率的可逆シミュレーションの自動導出が可能になることが期待される.本論文の可逆プログラムは全てオンラインインタプリタで実行して振る舞いを確かめることが可能である.