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

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

1. 概要 本講座では，Bostan–Mori のアルゴリズムに関する発展的な話題を扱います． 前回の講座 線形漸化的数列の第 K 項 では，線形漸化的数列の第 $K$ 項を高速に求める方法として，Fiduccia のアルゴリズムと Bostan–Mori のアルゴリズムを解説しました．…

1. 概要 単位的可換環 $R$ 上の数列 $A = (A_0,A_1,A_2,\ldots)$ が，定数 $c_1, c_2, \ldots, c_d$ について $$ A _ i = c_1 A _ {i-1} + c _ 2A _ {i-2} + \cdots + c _ dA _ {i-d}\qquad(i\geq d) $$ を満たすとします．このような数列を線形漸化的数列と…

解説動画はこちらです． 1. 概要 本講座では，線形漸化的数列について解説します． 線形漸化的数列とはある種の漸化式を満たす数列のことで，代表例としては漸化式 $$ F _ i = F _ {i-1} + F _ {i-2}\quad (i\geq 2) $$ を満たす Fibonacci 数列 $$ F = (0, …