FPM 1999, ТОМ 5, ВЫПУСК 4, СТР. 1061-1101

ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
1999, ТОМ 5, ВЫПУСК 4, СТР. 1061-1101

Алгоритм Берлекэмпа--Месси над коммутативными артиновыми кольцами главных идеалов

В. Л. Куракин

Аннотация

Посмотреть как HTML Посмотреть как рисунок Посмотреть в формате LaTeX





Представлен алгоритм, позволяющий по заданному отрезку длины $l$

над коммутативным артиновым кольцом главных идеалов $R$ построить унитарный

многочлен наименьшей степени, порождающий этот отрезок. Трудоемкость

алгоритма составляет $O(l^2n)$ операций кольца, где $n$ --- индекс

нильпотентности радикала кольца $R$. Алгоритм применяется для построения

канонической системы образующих идеала всех многочленов, аннулирующих

заданную линейную рекуррентную последовательность над кольцом $R$.

Полнотекстовая версия статьи в формате PostScript (133 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/99/994/99407t.htm
Изменения вносились 9 декабря 1999