85998 (Мономиальные динамические системы)
Описание файла
Документ из архива "Мономиальные динамические системы", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85998"
Текст из документа "85998"
Федеральное агентство по образованию Российской Федерации
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО
Кафедра дискретной математики
и информационных технологий
Курсовая работа
МОНОМИАЛЬНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ
Студента 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.
Фазовое пространство изоморфно к подграфу фазового пространства , состоя из всех наборов с базисным вектором .