分野別セミナー

アブストラクト： 本研究は乱択化によるカオスの計算の効率化を目標とする．例えば，β展開やテ ント写像，ロジスティック写像といったカオスが生成するビット列を計算機で求めることを考える．カオスの予測不可能性のため，通常n番目のビットを得るにはn回写像の計算が必要である．よって計算時間や必要な作業領域はnに対して線形に増加するが，より小さいコストで計算したい．本講演は，テント写像のLR記号列に関連する有限長0-1系列のランダム生成の領域計算量について議論する．具体的には，牧野たち[2015]のβ展開のアイデアを利用したマルコフ連鎖を設計し，0-1系列のビット長nに対して計算作業領域の小さなアルゴリズムを与える．このアルゴリズムの領域計算量が期待値でnの対数サイズとなることを示す．