- Алгоритм Берлекэмпа
-
Не следует путать с Алгоритм Берлекэмпа — Мэсси.
Алгоритм Берлекэмпа — алгоритм, который позволяет находить закон рекурсии для линейной рекуррентной последовательности.
Основные определения
Если существуют константы:
такие что:
, то последовательность
будем называть линейной рекуррентной последовательностью (ЛРП) порядка
. Поскольку
— ЛРП, то полином
будем называть характеристическим полиномом для ЛРП
. Характеристический полином, имеющий наименьшую степень, называется минимальным многочленом, а его степень — линейной сложностью рассматриваемой ЛРП. Обозначим u(0,…,l-1)={u(0),…,u(l-1)} — начальный отрезок рассматриваемой ЛРП. Будем говорить, что многочлен:
вырабатывает отрезок u(0,…,l-1), если для любого i принадлежащего [0,l-m-1] выполнено:
, то есть, если данный отрезок последовательности является отрезком некоторой ЛРП с характеристическим полиномом G(x). Определим операцию умножения многочлена на последовательность: пусть
— произвольный многочлен, а ν — последовательность. Тогда результатом произведения будет последовательность w(i), такая, что:
, a w(i) выражаются следующим образом:
. Для нормированного полинома G(x) определим параметры:
— количество лидирующих нулей последовательности G(x)u или ∞ ,если эта последовательность нулевая.
Очевидно,
— максимальная длина начального отрезка u, вырабатываемого полиномом G(x).
Постановка задачи
Задача ставится следующим образом: имеется последовательность u, и число l, нужно найти минимально необходимый полином G , вырабатывающий отрезок u(0,…,l-1). Будем строить последовательность полиномов
в соответствии со схемой алгоритма Берлекэмпа, представленной на рисунке[уточнить], который находится по адресу, указанному ниже. Таким образом, построенный набор полиномов
отражает реккурентную закономерность в последовательности u.
Литература
- V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, A. A. Nechaev. Linear recur-ring sequences over rings and modules. // I. of Math. Science. Contemporary Math. and it’s Appl. Thematic surveys, vol. 10, 1994, I. of Math. Sciences, vol. 76, № 6, 1995.
Для улучшения этой статьи по математике желательно?: - Проверить достоверность указанной в статье информации.
- Исправить статью согласно стилистическим правилам Википедии.
- Викифицировать статью.
На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.Категория:- Алгебра
Wikimedia Foundation. 2010.