情報処理学会 第76回全国大会講演要旨

現在，発展途上である可逆アルゴリズム理論では，
非可逆アルゴリズム理論における既存の知見を応用することに意義を見出せる状況にある．
既存のアルゴリズム理論の成果を直接的に用いるために，
既存のアルゴリズムの可逆シミュレーションが行われている．
しかし，現時点では個々のアルゴリズムについて最適なゴミ情報量をもつ
可逆アルゴリズムを自動生成する方法は知られていない．
本研究では，アルゴリズムを構成する基本的な処理を可逆化する方法，
および自然数の組によって表された複数の最適なゴミ情報を一つにマージする方法を提案する．
この提案手法によって最適な可逆クイックソート，最適な可逆マージソートを生成できることを確認した．