Введение
Глава 1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций в конечном поле 16
1.1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций 16
1.2. Базовые понятия и теоремы 22
1.2.1. Определения теории цепей Маркова 22
1.2.2. Определения теории конечных полей 24
1.2.3. Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле GF(2") 25
1.3. О задаче анализа цепей Маркова по критерию линейной сложности 27
1.4. О задаче разработки комплекса методик и программ 30
1.5. Выводы по главе 31
Глава 2. Методы представления случайных последовательностей полиномиальными функциями над конечным полем 32
2.1. Представление стохастических матриц полиномиальными функциями над полем GF(2") с учетом точности представления элементов матриц 32
2.1.1. Введение 32
2.1.2. Подход разложения матриц, основанный на методе минимакса 34
- Алгоритм минимакса 34
2.1.3. Двоично-рациональный подход разложения матриц 36
- Алгоритм 2 36 -Алгоритм 2м 38
- Алгоритм 3 45
- Алгоритм Зм 47
- Алгоритм 4 49
- Алгоритм 4м 54
2.1.4. Метод построения функций цепей Маркова над полем GF(2") и оценки порядка поля 59
2.1.5. Выводы по разделу 60
2.2. Представление расширенных цепей Маркова над полем GF(2") 63
2.2.1. Введение 63
2.2.2. Получение стохастической матрицы расширенной цепи Маркова 63
- Постановка задачи 63
- Определение "промежуточной" матрицы переходов 64
- Определение матрицы О расширенной цепи Маркова 70
- Алгоритм вычисления матрицы О расширенной цепи Маркова по 72
матрице Р исходной цепи Маркова
2.2.3. Полиномиальные модели расширенных цепей Маркова над полем GF(2") 72
- Модель генератора расширенной цепи Маркова на регистре сдвига 72
- Полиномиальная модель расширенной цепи Маркова на основе имплицирующего вектора 73
- Полиномиальная модель расширенной цепи Маркова на основе приведенного автомата 78
2.3. Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице 82
2.3.1. Введение 82
2.3.2. Теоретический анализ. Постановка задачи 83
2.3.3. Схема построения минимального многочлена над полем GF(gc) 84
2.3.4. Метод моделирования случайной последовательности на основе минимального полинома 86
2.3.5. Характеризация класса случайных последовательностей 90
2.4. Выводы по главе 92
Глава 3. Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле 93
3.1. Анализ нелинейных моделей преобразователей случайных последовательностей над полем GF(2") на основе стохастических матриц 93
3.1.1. Введение 93
3.1.2. Определение базовых полиномиальных функций над полем GF(2") 94
3.1.3. Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова. Вероятностные характеристики моделей 95
- Полиномиальная модель цепи Маркова 95
- Полиномиальная модель марковской функции Bt 96
- Полиномиальная модель марковской функции Zt 100
- Полиномиальная модель марковской функции Zt 102
3.2. Статистический анализ линейной сложности регулярных цепей Маркова 104
3.2.1. Введение 104
3.2.2. Постановка задачи 106
3.2.3. Реализация и тестирование алгоритма Берлекэмпа-Мэсси 108
3.2.4. Обсуждение полученных результатов 113
3.3. Выводы по главе 117
Глава 4. Комплекс методик и программ для решения задач построения и анализа полиномиальных функций и моделирования случайных последовательностей 118
4.1. Методика программной реализации представления простых и расширенных цепей Маркова над полем GF(2") 118
4.2. Методика программной реализации моделирования случайных последовательностей на основе минимальных полиномов 121
4.3. Программная реализация алгоритма Берлекэмпа-Месси 122
4.4. Методика программной реализации статистического анализа линейной сложности регулярных цепей Маркова 126
4.5. Программный комплекс "Лабораторный практикум вычислений в конечных полях" 128
4.6. Программный комплекс "Генераторы псевдослучайных чисел" 131
4.7. Подсистема временного прогнозирования для автоматизированного рабочего места менеджера предприятия 133
4.8. Выводы по главе 137
Заключение 138
Список литературы
