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

В настоящей статье рассматривается один из принципиальных вопросов, возникающий при моделировании дискретно-временных динамических систем с антиципацией — вычислительные затраты. Подробно представлены процедуры расчета периода циклических траекторий для ДСА и описаны их сложности. Предложен и обосно...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблемы управления и информатики
Дата:	2019
Автори:	Лазаренко, С.В., Макаренко, А.С.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Теми:	Математическое моделирование и исследование сложных управляемых систем
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/180781
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Вычислительные сложности моделирования динамических систем с антиципацией / С.В. Лазаренко, А.С. Макаренко // Проблемы управления и информатики. — 2019. — № 2. — С. 37-47. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-180781
record_format	dspace
spelling	Лазаренко, С.В. Макаренко, А.С. 2021-10-18T18:53:11Z 2021-10-18T18:53:11Z 2019 Вычислительные сложности моделирования динамических систем с антиципацией / С.В. Лазаренко, А.С. Макаренко // Проблемы управления и информатики. — 2019. — № 2. — С. 37-47. — Бібліогр.: 14 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180781 519.7 В настоящей статье рассматривается один из принципиальных вопросов, возникающий при моделировании дискретно-временных динамических систем с антиципацией — вычислительные затраты. Подробно представлены процедуры расчета периода циклических траекторий для ДСА и описаны их сложности. Предложен и обоснован переход описания состояний ДСА на мультимножества для понижения вычислительных затрат в ходе поиска циклических траекторий. Поняття антиципації передбачає залежність майбутніх станів не лише від минулих, а й від самих майбутніх станів. Одна з основних причин, що обумовлює актуальність дослідження систем із антиципацією, — це надресурсоємність задачі моделювання систем із множинними сценаріями розвитку, оскільки антиципаційні системи часто передбачають багатозначність розв’язків. Невелика кількість робіт в даній області інформатики також обумовлена часто некоректністю постановки задачі в силу існування кількох можливих розв’язків. Тим самим системи із антиципацією представляють новий напрям в кібернетиці та моделі на основі антиципації більш точно можуть формально описувати велику кількість існуючих систем та процесів порівняно з класичними моделями із запізненням. Розглянуто такі нелінійні дискретні динамічні системи із сильною антиципацією, у яких майбутні стани можна представити явною залежністю від минулих за допомогою оператора Хатчинсона. Еволюція таких динамічних систем здійснюється в хаусдорфовому метричному просторі. Розглянуто принципову проблему моделювання таких систем — обсяг використання обчислювальних ресурсів. Введено ряд означень для дослідження динаміки систем із антиципацією. Представлено необхідні поняття теорії обчислювальних складностей. Важливий інструмент дослідження динаміки систем — карта динамічних режимів, побудова якої вимагає адаптації процедур пошуку періодичних траєкторій для систем такого типу. Запропоновано та детально описано процедури пошуку періодичних траєкторій динамічних систем із антиципацією. Послідовно отримано часові та просторові складності побудови станів, траєкторій та цих процедур в цілому. З метою мінімізації часової складності в ході симуляції систем із антиципацією обґрунтовано представлення станів відповідних динамічних систем за допомогою мультимножин. З метою подальшої оптимізації обчислювальних витрат слід враховувати структуру фазового простору динамічної системи із антиципацією, комбінуючи запропоновані процедури. The concept of anticipation stands for the dependence of future states not only on the past, but also on themselves. One of the main reasons for the relevance of the study of the anticipatory systems is the over-complexity of modeling of the systems with multiple possible scenarios, since anticipatory systems often imply multiple solutions. A non-prevalence of this field of computer science is also often caused by not well-posing of the problem due to non-uniqueness of the solutions. Thus, systems with anticipation represent a new direction in cybernetics and the models based on anticipation can more formally describe a large number of existing systems and processes, compared with classical models with delay. In current paper, we consider such nonlinear discrete dynamical systems with strong anticipation, in which future states can be represented by an explicit dependence on the past with the help of the Hutchinson operator. The evolution of such dynamical systems is carried out in a Hausdorff metric space. The article focuses on the fundamental problem of modeling such systems – the amount of use of computing resources. A number of definitions have been introduced to study the dynamics of anticipatory systems. The necessary concepts of the theory of computational complexity are presented. An important tool for studying the dynamics of systems is the Atlas of Charts of dynamic regimes. The construction of which requires the adaptation of procedures for finding periodic trajectories for systems of this type. The article proposes and describes in detail the procedures for searching for periodic trajectories of dynamical systems with anticipation. Time and spatial complexities are obtained for the construction of states, trajectories, and these procedures in general. In order to minimize the time complexity during the simulation of anticipatory systems, the presentation of the states of the corresponding dynamical systems with the help of multisets is justified. In order to optimize further computational costs, one should take into account the structure of the phase space of a dynamical system with an anticipation, thereby combining the proposed procedures. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Математическое моделирование и исследование сложных управляемых систем Вычислительные сложности моделирования динамических систем с антиципацией Обчислювальні складності моделювання динамічних систем з антиципацією Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Вычислительные сложности моделирования динамических систем с антиципацией
spellingShingle	Вычислительные сложности моделирования динамических систем с антиципацией Лазаренко, С.В. Макаренко, А.С. Математическое моделирование и исследование сложных управляемых систем
title_short	Вычислительные сложности моделирования динамических систем с антиципацией
title_full	Вычислительные сложности моделирования динамических систем с антиципацией
title_fullStr	Вычислительные сложности моделирования динамических систем с антиципацией
title_full_unstemmed	Вычислительные сложности моделирования динамических систем с антиципацией
title_sort	вычислительные сложности моделирования динамических систем с антиципацией
author	Лазаренко, С.В. Макаренко, А.С.
author_facet	Лазаренко, С.В. Макаренко, А.С.
topic	Математическое моделирование и исследование сложных управляемых систем
topic_facet	Математическое моделирование и исследование сложных управляемых систем
publishDate	2019
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Обчислювальні складності моделювання динамічних систем з антиципацією
description	В настоящей статье рассматривается один из принципиальных вопросов, возникающий при моделировании дискретно-временных динамических систем с антиципацией — вычислительные затраты. Подробно представлены процедуры расчета периода циклических траекторий для ДСА и описаны их сложности. Предложен и обоснован переход описания состояний ДСА на мультимножества для понижения вычислительных затрат в ходе поиска циклических траекторий. Поняття антиципації передбачає залежність майбутніх станів не лише від минулих, а й від самих майбутніх станів. Одна з основних причин, що обумовлює актуальність дослідження систем із антиципацією, — це надресурсоємність задачі моделювання систем із множинними сценаріями розвитку, оскільки антиципаційні системи часто передбачають багатозначність розв’язків. Невелика кількість робіт в даній області інформатики також обумовлена часто некоректністю постановки задачі в силу існування кількох можливих розв’язків. Тим самим системи із антиципацією представляють новий напрям в кібернетиці та моделі на основі антиципації більш точно можуть формально описувати велику кількість існуючих систем та процесів порівняно з класичними моделями із запізненням. Розглянуто такі нелінійні дискретні динамічні системи із сильною антиципацією, у яких майбутні стани можна представити явною залежністю від минулих за допомогою оператора Хатчинсона. Еволюція таких динамічних систем здійснюється в хаусдорфовому метричному просторі. Розглянуто принципову проблему моделювання таких систем — обсяг використання обчислювальних ресурсів. Введено ряд означень для дослідження динаміки систем із антиципацією. Представлено необхідні поняття теорії обчислювальних складностей. Важливий інструмент дослідження динаміки систем — карта динамічних режимів, побудова якої вимагає адаптації процедур пошуку періодичних траєкторій для систем такого типу. Запропоновано та детально описано процедури пошуку періодичних траєкторій динамічних систем із антиципацією. Послідовно отримано часові та просторові складності побудови станів, траєкторій та цих процедур в цілому. З метою мінімізації часової складності в ході симуляції систем із антиципацією обґрунтовано представлення станів відповідних динамічних систем за допомогою мультимножин. З метою подальшої оптимізації обчислювальних витрат слід враховувати структуру фазового простору динамічної системи із антиципацією, комбінуючи запропоновані процедури. The concept of anticipation stands for the dependence of future states not only on the past, but also on themselves. One of the main reasons for the relevance of the study of the anticipatory systems is the over-complexity of modeling of the systems with multiple possible scenarios, since anticipatory systems often imply multiple solutions. A non-prevalence of this field of computer science is also often caused by not well-posing of the problem due to non-uniqueness of the solutions. Thus, systems with anticipation represent a new direction in cybernetics and the models based on anticipation can more formally describe a large number of existing systems and processes, compared with classical models with delay. In current paper, we consider such nonlinear discrete dynamical systems with strong anticipation, in which future states can be represented by an explicit dependence on the past with the help of the Hutchinson operator. The evolution of such dynamical systems is carried out in a Hausdorff metric space. The article focuses on the fundamental problem of modeling such systems – the amount of use of computing resources. A number of definitions have been introduced to study the dynamics of anticipatory systems. The necessary concepts of the theory of computational complexity are presented. An important tool for studying the dynamics of systems is the Atlas of Charts of dynamic regimes. The construction of which requires the adaptation of procedures for finding periodic trajectories for systems of this type. The article proposes and describes in detail the procedures for searching for periodic trajectories of dynamical systems with anticipation. Time and spatial complexities are obtained for the construction of states, trajectories, and these procedures in general. In order to minimize the time complexity during the simulation of anticipatory systems, the presentation of the states of the corresponding dynamical systems with the help of multisets is justified. In order to optimize further computational costs, one should take into account the structure of the phase space of a dynamical system with an anticipation, thereby combining the proposed procedures.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/180781
citation_txt	Вычислительные сложности моделирования динамических систем с антиципацией / С.В. Лазаренко, А.С. Макаренко // Проблемы управления и информатики. — 2019. — № 2. — С. 37-47. — Бібліогр.: 14 назв. — рос.
work_keys_str_mv	AT lazarenkosv vyčislitelʹnyesložnostimodelirovaniâdinamičeskihsistemsanticipaciei AT makarenkoas vyčislitelʹnyesložnostimodelirovaniâdinamičeskihsistemsanticipaciei AT lazarenkosv občislûvalʹnískladnostímodelûvannâdinamíčnihsistemzanticipacíêû AT makarenkoas občislûvalʹnískladnostímodelûvannâdinamíčnihsistemzanticipacíêû
first_indexed	2025-11-26T01:39:50Z
last_indexed	2025-11-26T01:39:50Z
_version_	1850603891341656064
fulltext	© С.В. ЛАЗАРЕНКО, А.С. МАКАРЕНКО, 2019 Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 37 УДК 519.7 С.В. Лазаренко, А.С. Макаренко ВЫЧИСЛИТЕЛЬНЫЕ СЛОЖНОСТИ МОДЕЛИРОВАНИЯ ДИНАМИЧЕСКИХ СИСТЕМ С АНТИЦИПАЦИЕЙ Ключевые слова: вычислительная сложность, дискретные динамические системы, оператор Хатчинсона, периодическая траектория. Введение Моделирование динамических систем, операторы эволюции которых преду- сматривают многозначность решений, — относительно новое направление теоре- тической кибернетики. Актуальность и значительный прикладной потенциал за- ключаются в построении новых моделей, которые, в некоторой степени, будут лучше описывать и формализовать ряд сложных явлений и процессов, так как предполагают некую рефлексивную составляющую. К числу таких процессов, несомненно, можно отнести такие социально-экономические рефлексивные про- цессы: общественное и индивидуальное сознание [1], моделирование транспорт- ных потоков [2] (являющееся важной задачей управления инфраструктурой совре- менных крупных городов) и др. В ходе моделирования систем с многозначными операторами эволюции так или иначе сталкиваются с проблемами объемов вычислений и нелинейным ро- стом использования машинной памяти. Поэтому именно эти принципиальные ас- пекты моделирования динамических систем с антиципацией (ДСА) находятся в фокусе данной статьи. В частности, рассматриваются вопросы вычислительных сложностей процедур поиска периода циклических траекторий при моделирова- нии таких систем. 1. Математическая модель Для начала введем необходимые определения и принятые обозначения. С более детальной терминологией антиципационных систем можно ознакомиться в работе [3] и по ссылкам в ней. В качестве примера рассмотрим исходную систему, описыва- емую законом сильной антиципации первого порядка: ),,( 11   iii xxfx , ,,2,1,0,  iRx n i (1) где 2);( R — управляющий параметр, nnn RRRRf  2: — оператор связи, ix — состояние неявной системы. Нас интересует случай, когда f предполагает возможную многозначность решений. Исходя из этих соображений, вводим следующие определения. Часто под состоянием антиципационной динамической системы (ДС) понимают именно ix в (1), однако в контексте нашей задачи по поиску периодических траекторий будем придерживаться следующего определения. Определение 1. Состояниями ДС в явном виде в дискретные моменты ,1,0i , будем называть такие множества: n k i ki SxX  }{ . Здесь nS — под- множество множества всех возможных подмножеств nR ( nR nS 2 ). 38 ISSN 0572-2691 Пусть оператор f в (1) предусматривает многозначность решений, и его можно представить отображением n n n SRSF  )dim( : в виде   1 ),(),( 1    iXx k kii xfXFX , (2) здесь ni SX  , nRx , )dim(,1,),,,,( )dim(21   iRn i . С необходимыми понятиями теории многозначных отображений и многознач- ного анализа, которые используются в данной статье, можно ознакомиться, напри- мер, в [4; 5]. При таком представлении нашей антиципационной ДС (2) через явную зависимость текущего ее состояния от предыдущих (по времени) состояний опера- тор )(F будем называть оператором эволюции ДС с антиципацией. Определение 2. Траекторией ДС, заданной правилом смены состояний (2) под действием оператора )(F , начиная с состояния в момент i , будем называть по- следовательность состояний kiiii XXXX  ,,,, 21  . Если k — конечное, то речь пойдет о конечной части траектории. Определим на nS метрику Хаусдорфа )},(infsup),,(infsup{max),( yxyxYXd XxYyYyXx H   , (3) где nSYX , , )(, — евклидова метрика. Заранее зададим достаточно малое значение  , которое будет представлять точность расчетов периодических орбит нашей ДС. Определение 3. Под неподвижной точкой периода p антиципационной ДС будем понимать набор последовательных состояний 11 ,,,  piii XXX  таких, что p — наименьше положительное, при котором 0)),(,( 1    ipiiH XFXd . Практически для определения периода будем использовать условие ,( iH Xd  )),( 1piXF . Определение 4. Возмущенным состоянием ДС с антиципацией относи- тельно состояния ni SX  будем называть такое состояние ni SX  , что iiiH xXXd ~),(  , где n i Rx ~ — возмущение iX . Такое определение задает неоднозначность iX  . Понятно, что, возмущая iX разными способами с помощью ix~ так, чтобы iiiH xXXd ~),(  , можно полу- чить различные результаты в ходе итерирования (2). Для большей определенно- сти будем возмущать iX следующим образом: }~\|{~ iiiii XxxxxXX  . 2. Теория алгоритмов и вычислительные модели Хотя само понятие алгоритма кажется довольно очевидным, его формализацию заложили относительно недавно — в первой половине ХХ века. Прежде всего этим мы обязаны диссертации А.М. Тьюринга, работам А. Черча, Е.Л. Поста [6], А.Н. Колмогорова, А.А. Маркова и др. [7, 8]. В настоящее время практическое применение и актуальность теории алго- ритмов не вызывает никаких сомнений, поскольку работа практически всей тех- Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 39 ники базируется на основах этой теории. Именно работы Тьюринга и Дж. фон Неймана дали основной теоретический толчок к созданию ЭВМ [9]. В настоящее время теория алгоритмов охватывает значительный спектр вопросов: начиная от первичных, формировавших ее, — вопрос вычислимости функций, вычислитель- ных моделей, сложности вычислений и отношение между их классами; и заканчи- вая построением новых типов алгоритмов и их классификации — управляющие, вычислительные и тому подобное. С прикладной точки зрения, в теории алго- ритмов, прежде всего, стоят задачи анализа трудоемкости алгоритмов, их классификация по сложностям и определение и оптимизация их ресурсоемко- сти. Так, среди основных прикладных достижений теории алгоритмов есть наработки практических рекомендаций по проектированию и разработке про- граммных систем, что наряду с усовершенствованием аппаратного обеспече- ния обусловливают решение ряда задач математического моделирования, ре- шение которых до недавних пор было невозможным. Несмотря на постоянно рас- тущую вычислительную мощность машин, вопрос сложности алгоритмов актуален и поныне. Поэтому именно этот вопрос, так или иначе, будет прохо- дить через всю статью как основной. Алгоритм [10, с. 99; 11, с. 135] есть предписание, однозначно определяющее ход некоторых конструктивных процессов. Он задает переход от одного состоя- ния процесса в другое под действием некоторого оператора «непосредственной переработки» состояний. Этот оператор задается конечным набором правил. Один и тот же алгоритм может задавать различные процессы, которые отличаются лишь начальным состоянием. Алгоритмический процесс состоит из отдельных шагов наперед заданной сложности. Для построения алгоритма необходимо иметь алфавит, с помощью которого представлены состояния процесса. Формально алгоритм можно представить как функцию   BBf : , которая превращает одно конечное слово в другое из того же алфавита B (в качестве ал- фавита, как правило, берут }1,0{B ). B обозначает множество всех конечных последовательностей номеров из B , т.е.  0   i iBB при всех конечных i , где iB — множество всех конечных последовательностей из B длиной i . Расчет та- кой функции f осуществляется на некоторой вычислительной модели. Эта мо- дель задается фиксированным набором правил, при последовательном примене- нии их можно рассчитать )(xf для любого входного слова Bx . Каждое пра- вило представляет собой комбинацию базовых операций этой модели. Например, такими операциями для машины Тьюринга могут быть следующие: прочитать символ с входной ленты, прочитать символ из рабочей области памяти, записать символ на ленту, остановка расчета или выбор следующей операции. Кроме базо- вых операций в определение модели также включена и цена (cost) этих операций для определения сложности данного алгоритма. Из самых распространенных вы- числительных моделей отметим [12, с. 5]: Машина Тьюринга, лямбда-исчисление, регистровые машины. Сейчас существует достаточно большое количество раз- личных модификаций и производных моделей: недетерминированные машины Тьюринга, клеточные автоматы и тому подобное [13]. 3. Теория сложности вычислений На множестве алгоритмов вводят такие характеристики, как понятие мер сложности для сравнения алгоритмов и выбора «лучшего» по заданному кри- 40 ISSN 0572-2691 терию. Эта мера сложности описывается количеством вычислительных ресурсов, необходимых для выполнения данного алгоритма. Основными мерами явля- ются время выполнения (временная сложность) алгоритма на данной вычисли- тельной модели (его скорость выполнения) и объем памяти (пространственная сложность), который нужен для того, чтобы выполнить алгоритм на той же вычислительной модели. Временем выполнения алгоритма )(nT для данной вычислительной модели является количество базовых операций, которые выполняются для преобразова- ния входного слова x длиной n . Временная сложность алгоритма в худшем слу- чае определяется как )(max)( \|\| max xtnt nx   . При вычислении точного значения использованных ресурсов для выполнения алгоритма в нем фигурируют постоянные составляющие — затраты на выполне- ние базовых операций, которые будут зависеть от конкретной вычислительной модели. Однако с ростом размера входных данных (длины входного слова x ) их влияние нивелируется вместе со слагаемыми низших порядков. Поэтому в теории вычислительных сложностей расчет сложности алгоритма проводится асимптоти- чески, т.е. оцениваются затраты ресурсов (времени или памяти) в предельном случае — когда размер входных данных стремится к бесконечности. В асимптотическом анализе приняты следующие определения [12, с. 8]. Пусть некоторый алгоритм имеет вычислительную сложность )(nf . Определение 5. Оценка сложности алгоритма ))(( ng задает множество та- ких функций )(nf , если существуют некоторые константы 0, 21 cc и некоторый номер 0n , 0nn  , для которых будет выполняться )()()(0 21 ngcnfngc  . В таком случае говорят, что )(ng — асимптотически точная оценка )(nf . Аналогично вводят понятие асимптотически верхней и нижней оценок. Определение 6. Оценка сложности алгоритма ))(( ng задает множество та- ких функций )(nf , если существуют некоторая константа 0c и некоторый но- мер 0n , 0nn  , для которых будет выполняться )()(0 ngcnf  . Полагаем, что )(ng — асимптотически верхняя оценка )(nf . 4. Расчет вычислительных сложностей ДСА Рассмотрим главный вопрос данной статьи: какие необходимые вычисли- тельные затраты мы понесем в ходе численного моделирования ДСА для поиска периодических траекторий? Для данной задачи выделим следующие подзадачи по расчету вычислительных сложностей: построение состояния ДС, сравнение не- скольких таких состояний, построение последовательности состояний. Прежде всего введем ряд необходимых обозначений. Пусть имеем траекторию, дискрет- ную ДСА ,,, 210 XXX . Поскольку ДСА часто можно представить в явном виде оператором Хатчинсона от предыдущих состояний, то кардинальные числа \|\| iX , в худшем случае (например, без образования циклов) будут расти по показатель- ному закону i i NXX  \|\|\|\| 0 , ,2,1,0i , (4) где N — количество селекторов в операторе Хатчинсона (2). Из-за этой особен- ности ДСА при их моделировании вопрос вычислительных затрат становится Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 41 особенно острым. Рассчитаем вычислительные сложности процедур поиска пери- одических траекторий. На их основе сможем скорректировать и улучшить пред- ложенные процедуры с точки зрения минимизации вычислительной сложности. Будем придерживаться следующих необходимых обозначений:  nc — вычислительные затраты на сравнение двух чисел в nR ;  nm — вычислительные затраты на расчет функции, действующей в nR ;  p — максимальная длина цикла, которую рассматриваем. 4.1. Сложность построения состояния ДСА. Каждая итерация эволюции ДСА сопровождается построением очередного состояния системы, поэтому рассмотрим вычислительные затраты на каждой итерации. Имеет место сле- дующая теорема. Теорема. Вычислительная сложность построения каждого состояния ,,2,1,0, iXi в худшем случае будет )( 2iNO . Доказательство. Пусть состояние },,,{ \|\|21 i X ii i i xxxX  построено на основе предыдущего },,,{ 11 2 1 11 1     i X ii i i xxxX  . Определим вычислительную слож- ность построения iX на множестве конечных кардинальных чисел как отображе- ние )(km (здесь k — мощность состояния iX ), так как сложность в первую оче- редь будет зависеть не от номера итерации, а от мощности состояния. Рассмотрим наихудший сценарий в смысле вычислительных затрат, для которого мощность состояний будет расти по показательному закону \|\|\|\| 1 ii XNX . Сначала действуем первым селектором оператора )(F на первую точку в 1iX согласно (2), т.е. )( 1 111  ii xfx . В результате имеем первую точку в iX , по- лучив вычислительные затраты только на операцию расчета точки в nR , слож- ность которой nm . Для следующей точки )( 1 212  ii xfx проведем операцию со сложностью nn cm  , поскольку дополнительно придется проверить, принадле- жит ли ix2 состоянию iX (сравнив ее с ix1 ). Для всех последующих точек i jx (полученных по всем остальным точкам с 1iX и по всем остальным селекторам) будут проведены операции сложности nn cjm  )1( , где \|\| iXj  . Таким обра- зом, сложность построения состояния iX . 2 )1( )())1(()()( 1 0 n n nn ki i nnnnn c kkmk cimckmcmmkm       Учитывая \|\|\|\|)( 0XNXik i i  , переходим к определению сложности построе- ния состояния в зависимости от номера i этого состояния: in n in NX c mN Xc im        \|\| 22 \|\| )( 0 2 2 0 , (5) она и будет ограничена по отношению к функции iN2 при i . Теорема доказана. 42 ISSN 0572-2691 Как видно из (5), наибольшие вычислительные затраты )( 2iNO приходятся на операции сравнения, а на вычисление соответствующих точек в nR — только )( iNO . В этом и заключается одна из самых больших проблем при моделирова- нии ДСА. Ее можно частично обойти за счет представления iX как мультимно- жеств (отсутствуют затраты на сравнение 0nc ), тогда в (5) останется только составляющая )( iNO . В таком случае, однако, условие (4) будет иметь место все- гда, независимо от того — регулярный или нет режим ДСА. И как следствие — постоянный рост использования памяти по показательному закону .iN 4.2. Сложность расчета метрики. Так как мы работаем в метрическом пространстве всех непустых компактных подмножеств с метрикой Хаусдорфа ),.(.Hd , разумным будет задаться вопросом — какие вычислительные затраты на ее расчет для двух состояний ( iixX }{ и jjyY }{ ), исходя из определения этой метрики (3)? Как видим, ее расчет состоит из двух видов операций: 1) вычис- ление yxyx def  ),( в евклидовой метрике для nRyx , (затраты на ее рас- чет будем обозначать nd ); 2) сравнение двух значений .).,( , поэтому она по- требует 1c затрат. Количество расчетов ),( ji yx по всем возможным парам ),( ji yx , очевид- но, будет \|\|\|\| YX  . Подсчет ixji j yx  ),(inf для каждой точки ix потребует 1\|\| Y операций сравнения .).,( , а для всех ix их будет \|\|)1\|(\| XY  . Далее необходимо рассчитать }{sup ix i  , на что потребуется 1\|\|)1\|(\|1\|}{\|  XYixi сравнений. В силу коммутативности метрики общее количество сравнений .).,( , которые понадобятся для расчета ),,( YXdH составит  1)1\|\|)1\|((\|2 XY 1\|\|\|\|2  YX . Общие вычислительные затраты для получения ),( jiH XXd , учитывая (4), будут 1 2 011 \|\|)2()1\|\|\|\|2(\|\|\|\| cXNcdcXXdXXd ji njinjiij   или в О-нотации — ).( ji ij NOd  (6) 4.3. Сложность построения траектории ДСА. Следующим шагом после построения состояния ДС является построение их последовательности (траек- тории). Какой же будет сложность построения траектории длиной p , которая начинается из состояния с индексом i ? Обозначим ее ),( piiM  : 1 )1( \|\| 21 )1( 2 \|\| \|\| 22 \|\| )(),( 1 02 )1(222 0 0 2 2 0                                   N NN X c m N NNXc NX c mN Xc kmpiiM pi n n pi n kn n kn pi ik pi ik или в O -нотации — ),(),( 22 piNOpiiM  а в случае мультимножеств )0( nc — ).(),( piNOpiiM  (7) 4.4. Сложность поиска периода циклической траектории ДСА. Задача по- иска периода траекторий выступает как составляющая, например, такого инстру- Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 43 мента анализа ДС, как построение карт динамических режимов ДСА. Детальное описание алгоритма конструирования этих карт можно найти по ссылке [14]. Рас- смотрим возможные процедуры определения периода траектории и их вычисли- тельные сложности. Каждую процедуру разобъем на две составляющие: 1) по- строение состояний ДС в моменты времени ;,,1, jii  2) сравнение новых со- стояний между собой и с ранее полученными в метрике .).,(Hd . Вычислительная оптимизация процедуры поиска периода как раз заключается в комбинировании этих составляющих таким образом, чтобы общая сложность была наименьшей. Рассмотрим следующие возможные процедуры. Процедура А. Суть ее заключается в том, что на каждом шаге построения траектории мы пытаемся найти цикл, сравнивая последнее полученное состояние ДС с предыдущими в обратном времени. Для начала ограничиваемся поиском цикла длиной p . Пусть в некоторый момент времени мы находимся в точке 1iX ДСА. Строим iX согласно (2) и сравниваем это состояние с предыдущими 1i -м, 2i -м и так далее до pi  , пока не найдем достаточно близкое (с заранее задан- ной точностью) состояние в выбранной метрике. Именно такое направление срав- нений выбрано не случайно, чтобы избежать ситуации, когда мы сначала нашли кратный цикл. Таким образом, сначала получим «наименьший» цикл (без удвое- ний, утроений и т.д.). Если найдено такое состояние jX с ),( jiH XXd , то дальнейшие действия вполне понятны. В противном случае продолжаем траекто- рию на одно состояние вперед и повторяем процедуру снова. Нас интересует вопрос: какой будет сложность действий на каждой итерации? Пусть мы ранее построили состояние 1 ki и не нашли цикл длины pk 1 . Строим ki  -е и сравниваем его со всеми ранее построенными в обратном поряд- ке — с ikiki ,,2,1  . Это соответственно потребует таких затрат: .)( 21 ikikikikiki dddkim    Поэтому и вся процедура потребует следующих затрат при итерировании из со- стояния i в состояние pi  , замыкающее найденный цикл длины p :           1 1 11 2121 .),())((... ))2(())1(()( pi ik kj pi kj pipipiipii iiiiii dpiiMdddpim ddimdimim   (8) На протяжении всей процедуры необходимо постоянно держать в памяти по- следние 1p состояний ДС ( piii XXX  ,,, 1  ) для расчета метрик между ними (пространственная сложность), т.е. необходимо держать в памяти    \|\| j pi ij X 1 1 \|\| 1 0     N N NX p i чисел из nR или в O -нотации )( piNO  . Процедура В. Из выражения (8) нетрудно показать, что если в качестве со- стояний ДС выбраны мультимножества ( 0nc ), составляющая по вычислению метрик )(,Hd в процедуре поиска цикла требует значительно больше вычисли- тельных ресурсов, чем построение состояний. Для этого возьмем лишь последнее слагаемое в (8) pipid  1 и сравним его со сложностью ),( piiM  , учитывая (6) и (7). В результате получим ).(),(),( 122 1 pipi pipi NOpiiMNOd    Поэтому следующая альтернативная процедура предусматривает минимиза- цию именно этих вычислений. Для простоты описания данной процедуры рас- смотрим некоторые упрощения и локальные обозначения. Пусть  — наперед за- 44 ISSN 0572-2691 данная точность поиска периодической траектории. Имеем D — область опреде- ления ДСА, которая является объединением предельного множества (цикл перио- да не более p ) и области его притяжения. Исходное состояние ДС — DXi 1 . Начинаем строить траекторию с первой серии итераций 11 ,,,  piii XXX  ( 0s ). Заранее задаем длину этих серий, равную p . Расстояние между такими сериями 1t определяется эмпирически и зависит от особенностей динамики си- стемы (чем быстрее траектория приближается к предельному множеству, тем меньшим выбираем t ). Такое разбиение процесса итерирования на состояния в сериях и вне их обусловлено тем, что операции сравнения состояний будут осу- ществляться только для состояний, имеющихся в сериях, сокращая тем самым вычислительные затраты. Структура траектории согласно этой процедуре пред- ставлена на рис. 1. 1 tpiX iX 1iX 1 piX  piX  1 piX  tpiX   Серия 0s 1s 0s 1s Серия Состояния между сериями и Рис. 1 Таким образом, получим серии, начинающиеся с )( tpsi  и заканчивающи- еся в 1)(  ptpsi , при номерах ,1,0s , поэтому и сложность построения этих частей траектории будет )1)(),((  ptpsitpsiM для ,1,0s Между сериями будут только затраты на построение траекторий: )1)(,)((  tpsittpsiM при ,2,1s Для каждой серии необходимы дополнительные затраты на сравнение всех ее состояний с первым состоянием, которое следует за этой серии (для серии 0s это состояние piX  приведено на рис. 1). Итак, строим piX  . Рассчитываем от- клонения между состояниями текущей серии и :piX  ),,,( )()( 2 )( 1 )( s p sss dddd  , где ),( )()( )( jtpspitpspiH s j XXdd  согласно иллюстрации на рис. 2. iX 1iX  1 piX piX  1d 1pd pd Рис. 2 В таком случае расходы для 0s будут    p j jpipid 1 , , и для каждого ,1,0s : . 1 )(,)(   p j jptpsiptpsid Если найдено такое  )(s kd (понятно, что затраты на сравнение значений метрик здесь будут 1pc ), то процедура поиска цикла завершена и считаем, что ДС имеет период k . Если таких ,, )()( 21 s k s k dd (9) Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 45 несколько, то выбираем тот, у которого наименьший индекс )(min i i k , чтобы зара- нее избежать кратных циклов и сфокусироваться на «наименьшем». Вычисли- тельные расходы на сравнение всех )(s kd (равны 1pc ) и поиска наименьшего из них ( 1)1( cp ) будут .1)12(1)1(1 cpcppc  И наконец, третий вариант: если такое  )(s kd не найдено, то увеличиваем 1 ss и осуществляем следующую серию итераций. Такие серии итерирова- ний ,1,0s проводим до тех пор, пока ),,,(min )()( 2 )( 1 )( s p sss dddm  убывает, но все еще превышает  . Подытожим затраты этой процедуры: .)12( ))(()1)(,( 1 0 1 )(,)( cpd ptpsimptpsiiM s k p j jptpkiptpki        Если стоит задача — убедиться, что мы приблизились к орбите периода именно 1k , то рассматриваем  )()( 1 s k s dm . В таком случае необходимо прово- дить оценку компонентов вектора                                       )( )( 2 )( 1 )1( )1( 2 )1( 1 )1( 11 1 s k s s s k s s s k d d d d d d  . (10) Перейдем к сериям итерированний длиной 1k . В случае 1k -периодической орбиты необходимо, чтобы выполнялось условие 0 )1( 1     s s k . При его нарушении нужно выбрать следующего кандидата 12 kk  из со- отношения (9), отличного от всех ранее рассмотренных из набора  ),,,(min )1()1( 2 )1( 1 s p ss ddd  . Если таковых не осталось, то мы имеем дело либо с орбитой периода больше рассматриваемого p , либо мы попали в область квазипериодичности или хаоса. Такой подход дает возможность более точно определить, имеем мы дело с орбитой именно такого периода или перед нами более сложная структура. Расходы памяти в ходе проведения процедуры близки к расходам процедуры А. Кроме последних 1p состояний ДС в памяти необходимо держать p2 чисел для расчета (10). Поэтому пространственная сложность равна  iNX \|\| 0            n p N N p 2 1 11 чисел из nR или в O -нотации — )( piNO  . Для рассмотренных процедур, в случае если в процессе итерирования траек- тория прерывается (множество действительных значений состояний пустое), то возмущаем 1iX и, начиная с него, снова проводим выбранную процедуру поиска периодической орбиты. Заключение В настоящей статье рассматривается один из принципиальных вопросов, возникающий при моделировании дискретно-временных динамических систем с антиципацией — вычислительные затраты. Подробно представлены проце- 46 ISSN 0572-2691 дуры расчета периода циклических траекторий для ДСА и описаны их слож- ности. Предложен и обоснован переход описания состояний ДСА на мульти- множества для понижения вычислительных затрат в ходе поиска циклических траекторий. Поскольку проблема использования вычислительных ресурсов при модели- ровании ДСА — одна из наиболее значимых, то в дальнейшем, в целях ее мини- мизации в ходе поиска периодических траекторий (например, для построения карт динамических режимов), нужно сосредоточиться на сравнении предложен- ных процедур (с точки зрения вычислительных сложностей). Это сравнение сле- дует проводить с учетом структуры фазового пространства (например, распреде- ления периодических режимов). С.В. Лазаренко, О.С. Макаренко ОБЧИСЛЮВАЛЬНІ СКЛАДНОСТІ МОДЕЛЮВАННЯ ДИНАМІЧНИХ СИСТЕМ З АНТИЦИПАЦІЄЮ Поняття антиципації передбачає залежність майбутніх станів не лише від ми- нулих, а й від самих майбутніх станів. Одна з основних причин, що обумовлює ак- туальність дослідження систем із антиципацією, — це надресурсоємність задачі мо- делювання систем із множинними сценаріями розвитку, оскільки антиципаційні си- стеми часто передбачають багатозначність розв’язків. Невелика кількість робіт в даній області інформатики також обумовлена часто некоректністю постановки за- дачі в силу існування кількох можливих розв’язків. Тим самим системи із антици- пацією представляють новий напрям в кібернетиці та моделі на основі антиципації більш точно можуть формально описувати велику кількість існуючих систем та процесів порівняно з класичними моделями із запізненням. Розглянуто такі нелі- нійні дискретні динамічні системи із сильною антиципацією, у яких майбутні стани можна представити явною залежністю від минулих за допомогою опера- тора Хатчинсона. Еволюція таких динамічних систем здійснюється в хаусдор- фовому метричному просторі. Розглянуто принципову проблему моделювання таких систем — обсяг використання обчислювальних ресурсів. Введено ряд означень для дослідження динаміки систем із антиципацією. Представлено не- обхідні поняття теорії обчислювальних складностей. Важливий інструмент до- слідження динаміки систем — карта динамічних режимів, побудова якої вима- гає адаптації процедур пошуку періодичних траєкторій для систем такого типу. Запропоновано та детально описано процедури пошуку періодичних траєкторій динамічних систем із антиципацією. Послідовно отримано часові та просторові складності побудови станів, траєкторій та цих процедур в цілому. З метою міні- мізації часової складності в ході симуляції систем із антиципацією обґрунтовано представлення станів відповідних динамічних систем за допомогою мультим- ножин. З метою подальшої оптимізації обчислювальних витрат слід враховува- ти структуру фазового простору динамічної системи із антиципацією, комбі- нуючи запропоновані процедури. Ключові слова: обчислювальна складність, дискретні динамічні системи, опе- ратор Хатчинсона, періодична траєкторія. S.V. Lazarenko, A.S. Makarenko THE COMPUTATION COMPLEXITY OF MODELLING OF ANTICIPATORY DYNAMICAL SYSTEMS The concept of anticipation stands for the dependence of future states not only on the past, but also on themselves. One of the main reasons for the relevance of the study of the anticipatory systems is the over-complexity of modeling of the systems with Международный научно-технический журнал «Проблемы управления и информатики», 2019, № 2 47 multiple possible scenarios, since anticipatory systems often imply multiple solu- tions. A non-prevalence of this field of computer science is also often caused by not well-posing of the problem due to non-uniqueness of the solutions. Thus, systems with anticipation represent a new direction in cybernetics and the models based on anticipation can more formally describe a large number of existing systems and pro- cesses, compared with classical models with delay. In current paper, we consider such nonlinear discrete dynamical systems with strong anticipation, in which future states can be represented by an explicit dependence on the past with the help of the Hutchinson operator. The evolution of such dynamical systems is carried out in a Hausdorff metric space. The article focuses on the fundamental problem of modeling such systems – the amount of use of computing resources. A number of definitions have been introduced to study the dynamics of anticipatory systems. The necessary concepts of the theory of computational complexity are presented. An important tool for studying the dynamics of systems is the Atlas of Charts of dynamic regimes. The construction of which requires the adaptation of procedures for finding periodic tra- jectories for systems of this type. The article proposes and describes in detail the pro- cedures for searching for periodic trajectories of dynamical systems with anticipa- tion. Time and spatial complexities are obtained for the construction of states, trajec- tories, and these procedures in general. In order to minimize the time complexity during the simulation of anticipatory systems, the presentation of the states of the corresponding dynamical systems with the help of multi-sets is justified. In order to optimize further computational costs, one should take into account the structure of the phase space of a dynamical system with an anticipation, thereby combining the proposed procedures. Keywords: computational complexity, discrete dynamical systems, Hutchinson op- erator, periodic trajectory. 1. Паутова Л.А., Гуц А.К. Использование теории хаоса и странных аттракторов в исследова- ниях индивидуального и социального сознания. Математические структуры и моделиро- вание. 2004. № 13. С.126–131. 2. Семенов В.В. Математическое моделирование динамики транспортных потоков мегаполи- са. М., 2004. №34. 44 с. (Препр. Ин-та прикладной математики им. М.В. Келдыша). 3. Лазаренко С.В., Макаренко О.С. Аналіз логістичного антиципаційного рівняння із сильною антиципацією. Наукові вісті НТУУ “КПІ”. 2012. № 4. С. 91–96. 4. Борисович Ю. Г., Гельман Б. Д., Мышкис А. Д., Обуховский В. В. Введение в теорию мно- гозначных отображений и дифференциальных включений. М., 2011. 224 c. 5. Половинкин Е.С. Многозначный анализ и дифференциальные включения. М .: Физмат- лит, 2014. 522 с. 6. Díaz Josep, Torras Carme. A personal account of Turing’s imprint on the development of computer science. Computer Science Review. 2012. 6. P. 225–234. DOI: http://dx.doi.org/ 10.1016/j.cosrev.2012.11.001. 7. M. Cover Thomas, Gacs Peter, Gray Robert. Kolmogorov's Contributions to information theory and algorithmic complexity. the annals of probability. 1989. 17. 48 p. DOI: http://dx.doi.org/ 10.1214/aop/1176991250. 8. Guy Leonard Kouemou. History and theoretical basics of hidden Markov models. 2011. 26 p. DOI: http://dx.doi.org/10.5772/15205. 9. Eigenmann Rudolf, Lilja David. Von Neumann computers. 1998. DOI: http://dx.doi.org/10.1002/ 047134608X.W1704. 10. Колмогоров А.Н. Теория информации и теория алгоритмов. М. : Наука, 1987. 304 с. 11. Марков А.А., Нагорный Н.М. Теория алгорифмов. М. : Наука, 1984. 432 с. 12. James Aspnes. Notes on computational complexity theory CPSC 468/568. Spring, 2017. 162 p. 13. Mitchell Melanie. Computation in cellular automata: A Selected Review. 1996. DOI: http://dx.doi.org/10.1002/3527602968.ch4. 14. Лазаренко С.В., Макаренко О.С. Багатопоточні комп’ютерні обчислення у дослідженні не- лінійних динамічних систем. Проблеми програмування. 2013. № 3. С. 109–116. Получено 05.10.2018 После доработки 04.12.2018

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

Репозитарії

Схожі ресурси