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

Федеральне агентство з освіти Російської Федерації

САРАТОВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ІМЕНІ Н. Г. Чернишевського

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

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

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

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

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