Мономиальные динамические системы
Федеральное агентство по образованию Российской Федерации
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО
Кафедра дискретной математики
и информационных технологий
Курсовая работа
МОНОМИАЛЬНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ
Студента 4 курса факультета КНиИТ
дневного отделения
Научный руководитель
доцент, к.ф.-м.н. Л.Б. Тяпаев
Зав. Кафедрой ДМиИТ
доцент, к.ф.-м.н. Л.Б. Тяпаев
Саратов 2010
СОДЕРЖАНИЕ
Введение
1. Теоретическая часть
1.1 Конечные динамические системы
1.2 Сокращение мономиальных систем
1.3 Линейные системы над конечными коммутативными кольцами.
Заключение
Список использованных источников
ВВЕДЕНИЕ
Важнейшая проблема в теории динамических систем заключается в том, чтобы связать структуру системы с её динамикой. В данной курсовой работе рассматривается такая связь для семейства нелинейных систем над произвольными конечными областями. Для систем, которые могут быть описаны мономами, можно получить информацию о конечной циклической структуре для структуры мономов. В частности, курсовая работа содержит достаточное условие для мономиальных систем, имеющих только фиксированные элементы, в качестве конечных циклов. Условие позволяет уменьшить проблему изучения Булевых мономиальных систем и линейных систем над конечными кольцами.
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Конечные динамические системы
Конечные динамические системы – динамические системы с конечным набором состояний в дискретном времени. Широко известны примеры использование клеточного автомата и Булевой сети, они нашли широкое применение в машиностроении, в компьютерных науках, и, ещё раньше, в биологической статистике. Чаще общие многопозиционные системы используются в теории управления, в проектировании и анализе компьютерного моделирования. Основной математический вопрос, который обычно возникает в большинстве из этих наук – как анализировать динамику модели без фактического перечисления всех состояний переходов, так как перечисление имеет экспоненциальную сложность в количестве переменных в модели.
Для ответа
на поставленный
вопрос, обозначим
конечную динамическую
систему как
функцию
,
где
– конечный
набор. Динамика
заключается
в повторении
и кодируется
в его фазовом
пространстве
,
которое является
ориентированным
графом определённым
следующим
образом. Вершина
– элемент из
.
Существует
ориентированная
дуга
в
если
.
В частности,
допустима
ориентированная
дуга в саму
себя. То есть
кодирует все
состояния
переходов
,
и имеет свойство:
для каждой
вершины имеется
полустепень
исхода точно
равная 1. Каждый
компонент
связанного
графа
состоит из
направленного
цикла, так
называемого
конечного
цикла, с направленным
деревом приложенным
к каждой вершине
в цикле, состоящем
из так называемых
переходов.
Любую Булеву
сеть можно
представить
как конечную
динамическую
систему
,
где
– конечная
область над
двумя элементами
и
.
В данной курсовой
работе, изучаются
конечные динамические
системы
,
где
– любая конечная
область и
.
Точнее, рассматривается
семейство
нелинейных
конечных систем,
для которых
можно получить
информацию
относительно
динамики структуры
функции.
Пусть
,
– конечная
динамическая
система. Рассмотрим,
как
может быть
описана в зависимости
от координатных
функций
,
то есть,
.
Известно что
любая теоретико-множественная
функция
может быть
представлена
полиномиалом
в
.
Этот полиномиал
может быть
выбран таким
образом, чтобы
любая переменная
в нём была в
степени меньшей
чем
.
То есть, для
любого
имеется уникальное
,
такое что
для всех
.
Следовательно,
любая конечная
динамическая
система над
конечной областью
может быть
представлена
как полиномиальная
система.
В случае, где
все
– линейные
полиномиалы
без константного
описания, динамику
линейных систем
можно полностью
определить
ее матричным
представлением.
Пусть
– матричное
представление
линейной системы
.
Тогда количество
конечных циклов
и их длинна,
так же как структура
переходов,
может быть
определена
разложением
на множители
характерной
полиномиальной
матрицы
.
Структура
конечных циклов
была определена
ранее Элспасом,
и для аффинных
систем Миллиганом
и Уилсоном.
В данной
курсовой работе
рассматривается
класс нелинейных
систем, описанных
специальным
типом полиномиалов,
а именно мономами.
То есть, рассматриваются
системы
,
такие, что каждый
был полиномиалом
вида
,
или константой.
Допустимо
предположение,
что никакая
координатная
функция не
константа, так
как это частный
случай переменной.
Некоторые
классы мономиальных
систем и их
динамические
поведения
изучались
прежде в работах:
Мономы клеточного
автомата, Булевы
мономиальные
системы, мономиальные
системы над
периодическими
числами и
мономиальные
системы над
конечными
областями.
В работе
«Булевы мономиальные
системы» изучался
специальный
класс Булевых
мономиальных
систем, а именно
те, которые
имеют фиксированные
элементы в
качестве конечных
циклов, так
называемые
системы конечных
элементов.
Причиной для
рассмотрения
именно этого
класса стало
использование
полиномиальных
систем в качестве
моделей для
биохимических
сетей. В зависимости
от экспериментально
рассматриваемой
системы, такие
сети часто
проявляют
устойчивые
состояния
динамики. То
есть, их динамические
модели имеют
фазовые пространства,
в которых конечные
циклы – фиксированные
элементы. С
целью подбора
модели, было
бы полезно
иметь структурный
критерий распознания
фиксированных
элементов
системы. Главная
цель данной
работы ответить
на вопрос о
мономиальных
системах над
общей конечной
областью
,
а так же, на вопрос
о связи Булевой
мономиальной
системы и линейной
системы над
кольцом
.
1.2 Сокращение мономиальных систем
Пусть
:
– полиномиальная
система, где
каждый
– моном, такой,
что
,
где
– неотрицательное
целое число.
То есть,
может быть
описано матрицей
.
В первую очередь
связывается
с Булевой
мономиальной
системой
и линейной
системой
над кольцами
.
В работе «Булевы
мономиальные
системы»
называется
системой конечных
элементов если
все конечные
циклы
заключаются
в фиксированном
элементе. Покажем
что
– конечный
элемент системы
тогда, и только
тогда, когда
и
– системы конечных
элементов.
Определение 1.2.1.
Для
,
мы определим
базис
,
обозначенный
supp(u),
равный
,
где
![]()
Мономиальная
система
порождает
Булеву мономиальную
систему
на
с параметрами
,
где
и v=supp(u).
Лемма 1.2.1.
-
коммутативная
диаграмма.
Доказательство.
Это прямо доказывается тем что supp(f(u))=f(supp(u)).
Так как
на множестве
всех
таких, что supp(u)=u,
появляется
следующие
прямые следствия.
Следствие 1.2.1.
Фазовое
пространство
– подграф фазового
пространства
.
Следствие 1.2.2.
Предположим
что
– система конечных
элементов. Если
– цикл в фазовом
пространстве
,
тогда
для всех
.
Пример 1.2.1.
Пусть
.
-
состоит из всех
возможных
наборов длины
3 из трёх элементов:
0, 1, 2.
Это наборы:

