Федеральноеагентство по образованию Российской Федерации
САРАТОВСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО
Кафедра дискретной математики
иинформационных технологийКурсовая работаМОНОМИАЛЬНЫЕ ДИНАМИЧЕСКИЕСИСТЕМЫ
Студента 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. Фазовоепространство />.
ЗАКЛЮЧЕНИЕ
Результат позволяетизучить динамику линейных систем над конечными кольцами, в частности длянахождения критерия для линейной системы быть системой конечных элементов. Такжеобеспечивается алгоритм решения того, чтобы мономиальная система надпроизвольной конечной областью была системой конечных элементов. Однако, пока,трудно изучается даже динамика линейных систем над кольцам вида />, из-за недостаткауникальной факторизации в полиномиальном кольце />.
СПИСОКИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1. Colon-Reyes O., Jarrah A.,Laubenbacher R., Sturmfels B. Monomial dynamical systems over finite fields//Complex Systems. 2006. Том 16, стр. 333-342.