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

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

В. Л. Куракин

Аннотация

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

Представлен алгоритм, позволяющий по заданному отрезку длины $l$ над коммутативным артиновым кольцом главных идеалов $R$ построить унитарный многочлен наименьшей степени, порождающий этот отрезок. Трудоемкость алгоритма составляет $O(l2n)$ операций кольца, где $n$ -- индекс нильпотентности радикала кольца $R$. Алгоритм применяется для построения канонической системы образующих идеала всех многочленов, аннулирующих заданную линейную рекуррентную последовательность над кольцом $R$.

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

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