Введение к работе
Актуальность темы. В современном мире технологии стремительно развиваются с каждым днем. Сейчас трудно представить себе деятельность крупных организаций без наличия различных автоматизированных систем, поэтому отлаженная работа и надежность сетей занимают важное место для успешного развития. Всё это было бы невозможно, не имей эти структуры под собой фундамента из крепкого математического аппарата.
Так, в задачах, связанных с отказоустойчивостью компьютерных сетей, заметное место занимают графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг. Здесь можно выделить следующие три основные конструкции, получившие и самостоятельное значение в теории графов: минимальное расширение графа (см. [1], [3], [12]), Т-неприводимое расширение графа [4], бесконтурный связный ориентированный граф с заданной структурой источников и стоков [9]. В модели [9] в качестве механизма восстановления работоспособности сети предлагается так называемая SER-динамика бесконтурных связных ориентированных графов. Это позволяет использовать при изучении модельных графов идеи и методы теории конечных динамических систем, и в частности динамических систем двоичных векторов (см., например, [5], [11]) - когда имеется естественная двоичная кодировка графов рассматриваемого класса.
Под динамической системой понимается пара (S, S), где S - непустое множество, элементы которого называются состояниями системы, д: S -> S - отображение множества состояний в себя, называемое эволюционной функцией. Различные интерпретации этого понятия вместе с возникающими конкретными конструкциями и проблематикой составляют предмет общей теории динамических систем, с которой связаны многие теоретические и прикладные исследования как в математике, так и в других естественных науках ([2], [8]).
Заметим, что приведенному определению динамической системы удовлетворяют также такие известные объекты как моноунарная алгебра (унар) и автономный (то есть с одним входным сигналом) автомат без выхода. Они интенсивно изучались различными авторами соответственно в теории алгебраических систем и в теории автоматов. Отметим, например, работы [6], [7], [10], [13].
В приложениях, связанных с дискретной математикой, большой интерес представляют динамические системы, состояния которых наделены некоторой индивидуальной структурой, определяющей
эволюцию состояний. Так, натуральные числа являются состояниями широко известной динамической системы «Зх + 1», с которой связаны многочисленные работы в теории чисел, теории динамических систем, эргодической теории, математической логике и теории алгоритмов (см. [15]). Натуральные числа с фиксированным числом цифр образуют систему Капрекара [14], обобщения которой [16] используются в теоретико-числовых исследованиях. В математической генетике находят приложения булевы динамические системы, состояниями которых являются двоичные векторы заданной размерности [11]. В задачах об отказоустойчивости компьютерных сетей применяется упомянутая SER-динамика, действующая на бесконтурных связных ориентированных графах [9]. Подробнее об этих динамических системах говорится в первой главе.
Динамическая система называется конечной, когда множество S состояний системы является конечным. Каждой конечной динамической системе сопоставляется карта, представляющая собой ориентированный граф с множеством вершин S и дугами, проведенными из каждой вершины s Є S в вершину S(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры в свою очередь называются предельными циклами, или аттракторами.
В теории конечных динамических систем можно выделить следующие задачи. Прежде всего, это само описание динамической системы, в частности, задание её состояний и эволюционной функции. Одной из важнейших проблем является отыскание эволюционных параметров без проведения динамики. К числу таких характеристик относятся ветвление состояния (количество его непосредственных предшественников), индекс состояния (его расстояние до аттрактора того бассейна, которому оно принадлежит), принадлежность состояния аттрактору. Также интерес представляет исследование вида самих динамических систем, их карт, бассейнов, в частности, какие аттракторы имеет система, их количество, вид и длина, умение определять количество начальных состояний системы (недостижимых, то есть с нулевым ветвлением, состояний), наибольший из индексов состояний.
Цель работы. Изучение конечных динамических систем двоичных векторов, ассоциированных с цепями и циклами, исследование вида и основных характеристик таких систем, отыскание различных параметров динамических систем без проведения динамики.
Методы исследования. При выполнении работы применялись различные методы исследования теории графов, теории динамических систем, теории дискретных систем, комбинаторики, теории алгоритмов.
Научная новизна и выносимые на защиту положения. Основные результаты диссертации, выносимые на защиту:
1. Доказана теорема о ветвлении в конечных динамических системах,
ассоциированных с графами, показано, какие именно существуют
непосредственные предшественники у данного состояния системы,
описано свойство недостижимости состояния системы.
2. Введена динамическая система двоичных векторов,
ассоциированных с ориентациями циклов.
3. Описаны аттракторы, их количество, размерность и вид, в
динамических системах двоичных векторов, ассоциированных с цепями
и циклами, а также определены свойства принадлежности состояния
аттрактору в данных системах.
4. Предложены и обоснованы эффективные алгоритмы для подсчёта
индексов состояний в динамических системах двоичных векторов,
ассоциированных с цепями и циклами. Определены максимальные
индексы в подсистемах заданной размерности указанных динамических
систем.
-
Описаны недостижимые состояния динамической системы двоичных векторов, ассоциированных с ориентациями циклов. Подсчитаны количества недостижимых состояний в подсистемах заданной размерности динамических систем двоичных векторов, ассоциированных с цепями и циклами.
-
Получены различные статистические данные с помощью написанных автором программ для ЭВМ, в частности [А4].
7. Приведены карты динамических систем двоичных векторов,
ассоциированных с цепями и циклами начальных размерностей.
Все вышеназванные результаты являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные в диссертационной работе результаты могут быть использованы при построении и анализе различных дискретных систем, моделируемых графами.
Апробация работы. Результаты представляемой работы обсуждались на научных семинарах кафедры теоретических основ компьютерной безопасности и криптографии Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов, 2007, 2010-2012 года) и на объединенном семинаре по дискретной математике и математической кибернетике Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов, 2012 год). Результаты исследований также докладывались на следующих научных мероприятиях: Научные студенческие конференции Саратовского государственного университета (г. Саратов, 2005, 2006,
2008 годы); I Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых (г. Нальчик, 2008 год); Научная конференция «Компьютерные науки и информационные технологии» (г. Саратов, 2010 год); XVIII и XIX Международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов - 2011» и «Ломоносов - 2012» (г. Москва, 2011 и 2012 год соответственно); VIII Всероссийская межвузовская конференция молодых ученых (г. Санкт-Петербург, 2011 год); XVI Международная конференция «Проблемы теоретической кибернетики» (г. Нижний Новгород, 2011 год); X Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT11 (г. Томск, 2011 год).
Публикации. Основные результаты опубликованы в работах автора [А 1-А 14]. Работы автора [А 10], [А 12], [А 13] опубликованы в изданиях, включенных в «Перечень ведущих рецензируемых научных журналов и изданий» ВАК, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук.
Структура и объем работы. Диссертационная работа состоит из введения, трёх глав, заключения, списка использованных источников, включающего 43 наименования, и двух приложений. Диссертация изложена на 119 листах.
