Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
По тематике восьмой главы кроме указанных имеются ещё работы: Кисловская
[1*] и Нечаев [1*]* - Перев.]
Упражнения
8. \. Построить регистр сдвига с обратной связью, реализующий линейно!
рекуррентное соотношение
Sft+S - ^Н+4 ^71+8 (r)rt+i * й = 0, 1,
над полем Fs.
8,2, Построить регистр сдвига с обратной связью, реализующий линейно!
рекуррентное соотношение
• *.\л №
.)Й
V-й*
!•,* Ж
тк
>аг
>'ЛЪ5
'М
'¦it
• * "
' Ф. ' ••• •
Щ
'П+7
= 3.5
гг+5
П
О, I,
* I
над полем F7.
8*3. Пусть г - период периодической последовательности s0> 5i. * *, и
пусть щ - наименьшее неотрицательное целое число, для которого
выполняется равенство sn+r(tm) sn при всех п ^ п0. Доказать, что п0
совпадает с предпериодом
последовательности %, зг......
8.4, Определить порядок матрицы
А -
0 0 0 -1
10 0 I
¦I
0 1 о 0 0 1
1
I
как элемента общей линейной группы GL (4, F3).
¦М
• I IK1
.:<Я •* ":>?
Упражнения
581
8.5. Доказать результаты из примера 8.18 с помощью методов § 5.
8.6. Пользуясь равенством (8.8), получить явную формулу для членов
линейной рекуррентной последовательности над полем F3, определяемой
рекуррентным соотношением = -sn+i + sn, п = О, I, ..., и начальными
условиями $о si = ^ - 6.
8.7. Пользуясь результатом, приведенным в замечании 8,23, получить я иную
формулу для членов рекуррентной последовательности над полем F4>
определяемой рекуррентным соотношением sn+4 = asn+3 -f sn+1 -f n
-
- 0, 1, .... где а -примитивный элемент поля F4, н начальными условиями
So •' s'i - s2 0. S3 - 1.
8.8. Доказать, что члены sn, задаваемые формулой, приведенной в замечании
8.23, удовлетворяют однородному линейному рекуррентному соотношению с
характеристическим многочленом f (ж).
8.9. Доказать результат, приведенный в замечании 8.23, для случая ^ ^ 2,
i 1, 2 т, и е,- -- 1, если а; - 0.
8.10. Представить элементы линейной рекуррентной последовательности над
полем F2, определяемой рекуррентным соотношением -f Sn,
n - 0, И начальными условиями So = 0, SJ - s2 ~ Ь с помощью
подходя-
щей функции следа.
8.11. Доказать лемму 8.26, используя линейные рекуррентные
последовательности.
8.12. Найти минимальный период последовательности, порожденной импульсом
и удовлетворяющей линейному рекуррентному соотношению ^
Sfi+c. ^н+5 "Ь Sn-н "h Sji, п - 0, 1, над полем Fg.
8.13. Найти минимальный период последовательности, порожденной им-
пульсом, соответствующей линейному рекуррентному соотношению Sn.+ie -
~ ?п+7~Ь ^71+2 + ^н+i "Ь ^ ~ 6, 1, ..., над полем Fg*
8.14. Доказать теорему 8.27, пользуясь производящими функциями.
8.15. Найти линейную рекуррентную последовательность наименьшего порядка
над полем Г2, минимальный период которой равен 21.
8.16. Найти линейную рекуррентную последовательность наименьшего порядка
над полем Fg, минимальный пернод которой равен 24.
8.17- Пусть г - минимальный период последовательности Фибоначчи над полем
F,j, т, е. последовательности, определяемой рекуррентным соотношением
sn+2 ^ $п^1 -[- snt п ¦¦ 0, 1, ..., и начальными условиями % - 0, Sj = 1.
Пусть р -¦ характеристина поля Fq. Доказать, что г 20, если р = 5, г
делит р - 1, если р hi ±1 {mod 5), г делит рг- 1 во всех остальных
случаях.
8.18. Построить последовательность максимального периода над полем F3,
имеющую минимальный период, равный 80.
8.19. {т, к) - последов а тел ь ноет ью де Брейна называется конечная
последовательность Sq, Si, . ., Sjv ь содержащая N - тк членов, взятых нз
множества, содержащего т различных элементов, такая, что все наборы длины
к вида {sn, s*.+b * . &n+k~ 1)1 к - 0, 1, ..., N - 1, где нижние индексы
берутся по модулю /V, являются различными. Доказать, что еслн ... -
последовательность А-го
порядка, порожденная импульсом и являющаяся последовательностью
максимального периода над полем F^, то последовательность Sq - 0, Sn=
drt-ъ ^ ^
- 1, является (щ ^-последовательностью де Брейна.
8.20. Построить (2, ^-последовательность де Брейна.
8.21. Пусть В (х) = 2 - х -f jt3 ? F? [ж]. Найти первые шесть ненулевых
членов формального степенного ряда 1 !В (ж).
8.22. Пусть
А{х) = - 1-х + х\ В(х) = ? ( i)nx" ? F, [[*]].
Найти первые пять ненулевых членов формального степенного ряда А (х)!В
(ж).
582
Гл. 8. Линейные рекуррентные последовательности
8.23. Рассмотрим линейную рекуррентную последовательность над нолем (Г3,
задаваемую рекуррентным соотношением sR+g (tm) $а±4 4- sn+2 -• sn+l -f--f-
Sn> ft - 0, 1, и начальными значениями s0 = sf = s2 I, s3 - s4 - -I,
Представить производящую функцию этой последовательности в виде (8.15),
8.24. Найти первые восемь членов последовательности, порожденной
импульсом н соответствующей линейному рекуррентному соотношению sR+s = (tm)
Sn+3 4- ^я+2 Н" sn> " = 0, 1, над полем fY Воспользоваться операций
деления углом.
8.25. Пусть se, sjf ... - однородная линейная рекуррентная
последовательность над полем Fg. Доказать, что множество всех многочленов
f (х) ^ akxk+ + ... + агх~\~ со € Fg UJ, таких, что ... + =
