リストの可逆分割アルゴリズムを利用した ゴミ情報が最適な可逆クイック整列法の生成

摘要

本論文では文献[1] におけるゴミ情報の生成・マージの手法を応用し，より一般性の高い手法を提案する．文献[1] では，ゴミ情報量が最適なリストの可逆分割アルゴリズムを提案している．ここではさらに提案したアルゴリズムを利用してクイックソートを生成し，分割の際のゴミ情報量が最適であること，再帰呼び出しの際にゴミ情報の最適な伝播が実現できていることの2 点を示している．しかし，この手法はクイックソートに特有のサブプロシージャに対して最適なゴミ情報の生成を保証することにより実現されており，この手法をそのまま他のアルゴリズムに応用することが難しい．そこで，本研究ではアルゴリズムのより小さな構成要素に最適なゴミ情報を生成させ，それらの最適性を保ったままより大きな構成要素へとマージを行う手法を提案し，既存の手法の応用性を高める．なお，ここではゴミ情報とは非可逆アルゴリズムを可逆化する際に記録する必要があり，可逆化する前の非可逆アルゴリズムにおいては記録する必要のない情報を表す．