Методы и алгоритмы построения и анализа полиномиальных функций над конечным полем на основе стохастических матриц

• Автор: Эминов, Булат Фаридович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Казань
• Количество страниц: 159 с. : ил.

Введение

Глава 1. Связь цепей Маркова, вероятностных автоматов и

полиномиальных функций в конечном поле

1.1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций

1.2. Базовые понятия и теоремы

1.2.1. Определения теории цепей Маркова

1.2.2. Определения теории конечных полей

1.2.3. Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле СБ2Л

1.3. О задаче анализа цепей Маркова по критерию линейной сложности

1.4. О задаче разработки комплекса методик и программ

1.5. В ы воды по главе Глава 2. Методы представления случайных последовательностей

полиномиальными функциями над конечным полем
2.1. Представление стохастических матриц полиномиальными функциями
над полем С2п с учетом точности представления элементов матриц
2.1.1. Введение
2.1.2. Подход разложения матриц, основанный на методе минимакса
Алгоритм минимакса
2.1.3. Двоичнорациональный подход разложения матриц
Алгоритм 2
Алгоритм 2м
Алгоритм 3
Алгоритм Зм
Алгоритм 4
Алгоритм 4м
2.1.4. Метод построения функций цепей Маркова над полем СР2 и оценки порядка поля
2.1.5. Выводы по разделу
2.2. Представление расширенных цепей Маркова над полем СР2П
2.2.1. Введение
2.2.2. Получение стохастической матрицы расширенной цепи Маркова
Постановка задачи
Определение промежуточной матрицы переходов
Определение матрицы 7 расширенной цепи Маркова
Алгоритм вычисления матрицы О расширенной цепи Маркова по
матрице Р исходной цепи Маркова
2.2.3. Полиномиальные модели расширенных цепей Маркова над полем ОР2
Модель генератора расширенной цепи Маркова на регистре
сдвига
Полиномиальная модель расширенной цепи Маркова на основе имплицирующего вектора
Полиномиальная модель расширенной цепи Маркова на основе приведенного автомата
2.3. Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице
2.3.1. Введение
2.3.2. Теоретический анализ. Постановка задачи
2.3.3. Схема построения минимального многочлена над полем СГс
2.3.4. Метод моделирования случайной последовательности па основе минимального полинома
2.3.5. Характеризация класса случайных последовательностей
2.4. Выводы по главе
Глава 3. Методы анализа полиномиальных функций, моделирующих
случайные последовательности в конечном поле
3.1. Анализ нелинейных моделей преобразователей случайных последовательностей над полем СР2 на основе стохастических
матриц
3.1.1. Введение
3.1.2. Определение базовых полиномиальных функций над полем
ОН2
3.1.3. Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова. Вероятностные характеристики моделей
Полиномиальная модель цепи Маркова
Полиномиальная модель марковской функции В
Полиномиальная модель марковской функции
Полиномиальная модель марковской функции
3.2. Статистический анализ линейной сложности регулярных цепей
Маркова
3.2.1. Введение
3.2.2. Постановка задачи
3.2.3. Реализация и тестирование алгоритма БерлскэмпаМэсси
3.2.4. Обсуждение полученных результатов
3.3. Выводы по главе 7 Глава 4. Комплекс методик и программ для решения задач построения и
анализа полиномиальных функций и моделирования случайных последовательностей
4.1. Методика прораммной реализации представления простых и расширенных цепей Маркова над полем СГ2
4.2. Методика нрораммной реализации моделирования случайных последовательностей на основе минимальных полиномов
4.3. Программная реализация алгоритма БерлекэмпаМесси
4.4. Методика программной реализации статистического анализа линейной сложности реулярпьх цепей Маркова
4.5. Программный комплекс Лабораторный практикум вычислений в конечных полях
4.6. Программный комплекс Генераторы псевдослучайных чисел
4.7. Подсистема временного прогнозирования для автоматизированного рабочего места менеджера предприятия
4.8. Выводы по главе
Заключение
Список литературы


Доказана теорема, устанавливающая линейную связь между точностью задания стохастической матрицы и величиной минимальной степени полинома. Новый метод определения вероятностных характеристик случайных последовательностей из класса функций однородных цепей Маркова, порождаемых полиномиальными нелинейными динамическими моделями над полем СР2П. Методика исследования однородных простых и сложных цепей Маркова на основе критерия линейной сложности. Сформулирован критерий нахождения длин реализаций марковских последовательностей при заданной точности представления матриц цепей Маркова. Определены стохастические зависимости линейной ело лености реализаций цепей Маркова от энтропии стохастических матриц. Достоверность результатов работы. Основные полученные результаты сформулированы в виде теорем и утверждений, приведены их доказательства. Предложенные аналитические методы и алгоритмы обоснованы доказательством теорем. Адекватность предложенных моделей подтверждается компьютерным моделированием и сравнением с известными результатами. Практическая значимость работы. Решение задачи представления РЦМ полиномиальными функциями над полем ОР2 расширяет класс дискретных случайных процессов, получаемых на полиномиальных моделях, и позволяет определить свойства данных процессов и стохастических матриц РЦМ. Предложенные алгоритмы разложения СМ ЦМ на имплицирующий вектор ИВ и множество стохастических булевых матриц СБМ позволяют определить вычислительную и комбинационную сложности вероятностных автоматов, синтезируемых в некотором логическом базисе. Полученные формулы определения предельного распределения вероятностей символов СП, порождаемых полиномиальными нелинейными динамическими моделями дискретных преобразователей информации, и фундаментальная матрица для СМ позволяют на их основе получить ряд других характеристик СП, например, матрицу средних времен достижения, векторы предельных дисперсии и корреляции. Метод моделирования СП па основе минимального полинома позволяет воспроизводить на линейных регистрах сдвига реализации ЦМ расширить функциональное использование линейных регистров сдвига. Методика исследования ЛС марковских последовательностей расширяет класс задач применения ЛС, дает возможность моделировать ЦМ на основе линейных и нелинейных полиномов минимальных степеней, позволяет выявлять свойства ЛС марковских функций. Комплекс программ, алгоритмов и методик является инструментальным средством для моделирования СП и исследования свойств полиномиальных функций над конечным полем. ОАО 1СЬКПО ВС, г. Компьютерные системы и информационная безопасность и кафедры Систем информационной безопасности КГТУ им. А.Н. Туполева в форме учебного электронного пособия Лабораторный практикум по вычислениям в конечных полях акт внедрения. Апробация результатов работы. Основные результаты докладывались и обсуждались на следующих конференциях и семинарах ХХУ Всероссийские молодежные научные конференции Туполевские чтения Казань, Всероссийская научная конференция студентов и аспирантов Таганрог, XIV Международная конференция Проблемы теоретической кибернетики Пенза, Региональная научнометодическая конференция Профессиональные компетенции в структуре модели современного инженера Нижнекамск, 6ая Международная конференция молодых ученых и студентов Самара, Международная научнопрактическая конференция Инфокоммуникационные технологии глобального информационного общества Казань, Региональная научнометодическая конференция Информационная культура в системе подготовки будущего инженера Нижнекамск, Всероссийский семинар Ситуационные исследования Казань, Региональная научнотехническая конференция по вопросам информатики, вычислительной техники и информационной безопасности Казань, Региональная научнопрактическая конференция Наука и профессиональное образование Нижнекамск, 9ый Международный семинар Дискретная математика и ее приложения Москва, Всероссийская научная конференция студентов, аспирантов и молодых ученых Наука, технологии, инновации Новосибирск, Республиканский научный семинар Методы моделирования при КГТУ им. А.Н. Туполева Казань, .