Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Жаркова А. В. Индексы состояний в динамической системе двоичных векторов, ассоциированных с ориентациями пальм // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2016. Т. 16, вып. 4. С. 475-484. DOI: 10.18500/1816-9791-2016-16-4-475-484, EDN: XHPYKF

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
14.11.2016
Полный текст:
(downloads: 121)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.1
EDN: 
XHPYKF

Индексы состояний в динамической системе двоичных векторов, ассоциированных с ориентациями пальм

Авторы: 
Жаркова Анастасия Владимировна, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Рассматривается динамическая система двоичных векторов, ассоциированных с ориентациями пальм. Дерево называется пальмой, если оно является объединением цепей, имеющих общую концевую вершину, причём все эти цепи, за исключением, быть может, одной, имеют длину 1. Данная система в зависимости от размерности состояний разбивается на конечные подсистемы. Состояниями конечной динамической системы являются все возможные ориентации данной пальмы, которые естественным образом кодируются двоичными векторами, а эволюционная функция задаётся следующим образом: динамическим образом данной ориентации пальмы является ориентация, полученная из исходной путём переориентации всех дуг, входящих в стоки, других отличий между исходной ориентацией пальмы и её образом нет. Предлагается алгоритм вычисления индексов состояний системы, находится глубина бассейна системы заданной размерности. 

Список источников: 
  1. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
  2. Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2004. Вып. 6. С. 113–125.
  3. Barbosa V. C. An atlas of edge-reversal dynamics. Boca Raton : Chapman&Hall/CRC, 2001. 385 p.
  4. Colon-Reyes O., Laubenbacher R., Pareigis B. Boolean monomial dynamical systems // Annals of Combinatorics. 2004. Vol. 8. P. 425–439. DOI: https://doi.org/10.1007/s00026-004-0230-6.
  5. Салий В. Н. Об одном классе конечных динамических систем // Вестн. Том. гос. ун-та. Приложе- ние. 2005. № 14. С. 23–26.
  6. Исследование эволюционных параметров в дина- мических системах двоичных векторов : свидетельство о государственной регистрации программы для ЭВМ № 2009614409, Рос. Федерация / Власова А. В.; выданное Роспатентом. Зарегистрировано 20.08.2009, Реестр программ для ЭВМ.
  7. Власова А. В. Индексы в динамической системе (B, δ) двоичных векторов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информа- тика. 2011. Т. 11, вып. 3, ч. 1. С. 116–122.
  8. Жаркова А. В. Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов // Прикладная дискретная матема- тика. 2012. № 2 (16). С. 79–85.
  9. Власова А. В. Динамические системы, определяемые пальмами // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : Изд-во Сарат. ун-та, 2009. С. 57– 60.
  10. Жаркова А. В. Аттракторы в конечных динамических системах двоичных векторов, ассоциированных с ориентациями пальм // Прикладная дискретная математика. 2014. № 3 (25). С. 58–67.
  11. Жаркова А. В. О ветвлении и непосредственных предшественниках состояний в конечной динамической системе всех возможных ориентаций графа // Прикладная дискретная математика. Приложение. 2013. № 6. С. 76–78.
Поступила в редакцию: 
23.07.2016
Принята к публикации: 
26.10.2016
Опубликована: 
30.11.2016