Используя
функцию
,
определим
переходы в
фазовом пространстве
.
000 -
,
001 -
,
002 -
,
010 -
,
020 -
,
100 -
,
200 -
,
111 -
,
110 -
,
112 -
,
101 -
,
121 -
,
011 -
,
211 -
,
222 -
,
220 -
,
221 –
,
202 -
,
212 -
,
022 -
,
122 -
,
012 -
,
021 -
,
210 -
,
102 -
,
120 -
,
210 -
,
201 -
,
Так как
,
то
.
Используя эту
функцию, определим
переходы в
фазовом пространстве
.
000 -
,
001 -
,
010 -
,
100 -
,
101 -
,
011 -
,
110 -
,
111 -
.
На рисунке
1.2.1 и 1.2.2 изображены
фазовое пространство
системы
и ее «Булеанизяция»
,
соответственно.

Рис. 1.2.1. Фазовое
пространство
.

Рис. 1.2.2. Фазовое
пространство
.
Затем связывается
с
- размерной
линейной системой
над конечным
кольцом. Заметим
сначала что
– изоморфный,
как Абелева
группа, для
через изоморфизм
,
появляется
возможность
генератора
для циклической
группы
.
В первую очередь
обратим внимание,
что множество
векторов
со всеми ненулевыми
вхождениями
– постоянны
для
.
Пусть
– генератор
для циклической
группы
,и
пусть
.
Тогда
.
Определение 1.2.2.
Обозначим
для
.
Видно что
– линейное
преобразование
-
элемента. Но
можно рассматривать
его, как линейное
преобразование
для
- элемента,
рассматривая
как конечное
кольцо, которое
обозначим –