Мономиальные динамические системы

Федеральное агентство по образованию Российской Федерации

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО

Кафедра дискретной математики

и информационных технологий

Курсовая работа

МОНОМИАЛЬНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ

Студента 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.

Обозначим для .

Видно что – линейное преобразование - элемента. Но можно рассматривать его, как линейное преобразование для - элемента, рассматривая как конечное кольцо, которое обозначим – . То есть, имеется линейное преобразование .

Это доказывает следующую лемму.

Лемма 1.2.2.

- коммутативная диаграмма.

Обратим внимание, что вертикальные стрелки – изоморфизмы. Это значит, что они сохраняют фазовое пространство структуры, включая длину конечных циклов. В частности, имеется следующее следствие.

Следствие 1.2.3.

Фазовое пространство изоморфно к подграфу фазового пространства , состоя из всех наборов с базисным вектором .

Пример 1.2.2.

Для мономиальной системы в примере 1.2.1, определим , где

.

Рассчитаем переходы в фазовом пространстве .

000 - ,

001 - ,

010 - ,

011 - ,

100 - ,

101 - ,

110 - ,

111 - .

Фазовое пространство изображено на рисунке 1.2.3.

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

Теорема 1.2.1.

Пусть – мономиальная динамическая система. Тогда – система конечных элементов тогда, и только тогда, когда и – системы конечных элементов.

Доказательство.

Из следствий 1.2.1 и 1.2.3, если – система конечных элементов, то и тоже системы конечных элементов. Для доказательства от противного, предположим что и – системы конечных элементов, а – нет. Для каждого конечного цикла , любой из двух связанных наборов имеет все координаты ненулевые, или все наборы имеют минимум одну нулевую координату. В первом случае из этого следует, что имеет конечный цикл, той же длины. Следовательно, если имеет конечный цикл длины большей чем , тогда включаются только наборы имеющие минимум одну нулевую координату.

Пусть – наборы в конечном цикле. Так как этот конечный цикл должен отображать конечный элемент для из этого следует, что имеет тот же самый базисный вектор, то есть, тот же самый образец нулевых вхождений, и отличается только в ненулевых координатах. Кроме того, мономы в ненулевых координатах не включают никакие переменные, соответствующие нулевым координатам. Таким образом, если построить новый набор , заменяя каждый в , на , – будет частью конечного цикла длины, по крайней мере , что является противоречием. Это доказывает теорему.

1.3 Линейные системы над конечными коммутативными кольцами

Теорема в предыдущей части показывает что для того чтобы решить, будет ли данная мономиальная система , над конечной областью , системой с конечными элементами, достаточно решить этот вопрос для связанных булевых систем, для которых определена линейная система над конечным кольцом . Поэтому остаётся развить критерий для линейных систем над конечными коммутативными кольцами, для того чтобы решить будет ли система – системой конечных элементов. Здесь мы сведем общий случай к имеющему первичную мощность.

Путь для взаимно простых целых чисел и , и пусть –линейная система для размерности . Выбрав изоморфизм получим, что – изоморфно к произведению , где и – линейные системы над и , соответственно. Используя факт того, что фазовое пространство является прямым произведением тогда, когда ориентированы графы фазовых пространств для и , мы получаем следующий результат.

Предположение 1.3.1.

Пусть для взаимно простых целых чисел и , и пусть – линейная система над размерности . Пусть и – линейные преобразования над и , соответственно. Тогда – система конечных элементов тогда, и только тогда, когда и – системы конечных элементов.

Имея цель развить критерий для изучения систем конечных элементов, достаточно изучить линейные системы над кольцами вида для простых чисел . Следующая теорема обеспечивает критерий для дальнейшего решения проблемы с линейной системой над областью простых чисел .

Теорема 1.3.1.

Пусть – линейное отображение, и пусть – проекционное отображение на . Тогда , где . Тогда фазовое пространство – изоморфно подграфу фазового пространства .

Доказательство.

Пусть определяется . Тогда легко проверить что , так как – линейные отображения для всех . Поэтому, прямо проверяется что тогда, и только тогда, когда , и, следовательно, фазовое пространство изоморфно подграфу фазового пространства .

Следствие 1.3.1.

Пусть – линейное отображение, и пусть – проекционное отображение на . Если не является системой конечных элементов, тогда – не является системой конечных элементов.

Пример 1.3.1.

Пусть определяется . Тогда .

- состоит из всех возможных наборов длины 2 из четырёх элементов: 0, 1, 2,3.

Это наборы:

Используя функцию , определим переходы в фазовом пространстве .

00 - ,

01 - ,

02 - ,

03 - ,

10 - ,

11 - ,

12 - ,

13 - ,

20 - ,

21 - ,

22 - ,

23 - ,

30 - ,

31 - ,

32 - ,

33 - .

Так как , переходы в фазовом пространстве определены следующим образом.

00 - ,

01 - ,

10 - ,

11 - .

Фазовые пространства и изображены на рисунках 1.3.1 и 1.3.2, соответственно.

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

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

ЗАКЛЮЧЕНИЕ

Результат позволяет изучить динамику линейных систем над конечными кольцами, в частности для нахождения критерия для линейной системы быть системой конечных элементов. Также обеспечивается алгоритм решения того, чтобы мономиальная система над произвольной конечной областью была системой конечных элементов. Однако, пока, трудно изучается даже динамика линейных систем над кольцам вида , из-за недостатка уникальной факторизации в полиномиальном кольце .

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Colon-Reyes O., Jarrah A., Laubenbacher R., Sturmfels B. Monomial dynamical systems over finite fields// Complex Systems. 2006. Том 16, стр. 333-342.