Berlekamp–Massey のアルゴリズム

線形漸化式の復元（mod m）

多項式・形式的べき級数 線形代数 線形漸化的数列 C-recursive Berlekamp–Massey のアルゴリズム Reeds–Sloane のアルゴリズム

1. 概要 本講座では，正整数 $\boldsymbol{m}$ を法とする線形漸化式の復元問題を扱います． 線形漸化式の復元 では，数列から定数係数線形漸化式を復元する問題を，係数環が体である場合に解説しました．その場合のアルゴリズムの代表が Berlekamp–Massey …

線形漸化式の復元

多項式・形式的べき級数 線形代数 線形漸化的数列 C-recursive 行列累乗 Berlekamp–Massey のアルゴリズム Euclid の互除法 Half-GCD

1. 概要 本講座では，数列から定数係数線形漸化式を復元する問題について解説します． 例えば，Fibonacci 数列の先頭項 $$ S=(0,1,1,2,3,5,8,13) $$ を入力として，この数列が満たす漸化式 $$ S _ i = S _ {i-1} + S _ {i-2} $$ を出力するような問題を考え…