|
|
Семинар «Актуальные проблемы дискретной математики»
29 марта 2016 г. 14:10–14:30, г. Москва, МИАН, ул. Губкина, д. 8
|
|
|
|
|
|
Синтез низкоресурсного линейного автомата с заданным характеристическим многочленом
В. О. Дрелихов |
Количество просмотров: |
Эта страница: | 207 | Материалы: | 3 |
Фотогалерея
|
Аннотация:
Формулировка задачи о выборе матрицы с заданным характеристическим многочленом, допускающей простую и быструю реализацию умножения вектора на неё для различных вычислительных платформ.
Задан характеристический многочлен $f(x)$, $\deg f=n$, «общего вида» над $GF(q)$, $q>2$. Требуется разработать алгоритм (работающий «быстро» при больших $n$) нахождения матрицы $A$ над полем $GF(q)$ размера $n\times n$, удовлетворяющей условиям:
- $f(x)=\|xE_n-A\|$, где $E_n$ – единичная матрица размера $n\times n$;
- в каждой строке и в каждом столбце должно быть не более трех ненулевых элементов поля $GF(q)$.
Случаи, представляющие особый практический интерес.
Матрица трехдиагональная (линейный клеточный автомат), при этом: либо многочлен $f(x)$ неприводим,
либо $f(x)=f_1(x)f_2(x)$, где многочлены $f_1(x)$, $f_2(x)$ неприводимы.
Для случая $q=2$ задача уже имеет решение (т.е. алгоритм построения трехдиагональной матрицы по заданному характеристическому многочлену).
Дополнительные материалы:
Дрелихов.pdf (191.7 Kb)
|
|