автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Новые теоретико-графовые подходы в моделировании сложных систем

ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В. КЕЛДЫША РОССИЙСКОЙ АКАДЕМИИ НАУК

КОЧКАРОВ Азрет Ахматович

НОВЫЕ ТЕОРЕТИКО-ГРАФОВЫЕ ПОДХОДЫ В МОДЕЛИРОВАНИИ СЛОЖНЫХ СИСТЕМ

Специальность 05.13.18 -Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Москва - 2005

Работа выполнена в Институте прикладной математики им. М.В. Келдыша Российской академии наук

Научный руководитель: доктор физ -мат. наук, профессор

Малинецкий Георгий Геннадьевич

Официальные оппоненты: доктор физ.-мат. наук, профессор

Дмитриев Александр Сергеевич

доктор технических наук, профессор Кульба Владимир Васильевич

Ведущая организация: Ярославский государственный

университет им. П Г. Демидова

Защита диссертации состоится « 2.0 » ^-Q-uQ-Sp-V,_2005 г

в П-ОО час. на заседании диссертационного совета Д002.024 02 при Институте прикладной математики им М В. Келдыша РАН по адресу: Москва, Миусская пл., д. 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН

Автореферат разослан « ^ » У-Д-^^Ву_2005 г.

Ученый секретарь диссертационного совета

кф.-м.н. — Г.В. Устюгова

2 ррм шть гь5ъ<\

I. Общая характеристика работы

Актуальность темы. На протяжении последних пятнадцати лет в Институте прикладной им. М В Келдыша РАН по инициативе МЧС России совместно с другими академическими институтами1 проводились исследования2'3'4, которые легли в основу концепции управления рисками5 Особое внимание в новой концепции уделяется подходам и методам, распространенным в нелинейной динамике5'6.

Одно из центральных мест в исследованиях по управлению рисками занимает анализ кризисов, то есть ситуаций, когда система оказывается не в состоянии в полном объеме выполнять возложенные на нее функции. Системы (технические, социально-экономические и т п.), рассматриваемые в теории управления риском, могут быть подвержены внешнему влиянию (воздействию) на протяжении небольшого промежутка времени. Нередко такие воздействия являются внезапными и интенсивными, а поэтому рассматриваемые системы не всегда могут "противостоять" этим поражающим факторам Поражающие воздействия, приложенные к системе, могут приводить к ухудшению ее функционирования, а порой и к кризисам.

Классическая теория надежности7 не предоставляет необходимых инструментов для исследования (оценки состояния системы в целом, прогнозирования поведения системы под влиянием поражающих факторов, методов повышения или сохранения сопротивляемости систем, функционирующих в условиях поражающих воздействий, и т.д) качества функционирования сложных систем в "зоне форс-мажорных обстоятельств". Пребывание систем именно в этой зоне приводит к необходимости разработки соответствующих математических моделей.

Следует также отметить, что исследование систем со сложной структурой в классической теории надежности сводится во многом к изучению систем со структурами в виде последовательно-параллельных схем8'9, что

1 Институт проблем управления им В А Трапезникова РАН, Институт машиноведения им А А Благонр<шова РАН, Международный институт теории прогноза землетрясений и математической геофизики РАН, Комиссия по устойчивому развитию Государственной Думы РФ и др

2 Малинецкий Г Г, Залиханов М Ч, Воробьев ЮЛ и др Кризисы современной России и система научного мониторинга // Проблемы безопасности при чрезвычайных ситуациях №1,2002

3 Малинецкий Г Г, Воробьев Ю Л, Махутов НА Кризисы современной России и научный мониторинг// Вестник РАН, 2003, т 73, №7, С 579-593

4 Архипова НИ, Кульба В В Управление в чрезвычайных ситуациях - М РГТУ, 1998

5 Владимиров В А , Кульба В В, Малинецкий Г Г и др Управление риском - М Наука, 2000

6 Малинецкий Г Г, КурдючовСП Нелинейная динамика и проблемы прогноза// Вестник РАН, 2001, т71,№3 С 210-224

7 БарлоуР, Прошан Ф Статистическая теория надежности и испытание на безотказность - М Наука, 1984

8 РайншкеК, Ушаков НА Оценка надежности систем с использованием графов - М Радио и связь, 1988

9 Райншке К Модели надежности и чувствительности систем - А Уу^ЦиОНАЛЬЬЛ ч

БИБЛИОТЕКА {

также сказывается отрицательным образом на качестве проводимого исследования.

Живучесть системы, ее способность функционировать в условиях внешних поражающих воздействий будем называть стойкостью системы С введением этого понятия очерчивается новая задача в рамках теории управления рисками - обеспечение стойкости сложных систем.

Важнейшую роль в формальном представлении сложных систем играет ее структура - порядок межэлементных связей системы Это наглядно подтверждает цикл работ научной школы профессора В.В. Кульбы10 , посвященный управлению риском В работах этой научной школы для моделирования поведения систем со сложной структурой используются методы теории взвешенных ориентированных графов11. Такой подход уже позволил обнаружить ряд синергетических эффектов в поведении систем со сложной структурой. Несомненно, от структуры системы зависит ее стойкость. Важно знать, также какие изменения в структуре системы приведут к улучшению или ухудшению функционирования рассматриваемого объекта.

Пели работы.

1 Построение модели влияния поражающих факторов на систему и распространения по ее структуре внешних воздействий.

2 Разработка методов изменения структур систем для наделения их требуемыми свойствами и характеристиками для повышения их стойкости.

3. Исследование динамики и стойкости систем с регулярно изменяющимися структурами.

4. Разработка параллельных алгоритмов анализа сложных объектов, имеющих масштабно-инвариантную структуру.

Методы исследования. Все исследования, проведенные в настоящей работе, используют методы и подходы дискретной математики и теории графов, в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач, связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем.

Кроме того, в работе используются методы когнитивного моделирования, связанные с анализом динамики нелинейных процессов, развивающихся на ориентированных графах Используются методы нелинейной динамики, теории вероятности, имитационного моделирования и теории фракталов.

Научная новизна. В диссертации формализовано понятие стойкости для сложных систем, попадающих в условия внезапных кратковременных

10 КульбаВВ, Кононов ДА, Косяченко С А , Шубин АН Методы формирования сценариев ражития социально-экономических систем - М СИНТЕГ, 2004

" Роберте Ф С Дискретные математические модели с приложениями к социальный, биологическим и экологическим задачам - М Наука, 1986

воздействий Построена математическая модель распространения поражающего воздействия по системе На ее основе выработаны рекомендации по повышению стойкости и обеспечению функционирования систем в условиях форс-мажорных обстоятельств.

Введены такие ключевые понятия как структурная уязвимость элемента системы и предельная надежность элемента системы. Они являются, соответственно, качественным и количественным параметрами оценки стойкости всей исследуемой системы Исследовано влияние контуров положительной обратной связи в структуре системы на ее функционирование

Для развивающихся систем с изменяющейся структурой сформулировано понятие структурной динамики Продемонстрирована возможность появления в таких системах структурного хаоса.

Для класса фрактальных графов предложены эффективные параллельные алгоритмы, позволяющие решать ряд классических задач теории графов существенно быстрее известных алгоритмов.

Практическая ценность. Полученные результаты используются в Институте прикладной математики им М В Келдыша РАН, 4-ом Центральном научно-исследовательском институте Министерства обороны РФ, Московском физико-техническом институте, Российской академии государственной службы при Президенте РФ, в Институте проблем управления им. В.А Трапезникова РАН, в Институте машиноведения им А.А Благонравова РАН, в Институте социально-политических исследований РАН.

Полученные результаты демонстрируют возможность широкого использования методов теории графов в выявлении синергетических эффектов, что представляется важным в прикладном аспекте как для специалистов по управлению риском и инженеров, так и для ученых, занимающихся исследованием синергетических явлений и теорией графов

Полученные результаты были использованы для анализа стойкости ряда систем управления техническими объектами и одной социально-экономической системы.

Апробация работы. Основные результаты работы докладывались на 4-ом и 5-ом Всероссийских симпозиумах "Математическое моделирование и компьютерные технологии" (Кисловодск, 2000 и 2002), 2-й Международной конференции "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 2001), 10-ой, 11-ой и 12-ой Международных конференциях "Проблемы управления безопасностью сложных систем" (Москва, 2002, 2003 и 2004), Международной конференции "Математическое моделирование социальной и экономической динамики" (Москва, 2004), 47-ой научной конференции Московского физико-технического института "Современные проблемы фундаментальных и прикладных наук" (Москва, 2004), 8-ой региональ-

ной научно-технической конференции "Вузовская наука - Северокавказскому региону" (Ставрополь, 2004), 12-ой Международной конференции "Математика Компьютер Образование" (Пущино, 2005), 1-ом Международном междисциплинарном семинаре памяти чл.-корр РАН С П Курдюмова "Идеи синергетики в естественных науках" (Тверь, 2005), 1-ой Международной конференции "Системный анализ и информационные технологии" (Переяславль-Залесский, 2005), на семинарах Института прикладной математики им М В Келдыша РАН

Публикации. По результатам выполненной работы имеется 21 публикация (см список публикаций)

Структура диссертации Диссертация состоит из введения и трех глав, изложенных на 118 страницах, содержит 23 рисунка и библиографию из 102 наименований.

II. Содержание работы

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

Существуют общеизвестные методы повышения надежности функционирования систем Одним из распространенных является - резервирование12 (и его виды - мажоритирование, дублирование и т п) В условиях ограниченности финансового (ресурсного) обеспечения не представляется возможным продублировать все элементы системы, предполагающей попадание под внешнее влияние. Поэтому требуется изучить реакцию системы на "стороннее" влияние, найти ее наиболее уязвимые "места" и рекомендовать их к резервированию. Для достижения этой цели важно подобрать метод формального представления системы, внешнего воздействия и определить динамику распространения внешнего влияния по системе

Под системой обычно понимается объединение любых элементов, рассматриваемых как связное целое Каждый элемент системы производит определенные действия, что позволяет всей системе выполнять возложен-

12 Острейковскив В А Теория надежности - М Высшая школа, 2003

ные на нее функции Особое значение для системы имеет порядок связей ее элементов, т.е. порядок взаимодействия элементов системы при ее функционировании. Факт непосредственного (без посредников) взаимодействия между двумя элементами системы и определяет наличие связи между ними. Общую картину связей между всеми элементами системы отражает структура системы Опыт исследования многих сложных систем показывает, что на начальном этапе анализа их элементы целесообразно представлять в виде вершин графа, наделенных определенными свойствами, а взаимодействие описывать с помощью ребер Иначе говоря, структура -это организация целого из составных частей, тесно взаимодействующих друг с другом яри функционировании системы4. Будем считать тождественными следующие понятия- граф системы и структура системы, вершина графа и э чемент системы, ребро графа и связь между элементами системы Отметим, что ребра графа могут отражать различные типы связей между элементами рассматриваемой системы - механические, электронные, информационные и т д

Для всякого конечного графа будем использовать обозначение -G = (V,E), где V = {vt},i,j =\,п - множество вершин, а И = {е - (v„v )|/ ф j] - множество его ребер13

Распространение воздействия от одного элемента системы к другому на графе системы будем задавать ориентированным ребром - ребром с заданными началом и концом. Ориентированное ребро часто называют дугой, а граф с дугами - орграфом13. Орграф структуры моделируемой системы не будет иметь петель (т.е. дуг, конец и начало которых совпадает). На орграфе G = (V,E) системы для вершины v( е V, i € {1,2,. ,п} весом 0 < w,(t) <1 является величина показателя качественного состояния элемента системы, соответствующего вершине v,. А весом . Vj ) = sy,je {1,2, ,«}, дуги (vt,Vj)eE является число О <е < 1, равное сохранившейся доле передаваемого воздействия, при переходе от вершины v, к вершине v} и называемое коэффициентом сопротивляемости.

Процесс изменения весов вершин графа системы можно отразить следующим правилом, называемым импульсным воздействием. Оно во многом напоминает импульсный процесс11 и заключается в следующем. Импульсное воздействие определяется импульсом imp (l), j е {l,2, ,«} в

дискретном времени t = 0,1,2,3 .. , который задается отношением

11ДистелъР Теория графов - Новосибирск Им-во Института математики, 2002

lmpJ(t) = wJ(t)/wJ(t-l),пpw 1>0 (1)

Тогда для г > О для г -ой вершины графа С определим импульсное воздействие

7=1

или

degv(

м>, (( + !) = к, (О ПО- елтР] (0). (3)

7=1

полагая при этом, что с!е§ V, - число входящих в вершину V, дуг.

Формулы (1), (2) и (3) задают изменения весов вершин графа С = (У,Е), тем самым определяя динамику распространения внешних воздействий по системе. Формула (2) соответствует возрастающим импульсным воздействиям, которые увеличиваются при переходе от одной вершины к другой. А формула (3) - затухающим, которые уменьшаются при переходе от одной вершины к другой.

Автономное импучъсное воздействие на взвешенном орграфе С определим по правилу (2) с вектором начальных значений \Л/(0) = (^,1(0),и'2(0),...,и'п(0)) и вектором импульсов

1тр(0) = (тр1(0),1тр2(0),...>1трп(0))> (4)

задающим импульс тр] (0) в каждой вершине в момент времени г = 0.

Автономное импульсное воздействие в паре с вектором начальных значений описывает состояние системы в начальный момент времени, когда под влияние внешних поражающих воздействий попадают все элементы системы.

Автономное импульсное воздействие, в котором вектор 1тр(0) = (1,1,. ,тр,{0), ..,1), тр,(0)>0, имеет только г-ую отличную от единицы компоненту, назовем простым воздействием с начальной вершиной V, е V Простое импульсное воздействие описывает состояние системы в начальный момент времени, когда внешнее воздействие поражает один из элементов системы А именно, тот, который соответствует / -ой вершине графа системы

В соответствии с описанным импульсным воздействием на орграфе можно ввести различные критерии отказа моделируемой системы (технической, социально-экономической, биологической и т п) К примеру, можно считать, что система находится в состоянии отказа, если показатель качественного состояния хотя бы одного из наиболее значимых элементов системы ниже некоторого допустимого уровня Этот уровень будем называть критическим уровнем качественного состояния элемента V, и обозначать сг(у) Если показатель качественного состояния элемента ниже критического уровня, то элемент не в состоянии выполнять возложенных на него функций, или функционировать требуемое время Элемент, находящийся в состоянии отказа, не передает распространяющееся по системе импульсное воздействие.

Представление исследуемой системы в виде взвешенного по правилу графа О = (V, Е) и формализация внешнего влияния на систему как автономного импульсного воздействия (1)-(4) определяет модель распространения поражающих воздействий по системе

Рис. 1. Пример графа системы управления. Пунктирными линиями изображены связи, по которым подается напряжение, а сплошными - информационный сигнал

В диссертации предложен алгоритм, позволяющий выяснить, как внешнее воздействие распространяется по структуре системы и влияет на ее функционирование Приведем конкретный пример использования этого алгоритма.

На рис 1 изображен граф системы управления сложным техническим объектом, подверженный импульсным воздействиям, имеющим два вида связей Граф, изображенный на рис. 1 со всеми показателями качественного состояния элементов и коэффициентов сопротивляемости, получен при экспертной поддержке специалистов соответствующего профиля.

Система может быть подвержена двум типам внешних воздействий Первый - электромагнитные воздействия, которые могут распространяться по обоим видам связей. Второй - информационные воздействия, которые могут распространяться только по связям, изображенными сплошными линиями.

Компьютерный эксперимент, в котором поочередно к каждой вершине прилагались различные затухающие импульсные воздействия (3) в соответствии с предложенным алгоритмом, выявил "окна уязвимости" исследуемой системы.

Например, если импульсное воздействие приложено к элементу 16, то из строя в течение незначительного промежутка времени выходит более 90% элементов системы.

Если импульсное воздействие одновременно приложено сразу к двум элементам - 31 и 32, то из строя выходит более 80% элементов системы, в то время как те же импульсные воздействия, приложенные к этим элементам поочередно не приносят существенного ущерба

Обнаружены группы элементов - 1-5, 34-38 и 48-50, - которые являются внутренними источниками воздействий. Каждая из этих групп составляют в графе системы контуры обратной связи "Зацикливание" импульсного воздействия в контуре графа системы приводит к периодическому изменению весов вершин самого контура и оказывает влияние на веса соседних с вершинами контура вершин графа Внутренние источники импульсных воздействий на графах систем приводят к появлению остаточного эффекта, когда из строя выходят элементы спустя длительное время после попадания системы под влияние внешних воздействий.

Как показывает практика, не всегда удается получить достоверные сведения о показателях качественного состояния элементов и коэффициентах сопротивляемости. В такой ситуации о стойкости системы можно судить и по одному лишь графу системы.

Структурной уязвимостью \/1(м) вершины и е V* назовем число путей, концом которых является вершина и,

Структурная уязвимость элемента дает качественную оценку его расположения в структуре системы Структурная уязвимость позволяет

судить о том, насколько безопасно расположение элемента в структуре системы относительно других элементов в период поражающих воздействий Структурная уязвимость элемента определяет выгодность его расположения в структуре системы при распространении по системе поражающих воздействий

Но структурная уязвимость не дает количественной оценки ухудшения надежности элемента при попадании системы в условия поражающих воздействий Такой оценкой будет служить другой параметр, отчасти являющийся дополнением структурной уязвимости.

Важно знать, как к окончанию времени распространения импульсного воздействия по графу системы изменились показатели качественного состояния элементов системы Предельным показателем вершины и назовем величину показателя качественного состояния соответствующего ей элемента системы на момент окончания времени воздействия, которую обозначим через Ьг(и)

Можно подсчитать сумму длин всех путей, концом которых является вершина и Обозначим эту сумму через рэ(гг) и назовем мерой структурной уязвимости вершины и.

Теорема 1.3. Предельный показатель Ьг (и) вершины и е V* графа в* =(У*,Е*) с равными весами е для всех ребер га Е* при автономном импульсном воздействии с начальным импульсом тр0, одинаковым для всех вершин из V", определяется формулой

Ьг (и) = ки1тр*м+1ер5(и\

где ц>и - показатель качественного состояния вершины и в начальный момент автономного импульсного воздействия.

Существенной особенностью построенной модели является возможность описания выхода из строя элемента с большим показателем качественного состояния Этот факг красноречиво подчеркивает прямую зависимость динамики показателей качественного состояния элемента системы от его положения в структуре, а так нее зависимость стойкости всей системы от этой структуры.

Исследование модели распространения поражающих воздействий по системе позволило выработать ряд рекомендаций по сохранению и улучшению функционирования системы и наделению системы заданной стойкостью при ее проектировании Рекомендации сформулированы в диссертационной работе в виде теорем.

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

Черногории.14

На рис. 2 представлена структура социально-экономической системы (см. рис 2а), типичная для многих небольших регионов (республик, областей) Российской Федерации. Система состоит из пяти основных элементов. СГ1 - социальное положение элита региона, УЭ -управленческая элита региона, ВА - внешний арбитр, ЭА - экономическая активность региона

Целесообразно также использовать в исследуемой модели управляющие воздействия, позволяющие повышать значения качественных показателей состояния элементов системы в' любой момент времени, вмешиваясь тем самым в процесс распространения дестабилизирующих импульсных воздействий по системе А также внутренний ресурс системы - периодическое восстановление значений качественных показателей состояния элементов системы на определенную величину

Исследование модели разумно проводить при различных исходных данных (показателях качественного состояния элементов системы и коэффициентах сопротивляемости ребер) о состоянии системы и импульсных воздействиях, приложенных к различным вершинам. Это позволит сделать наиболее достоверные выводы о стойкости системы

Своего критического уровня сг(СП) = 0,01 система со структурой на рис. 2а достигает за характеристическое время г=33 (см. рис. 26). Если в структуру системы добавить обратные связи (к примеру УЭ—ЮЭ или СП—>ВА), то на первый взгляд система должна стать более стойкой к внешним воздействиям Но при указанных структурных изменениях системы характеристическое время уменьшиться почти вдвое.

На рис. 3(сг) представлен график изменения основного показателя системы - СП исследуемой региональной социально-экономической системы с внутренним ресурсом и внешним затухающем воздействие, приложенным к вершине (элементу) ВА Наблюдается падение основного показателя.

Кульба В В, Кононов ДА , Чернов И В, Янич С С Сценарии управления государством (на примере Союза Сербии и Черногории) // Проблемы управления 2005 № 5 - С Ч1-42

(а) (б)

Рис. 2. Структура региональной социально-экономической системы

(напряженность) в регионе, ОЭ - оппозиционная

1,

« 1 ; 1 »

а | 1 <

{ 1 « 1

1 : ,1 # ; 1 1 1 к

* «• »

|"РР1Ч! Мвц >

; 4 кмиш

На рис. 3(6) представлен график изменения основного показателя системы СцПл, когда то же самое по величине внешнее затухающее воздействие, что и в предыдущем случае, о,з | : при тех же исходных данных системы

приложено к другому элементу системы 0,7 « ; 1 ¡"1 ; - к вершине (элементу) ОЭ. В такой си-

00- ! туации, в отличие от предыдущей, сис-

0,5 ; ; ; ; | ; ' | теме удается восстановиться, благодаря

внутреннему ресурсу, и зафиксировать значение основного показателя на некотором стабильном уровне, хотя и ниже исходного

На рис 3(в) показан график изменения основного показателя системы СП, когда импульсное воздействие, в два раза меньшее, чем ранее, приложено сразу к двум элементам системы -ОЭ и ВА Наблюдается падение значение СП

Управляющие воздействия являются основным инструментом повышения значений показателей качественного состояния элементов системы. Но величина управляющего воздействия, время и точка его приложения должны быть определены в зависимости от распространяемого по системе импульсного воздействия.

Использование этой модели позволяет увидеть парадоксальные, не очевидные на первый взгляд, способы управления социально-экономической системой.

На рис. 4(а) изображен график изменения основного показателя исследуемой региональной социально-экономической системы с внутренним рис ^ ресурсом, когда затухающее импульс-

ное воздействие приложено к элементу ВА. Наблюдается падение основного показателя.

Управляющее воздействие приложенное к системе в момент времени /=75 (см. рис. 4(6)), повысит значение показателей качественного состояния ее элементов, но не повлияет на общее состояние системы в дальней-

1

0.9 2 0,8

1 0,7

I 0,6

8 0,5 1 0,4

* 0.3

* 0,2 0,1

о

1 11 1 л

1

1

1 ь 1

! | ! !

1 1

1

о

101

201 301 I, время

401 501

1

0,9 3 0,8

I 0,7

I 0,6

8 0,5 § 0,4

0,3 ¥ 0,2 0,1 о

1 II 1 ■1

ь

1 1 1

4 1 1 т 1 - : 1

_

I

1

1 т . 1

о 101 201 301 401 501 время

1

0,9 | 0,8

I 07

о. 0,6 ф

» 0,5

и я л

Й °.4 о

0,3 | 0,2 0,1 о

Г"

1 1

в

1 =

1 1+ к

101

201 301 I, время

401 501

Рис. 4

шем.

Управляющее воздействие приложенное к системе в более поздний момент распространения по ней импульсных воздействий, приводит к иному результату. Основной показатель системы не понижается, а стабилизируется, хотя и на уровне более низком, чем первоначальный. Это объясняется тем, что в предыдущем случае управляющее воздействие было приложено к системе, когда по ней распространялось импульсное воздействие, величина которого позволяла "поглотить" повышение значение показателей качественного состояния элементов системы.

Для обеспечения стойкости системы как новой задачи в рамках концепции управления рисками5 возможны два подхода.

Первый - наделение системы достаточным внутренним ресурсом, позволяющим противостоять любым внешним дестабилизирующим воздействиям.

Второй - изменение структуры системы, позволяющее повышать стойкость системы, "убирая" из структуры системы наиболее опасные и уязвимые взаимосвязи. Второй подход очерчивает новое направление теории управле-

ния сложными системами - структурное управление. Модели рассмотренного типа, как показывает их анализ и опыт применения, могут быть элементом систем поддержки принятия решений в соответствующих ситуаци-

онных центрах.

Во второй главе даются оценки различных "мерам стойкости"15 и исследуется явление структурного хаоса.

В 1967 г. социолог из Гарвардского университета С. Милграм16 сделал утверждение о том, что каждого человека можно связать с любым другим человеком на земном шаре из цепочки из шести знакомых. Этот феномен получил название "тесного (маленького) мира" ("small world"). В 90-х годах прошлого века эмпирически было доказано, что подобным свойством обладают структуры многих социальных технических систем Например' электроэнергетические сети, WWW (Internet), нейронные сети, метаболические сети клеток, сети научного сотрудничества и т.д.

Структура таких систем по истечении времени претерпевает определенные изменения, вызываемые различными внешними обстоятельствами Изменения в структуре систем могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными Для второго случая разумно ввести понятие структурной динамики - изменение структуры системы с течением времени Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов

Одним из наиболее распространенных типов структурной динамики

является рост структуры17 Рост структуры - это регулярное появление новых элементов и связей в структуре системы Рост структуры происходит по правилам, определяющим предпочтительность присоединения новых элементов со старыми. Не исключается наличия в них фактора случайности

Структуры систем, обладающих свойством "тесного мира", - динамически растущие структуры Феномен "тесного" мира в терминах теории графов можно интерпретировать как графы с быстро растущим числом

15 Ма/шшенко Ю [■'. Нгхшк/иш Н М Модели неопределенности в многопольтовательских сетях М Эди-ториал УРСС, 1999

"'Stanlv Killgram The «¡mall uorld problcm // Psvchology Today 1967 №2 Pp 60-67

" Евин И А Самоорганил ющиеся сети //Синергетика Труды семинара Том 6 Естественные, социальные и г\ манитарные науки - М МИФИ, 2003

Рис. 5. Типичная зависимость для "тесного мира" N(1) - число вершин, с!(1) - диаметр

вершин при незначительно изменяющемся диаметре (см. рис. 5).

В настоящей работе для описания сложных структур, обладающих свойством "тесного мира", предлагаются так называемые фрактальные графы.

Фрактальные графы являются моделью структур, растущих в дискретном времени по одним и тем же правилам из каждой своей вершины. Формальным отражением этих правил является операция замены вершины затравкой, которая и лежит в основе определения фрактальных графоЕГермином затравка условимся называть какой-либо связный граф Е1 = (Ж, О). Суть операции

„ , , . замены вершины затравкой

"ис, о. Траектория предфрактального графа

^ /тг г-ч (тл 7 (ЗВЗ) заключается в сле-

01=(УЪЕ3) Жирными линиями нарисованы ребра '

первого ранга Линиями средней жирности нари- Дующем. В данном графе сованы ребра второго ранга Тонкими линиями на- О = (V, Е) у намеченной для рисованы новые ребра-ребра третьего ранга замещения вершины V еУ

выделяется множество

Г = ] = 1,2,. „\у\ смежных ей вершин Далее из графа С удаляет-

ся вершина V и все инцидентные ей ребра. Затем каждая вершина е V, ] =1,2, соединяется ребром с одной из вершин затравки Н =(№,0

Вершины соединяются произвольно (случайным образом) или по определенному правилу при необходимости

Предфрактапьный граф - конечный аналог фрактального графа -будем обозначать через = (Уь, ), где Уь - множество вершин графа, а Е] - множество его ребер. Определим его рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1,2,..,/,-1 графе (¡1 = (V/, Е1) каждую его вершину затравкой Н = (IV,О). На этапе /= 1

предфрактальному графу соответствует затравка (7, = Н. Об описанном процессе говорят, что предфрактальный граф (тг =(У1,Е1) порожден затравкой Н = (И7,(7) Процесс порождения предфрактапьного графа С1 по существу есть процесс построения последовательности предфракталь-ных графов СЬС2, ,(г/,.,, называемой траекторией (см. рис 6) Фрактальный граф С = (У,Е), порожденный затравкой И = (IV,О), определяется бесконечной траекторией Предфрактальный граф Оь = (V;, Е;) условимся называть («,</, А) - графом, если он порожден л-вершинной ц-реберной связной затравкой Н = (IV, 0.

Для предфрактапьного графа (т£ ребра, появившиеся на / -ом, / е {1,2,. ,1}, этапе порождения, будем называть ребрами ранга I Новыми ребрами предфрактапьного графа (7, назовем ребра ранга Ь, а все остальные ребра назовем старыми

Правила порождения предфрактапьного графа позволяют прогнозировать и оценивать его качественные и количественные характеристики Это позволило заложить основы нового метода проектирования и анализа сложных многоэлементных структур Метод базируется на свойстве самоподобия18 фрактальных графов Использование свойства самоподобия дает возможность "программирования" предфрактапьного графа, наделения его требуемыми характеристиками и свойствами При этом особенно важным представляется рассмотрение и числа "окон уязвимости" - точек сочленения и мостов Доказанные в диссертации теоремы позволяют оценить это число

Теорема 2.1. Для всякого предфрактапьного (п, -графа Сть = (VI, Еь), порожденного затравкой Н = (IV, О), справедливы следующие верхняя и нижняя оценки числа точек сочлененияп

п Г'~[т(Н) < т(С}ь )<п г'~1т(Н) + 2д-, если затравка Н - дерево

п-1

Теорема 2.2. Для всякого предфрактапьного (п^,Ь)-графа О, = (VI ,ЕГ), порожденного затравкой Н = (IV, О) без точек сочленения,

справедливы верхняя и нижняя оценки дчя числа точек сочченения ^^ _^

пь~1 < т(0,) <-, если смежность старых ребер одного ранга не на-

п-1

рушается.

Теорема 2.3. Для всякого предфрактального (п,д,Ь)-графа Оь, порожденного затравкой Н = (И7,0), справедливы верхняя и нижняя оценки

18Мандечьброт Б Фрактальная геометрия природы - М ИКИ, 2002

числа точек сочленения т(Н)п1'1 <т(С,)<т(Н)п1 1 +--если

п-1

смежность старых ребер одного ранга не нарушается.

Теорема 2.4. Для всякого предфрактального («,</, I.)-графа С/ =(У; ,Е[ ) порожденного затравкой Н = (IV,О), справедливы верхняя и

нижняя оценки числа мостовп: к(Н) < к(С{ )<к(Н) —-—

п-1

Теорема 2.5. Родп у(01) предфрактального графа -(УЬ,ЕЬ), порожденного затравкой Н = (IV, О) с сохранением смежности старых

п1 -1

ребер, определяется равенством у(Оь) = у(Н)-.

п-1

Фрактальные (предфрактальные) графы - структуры, динамически растущие во времени, причем с фактором случайности в правилах, определяющих их рост Поэтому представляется важным знать число всевозможных предфрактальных графов к определенному моменту времени (этапу порождения).

Теорема 2.6. Число всех предфрактальных графов Ь -го ранга, по-

2<?"/-+Д1~"н

рожденных затравкой Н = (IV, О), = |<у| = ц, равно п (п_1)

Динамические системы, имеющие конечный горизонт прогноза, принято называть системами с хаотическим поведением19 Траектории системы с хаотическим поведением с близкими начальными данными "разбегаются" экспоненциально, а поэтому для таких систем долгосрочный прогноз невозможен.

Для анализа работоспособности системы с динамически меняющейся структурой необходимо прогнозирование поведение структуры этой системы. Для этого иногда достаточно просмотреть все возможные варианты изменений в сгруктуре, и сравнить их количественные оценки. В нашем случае - фрактальные графы, динамически растущие структуры, причем рост структуры, те. увеличение числа вершин предфрактального графа, происходит очень быстро. Число всевозможных предфрактальных графов одного ранга, порожденного одной и той же затравкой, как свидетельствует теорема 2 6, зависит экспоненциально от числа вершин самого предфрактального графа. Структурную динамику такого рода, по аналогии с системами с хаотическим поведением, назовем структурным хаосом На первый взгляд, такое свойство может привести к мысли о невозможности получения хоть сколько-нибудь полезных, т.е. полиномиальных, количественных оценок для характеристик предфрактального графа О том, что это

19 Малипецкий I I . Потапов А Б Современные проблемы нелинейной динамики - М Эдиториал УРСС, 2000

не так, говорят результаты, представленные в настоящей главе (см. теоремы 2 1-25) И действительно, количественные оценки, полученные в работе, ограничены сверху полиномами О(Ы) от числа N - вершин пред-фрактального графа, в то время как число всех предфрактальных графов с N - вершинами ограничено сверху экспонентой 0(/?л+| ), где п - число вершин затравки (см. теорему 2.6).

Основная цель настоящей главы - продемонстрировать возможность получения "хороших" диапазонов количественных оценок, связанных со стойкостью, для несравнимо большого числа предфрактальных графов

Подводя итог, можно сказать, что использование архитектур компьютерных сетей или систем сетевой связи реализующих предфрактальные графы, дает ряд важных преимуществ, с точки зрения обеспечения стойкости таких объектов.

Третья глава посвящена проблеме разработки параллельных20 алгоритмов решения теоретико-графовых задач.

Анализ сложных структур большой размерности является одной из актуальных задач науки2 . Сложные структуры, обладающие свойством самоподобия, формализуются, как отмечалось ранее во второй главе, в виде фрактальных (предфрактальных) графов.

В диссертации предложены три параллельных алгоритма Рх, /?2 и /?3 решения классических задач теории графов на заданном предфракталь-ном (п, ц, I.)-графе Оь =(У1,Е1) Алгоритм Д - поиск кратчайшего пути между двумя произвольными вершинами предфрактального графа Оь, алгоритм /?2 - поиск остовного дерева минимального веса (ОДМВ) предфрактального графа (тг, и алгоритм /?3 - поиска совершенного паросо-четания предфрактального графа О ¡.

При удалении из предфрактального графа Ог всех ребер рангов / = 1,2,..., Ь - г получим множество {В^]}, ге{1,2, ..,¿-1}, блоком г-го ранга, где / = 1,2, ,п1~г - порядковый номер блока Термином подграф-затравка будем называть блок В^, .5 = 1 ,п'~1 первого ранга предфрактального графа С/, I = 1,1 из траектории Мощность множества = {г'''}, / = 1,/>, д=1 ,им всех подграф-затравок из траектории

графа (7/ равна |2((3£)| = ---.

20 Воеводин В В, Воеводин Вл В Параллельные вычисления - СПб БХВ-Петербург, 2002

21 Parallel Computing 2000 № 26

АЛГОРИТМ Рх Дан предфрактальный (п, д,Ь) -граф (}1, смежность старых ребер которого на всей его траектории не нарушается, и два процессора р| и р2. Необходимо найти кратчайший путь между двумя вершинами V е Уь и и е Уь. Сначала алгоритм производит поиск общего блока В минимального ранга для вершин V и и, в пределах которого в дальнейшем и будет осуществляться поиск кратчайшего пути между этими заданными вершинами Процессоры р1 и р2 назначаются ("привязываются") вершинам V и и, соответственно Каждая подграф-затравка блока В рассматривается как отдельный граф и процессоры параллельно, независимо • друг от друга, находят кратчайшие пути, переходя от одной затравки к другой Основная цель процессора р], назначенного вершине V, - найти кратчайший путь от вершины V до подграф-затравки 2 наименьшего ранга, принадлежащей блоку В. Основная цель процессора р2, назначенного вершине и, - аналогичная' найти кратчайший путь от вершины и до подграф-затравки г наименьшего ранга, принадлежащей блоку В Опишем детальнее поиск процессорами кратчайшего пути от назначенных им вершин до подграф-затравки г наименьшего ранга. Вершины предфракталь-ного графа могут одновременно принадлежать подграф-затравкам разных рангов. Пусть вершина V принадлежит подграф-затравке наименьшего ранга, тогда обозначим ее через V,, а подграф-затравку, которой она принадлежит - через г„ . Если подграф-затравка и есть искомая подграф-затравка 2, тогда работа процессора рх останавливается, и вершина V,

обозначается через V* В противном случае просматриваются все вершины подграф-затравки . Вершину, принадлежащую подграф-затравке наименьшего ранга, обозначим через у2 , а саму подграф-затравку - через 2Ч Далее осуществляется поиск кратчайшего пути между вершинами V, и у2 Если подграф-затравка и есть подграф-затравка г, тогда работа процессора останавливается, и вершина \'2 обозначается через V*. В противном случае процессор р^ продолжает свою работу до тех пор, пока не будет найден кратчайший путь до вершины V* подграф-затравки г. Работа л процессора р2 будет аналогичной и завершится, когда будет найден кратчайший путь до вершины и* подграф-затравки г. На последнем шаге алгоритм находит кратчайший путь между вершинами V* и и* В итоге искомый кратчайший путь (у,и) будет состоять из трех отрезков (у,у*), (и,и') и (V*,«*).

Поиск кратчайшего пути на подграф-затравках ведется с помощью алгоритма Дейкстрьт13, который заложен в алгоритм рх в виде вызываемой процедуры.

Теорема 3.2. Вычислительная сложность20 алгоритма р1 для предфрактального (и, <7,/-) -графа С1 = (У1 ,Е1), \УЬ ! = N равна О(М), если смежность старых ребер не нарушается.

Примечание 3.1. Вычислительная сложность параллельного алгоритма Р\ для предфрактального (п,д,Ь)-графа Оь, смежность старых ребер которого не нарушается, меньше вычислительной сложности алгоритма Дейкстры 0(А') < О(Л'2) в N раз.

Замети, что при вызовах абонента телефонной сети или обращении к удаленным интернет ресурсам решается сходная задача, поэтому ускорение связанное с распараллеливанием может быть существенно

Будем говорить, что предфрактальньш граф 6'£ = (У^ > ¡'ч.) - взвешен, если каждому его ребру е(/) е Е, приписано действительное число

м'{е0))&(в'-ха,в'-хЬ),тт1 = \Х -рангребра, а>0,и в

Ь

Алгоритм р2 осуществляет поиск ОДМВ Т = (Уь, Ет) на взвешенном предфрактальном графе G¿ = (У£, Еь) Алгоритм использует к процессоров Р\,Рг,.. Назначим каждый процессор одной из подграф-

затравок , / = 1,1, л = 1,им предфрактального графа G¿, тогда число

используемых процессоров равно к = ---. Суть работы алгоритма за-

п-1

ключается в следующем Каждая подграф-затравка г*'' рассматривается как отдельно взятый граф При этом каждый из к процессоров р,, 1 = 1,к параллельно независимо друг от друга находит ОДМВ 1] на своей подграф-затравке Поиск ОДМВ отдельно взятой подграф-затравки осуществляется алгоритмом Прима24. Алгоритм Прима используется в алгоритме рг в виде процедуры по мере необходимости Нахождение ОДМВ

7',,72, ,Тк всех подграф-затравок 2^ определяет ОДМВ Т = (У1,Е1) предфрактального графа С1 Каждое ребро предфрактального графа имеет свой "уникальный" номер, однозначно определяющий ребро во всей траектории Таким образом, выделение ОДМВ на подграф-затравке г\1>> соответствует выделению множества ребер на предфрактальном графе .

Теорема 3.4. Вычислительная сложность алгоритма рг для предфрактального {п,д,Ь)-графа 01 = ,^). \У/,\ = N равна 0{И-пг).

Примечание 3.2. Вычислительная сложность алгоритма Прима равна 0(N2). Сравнив ее с вычислительной сложностью алгоритма рг, получаем: 0(N-n2)<0(N2)

Алгоритм /?3 идентично предыдущему алгоритму производит поиск совершенного паросочетания М = (VL, Ем) на взвешенном предфракталь-ном (n,q,L) -графе GL = (VL,EL). Алгоритм использует nL~l процессоров ps, s=\,nl~x, каждый из которых назначен одной из подграф-затравок

zf\ s = l,nL~]. Основная идея алгоритма заключается в том, что каждая подграф-затравка рассматривается как отдельно взятый граф. При этом каждый ps процессор параллельно независимо от других находит совершенные паросочетания Ms на своей подграф-затравке z\L) Поиск совершенного паросочетания подграф-затравки осуществляется с помощью алгоритма Эдмондса13 Алгоритм Эдмондса оформлен в виде процедуры и используется по мере необходимости. В результате нахождения совершенных паросочетаний {MJ всех подграф-затравок z\L) получаем совершенное паросочетание М = (VL,EM) предфрактального графа G,

теорема 3.7. Вычислительная сложность алгоритма /З3 для предфрактального (п,ц,Ь)-графа GL = (V,,Е,), \VL\ = N, равна Q(N-n2).

Примечание 3.3. Вычислительная сложность алгоритма Эдмондса равна O(N^). Сравнив ее с вычислительной сложностью алгоритма /?3, получаем- 0(N -n2)<(){N^).

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

Во-первых Вычислительная сложность всех описанных алгоритмов на порядок ниже, чем у известных аналогичных алгоритмов

Во-вторых. Распараллеливание в исследованных задачах является геометрическим Т.е. входные данные алгоритмов делятся на определенные группы, которые затем обрабатываются на различных процессорах Входными данными в нашем случае является предфрактальный граф, а 4

группами, соответственно, являются все его подграф-затравки.

III. Основные результаты диссертации у

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

2 Рассмотрены задачи проектирования сложных масштабно-инвариантных структур с заданными количественными характеристиками, определяющими живучесть. Обнаружено и изучено явление структурного хаоса.

3 Для класса предфрактальных графов построены параллельные алгоритмы решения

- задачи поиск кратчайшего пути,

- задачи поиск остовного дерева минимального веса,

- задачи поиска совершенного паросочетания. Предложенные алгоритмы существенно эффективней стандартных методов.

по теме диссертации опубликованы следующие работы:

1. КочкаровАЛ., Кочкаров Р А Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе // Журнал вычис. матем и матем. физ 2004. Т. 44,№6.-С 1157-1162

2 Кочкаров A.A., Мапинецкий Г.Г. Управление безопасностью и стойкостью сложных систем в условиях внешних воздействий // Проблемы управления. 2005. № 5. - С. 70-76.

3. Кочкаров A.A., Мапинецкий Г.Г. Стойкость, управление риском и обеспечение безопасности сложных технических систем // Проблемы безопасности и чрезвычайных ситуаций. 2005. № 4 - С. 12-25

4 Кочкаров А А Мапинецкий Г Г Обеспечение стойкости сложных систем. Структурные аспекты // Препринт Института прикладной математики им. М.В. Келдыша РАН №53. М, 2005. 34 с.

5 Кочкаров А А., Кочкаров P.A. Предфрактальные графы в проектировании и анализе сложных структур // Препринт Института прикладной математики им. М В. Келдыша РАН №10. М., 2003. 23 с.

6. Кочкаров A.A., Кочкаров P.A. Параллельные алгоритмы на предфрактальных графах // Препринт Института прикладной математики им М.В. Келдыша РАН №84 М, 2003. 20 с.

7 Кочкаров А А , Кочкаров РАО планарности и других топологических свойствах фрактальных графов // Препринт Института прикладной математики им MB Келдыша РАН №83. М, 2003 20 с

8. КочкаровА.А, Салпагаров С И, Кочкаров Р А. О количественных оценках топологических характеристик предфрактальных графов // Известия ТРТУ. Специальный выпуск. - Таганрог, 2004. - № 8. - С. 298301.

9 Кочкаров Р.А, КочкаровА.А Особенности конструирования параллельных алгоритмов для решения классических задач теории графов (на примере класса фрактальных графов)// Труды IМеждународной конференции "Системный анализ и информационные технологии" Том 2 М.: КомКнига, 2005 - С 170-174.

10 Кочкаров А А, МачинецкийГГ Стойкость и обоснование стойкости сложных технических и социально-технических систем// Труды ХТ

Международной конференции "Проблемы управления безопасностью сложных систем". Часть 1 М • РГТУ, 2003 - С. 50-53

11 Кочкаров А А., Малинецкий Г Г Концепция стойкости для социально-экономических и технических систем // Труды Международной конференции "Математическое моделирование социальной и экономической динамики" М.: РГСУ, 2004. - С. 151-154.

12.Кочкаров А А Стойкость и моделирование систем, находящихся в условиях внешних воздействий// Труды XLVII научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть VII М. МФТИ, 2004. - С. 190-190.

13 Кочкаров A.A., Малинецкий Г.Г. Моделирование стойкости сложных * технических систем // Труды XII Международной конференции "Проблемы управления безопасностью сложных систем" М ■ РГТУ, 2004 -

С. 348-352.

14 Кочкаров А А , Малинецкий Г Г. Стойкость и моделирование стойкости систем в условиях внешних воздействий // XII Международная конференция "Математика. Компьютер. Образование". Тез. докл. М.-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2005. - С 136-136.

15 Кочкаров А А , Кочкаров Р А. Топологические характеристики пред-фрактальных графов и предупреждение кризисов сложных систем // Труды X Международной конференции "Проблемы управления безопасностью сложных систем" Часть 1 М • РГГУ - Издательский дом МПА-Прогресс, 2002 -С 116-119.

16 Кочкаров А А. Особенности моделирования сложных структур Структурный хаос // Материалы I Международного междисциплинарного семинара памяти чл.-корр. РАН С.П. Курдюмова "Идеи синергетики в естественных науках". Тверь: ТвГУ, 2005. - С. 36-37.

17.Кочкаров А А , Кочкаров P.A. Параллельный алгоритм поиска биком-понент предфрактального графа // Материалы VIII региональной научно-технической конференции "Вузовская наука - Северо-кавказскому региону" Том I. Ставрополь СевКавГТУ, 2004 - С 13-13

18 Кочкаров А А Число всевозможных предфрактальных графов // IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл , том 2. Кисловодск: КИЭП, 2000 - С 73-74.

19.Кочкаров А.А , Кочкаров P.A. Исследование связности предфрактальных графов // IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез докл., том 2. Кисловодск: * КИЭП, 2000. - С. 74-75

20. Кочкаров А. А Число точек сочленения предфрактального графа// II Международная конференция "Нелокальные краевые задачи и родст- ¿ венные проблемы математической биологии, информатики и физики"

Тез докл. Нальчик: НИИ ПМА КБНЦ РАН, 2001

21 КочкаровАА, Салпагаров С.И. Число мостов предфрактального графа// V Всероссийский симпозиум "Математическое моделирование и компьютерные технологии" Тез. докл. Кисловодск. КИЭП, 2002 - С. 36-37

Для заметок

Для заметок

*

г

Заказ Ы» 2169 Подписано в печать 18.11.2005 Тираж 100 экз. Усл. п.л 0,88

п'^': ООО "Цифровичок", тел. (095) 797-75-76; (095) 778-22-20 ■ ч У) www.cfr.ru ; e-maii.info@cfr.ru

-22694

РНБ Русский фонд

2006-4 23591

Введение.

Математическое моделирование и иерархия упрощенных моделей.

Мягкое моделирование и нелинейные явления.

Три парадигмы синергетики.

Структура и краткое содержание диссертационной работы.

Глава I. Математическая модель распространения внешних воздействий по системе.

1.1. Надежность, живучесть, стойкость.

1.2. Распространение импульсных воздействий.

1.3. Структурные параметры стойкости системы.

1.4. Контуры обратной связи.

1.5. Алгоритм повышения стойкости системы.

1.6. Исследование стойкости технической системы.

1.7. Моделирование региональной социально-экономической системы в условиях внешних воздействий.

1.8. Экспериментальное программное обеспечение для исследования сложных систем в условиях внешних воздействий.

1.9. Выводы.

Глава И. Синтез и анализ сложных структур большой размерности

2.1. Моделирование "тесных миров".

2.2. Фрактальные и предфрактальные графы.

2.3. О некоторых топологических и метрических характеристиках сложных структур.

2.4. Связность.

2.5. Структурный хаос и число всех пред фрактальных графов одного ранга.

Глава III. Параллельные алгоритмы на предфрактальных графах.

3.1. Параллельные алгоритмы на графах.

3.2. Параллельный алгоритм поиск кратчайшего пути.

3.3. Параллельный алгоритм поиска остовного дерева минимального веса.

3.4. Параллельный алгоритм поиска совершенного паросочетания.

Основные результатам диссертации.

мл тема тическое моделирование и иерархия упрощенных моделей

Моделирование — это один из важнейших методов научного познания, с помощью которого создается модель объекта исследования. Под термином "модель" [1-5] понимают реальный или идеальный объект, изучение которого позволяет получить новые знания о моделируемой системе, возможно, облегчить прогноз поведения или управления последней. Среди всего множества моделей особое место занимают математические модели. Ключом к успешному решению содержательной задачи является, прежде всего, адекватность математического описания изучаемых явлений и процессов, отражение в модели наиболее важных причинно-следственных связей, характерных для моделируемого объекта. Математическое моделирование связанно с введением абстрактных математических характеристик изучаемого процесса и записью строгих соотношений между этими характеристиками, которые являются "оформлением" интуитивных, почерпнутых из опыта, наблюдения, здравого смысла данных [6-12]. Математическая модель поэтому — всегда схема, упрощение, огрубление реальности. Сущность математических методов изучения реальных процессов — выявление однозначно трактуемых соотношений между характеристиками процесса, которые позволяют выводить из них формальные следствия, свойства, предсказывать развитие процесса. Цена, которую за это приходится платить, - огрубление процесса, его схематизация.

На следующем этапе, предсказания, сделанные на основе моделирования сопоставляются с результатами экспериментов или наблюдений. Затем модель вновь и вновь уточняется до тех пор пока точность ее предсказаний не станет удовлетворительной. Но практика показывает, что модели, получаемые на различных этапах уточнения и детализации, имеют свои собственные "диапазоны применимости".

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

В эпоху становления вычислительного эксперимента казалось, что изучение сложной системы аналогично складыванию мозаичной картины. Например, при изучении биосферы, одной группе исследователей можно поручить строить модели атмосферы, другой - океана, третьей - биоценоза тундры. Затем эти куски-блоки складываются и получается, по замыслу, "прекрасная" модель. Провал нескольких крупных проектов такого рода показал, что так поступать нельзя. Обычно получаются результаты, интерпретация которых не ясна, зачастую результаты не удовлетворительны, но в любом случае не удается продвинуться в понимании исследуемых процессов.

Поэтому приходится действовать иначе. Вначале выделяются основные ключевые процессы, играющие главную роль в изучаемом явлении на данных пространственных и временных масштабах. Затем строится еще более простая модель явления с меньшей областью применимости и учитывающая еще меньшее количество факторов. И так происходит до тех пор, пока не возникнет модель, поведение которой уже понятно. Только после того как модель нижнего уровня изучена и понята, удается перейти на следующий, более высокий уровень.

Можно сказать, что основным достижением и основной целью исследований при решении сложных задач является построение иерархии упрощенных моделей. При этом должно быть установлено, какой уровень модели разумно использовать в тех или иных случаях. Пока почти все построенные иерархии относятся к физическим системам. Идет строительство иерархий в ряде областей химии и математической экономики. Эта проблема ставится в биологии.

Замечательной чертой иерархии упрощенных моделей является наличие базовых математических моделей, т.е. таких математических объектов, исследование которых позволяет эффективно строить и изучать большие классы моделей различных явлений. Важно подчеркнуть два принципиальных факта, выяснившихся в последние двадцать лет.

Во-первых, базовых математических моделей немного. Можно строить предельно простые нелинейные математические модели, которые являются глубокими и содержательными.

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

Мягкое моделирование и нелинейные явления

В последнее время все большее внимание уделяется направлению исследований, часто называемому мягким моделированием [13]. В гидродинамике, квантовой механике, теории упругости известны законы, определяющие ход изучаемых процессов. И задача сводится к получению конкретных частных следствий из общих законов. В психологии [14-16], социологии [17, 18], истории [19-21] и многих других областях попытки поиска эффективного математического описания только начаты. Здесь часто важно проверить те или иные гипотезы. Поэтому обычно основное внимание обращается на качественные эффекты. Модели могут выступать как простейшие объекты, демонстрирующие желаемое качественное поведение. С этим, например, связано широкое использование моделей теории катастроф [22], динамических систем на плоскости, одномерных отображений [23] при описании различных явлений в экономике, медицине, при анализе природных и техногенных катастроф.

Кроме того, известные нелинейные модели, появившиеся в одной области, иногда могут использоваться в качестве своеобразных "строительных" блоков при построении математических моделей в других дисциплинах.

Приведем характерный пример. Одним из важнейших экспериментальных достижений в науке XX в. стало открытие Б.П. Белоусовым колебательных химических реакций [24]. Это привело к построению соответствующих математических моделей. Позже было показано, что эти модели при небольшой модификации позволяют описывать эпидемии ряда заболеваний.

Недавно А.Ю. Андреев и М.И. Левандовский предложили использовать близкую систему для описания забастовочного движения в России в начале XX века. Их модель имеет вид:

X = m(N-X)-bXZ,

Y = bXZ-(m + a)Y,

Z = aY-(m + g)Z, W = gZ-mW, где N — общее число рабочих, X— число рабочих еще не воспринявших информацию о забастовке, Y - рабочие, ставшие агитаторами, W - рабочие, отказавшиеся от стачечной борьбы после одной из забастовок.

Оказалось, что эта модель удовлетворительное описание стачечного движения во Владимирской губернии в период с 1895 по 1905 гг. Модель, родившаяся в одной области, оказалась достаточно универсальной. Такая ситуация - не редкость в мягком моделировании.

Три парадигмы синергетики

Необходимость исследовать открытые нелинейные, далекие от равновесия системы во многих областях физики, техники, химии, экономики, экологии привела к развитию междисциплинарных подходов. Один из наиболее успешных междисциплинарных подходов - синергетика [26-31]. В основе современной синергетики лежат три парадигмы — появившиеся друг за другом, парадигма диссипативных структур, парадигма динамического хаоса и парадигма сложности.

Парадигма диссипативных структур

Во многих гидродинамических системах ключевое значение имеет наличие в них диссипативных процессов (вязкости, диффузии, теплопроводности). Они позволяют исследуемым системам "забыть" начальные данные и независимо от их "деталей" сформировать с течением времени одни и те же или похожие пространственно-временные структуры. Иными словами, немного (а иногда и сильно) изменив начальный профиль (начальные данные в соответствующей задаче математической физики), в конце концов мы получаем одно и то же стационарное распределение переменных в пространстве. Чтобы подчеркнуть это обстоятельство, такие структуры, с легкой руки И.Р. Пригожина, стали называть диссипативны-ми структурами [32]. В основе большинства исследований научной школы И.Р. Пригожина лежали системы параболических уравнений типа реакция-диффузия

Щ = A"xx+/(M>V)» v, = D2vxx + g{u,v),

0<*</, u(x,0) = uq{x), v(x,0) = vq(*), их,ух|х=о,/=0.

Если говорить о парадигме диссипативных структур как о подходе к анализу спонтанного возникновения упорядоченности в нелинейных средах, т.е. о самоорганизации, то следует сказать и о научной школе член-корреспондента РАН С.П. Курдюмова. Научная школа С.П. Курдюмова сформировалась в Институте прикладной математики им. М.В. Келдыша РАН, в МГУ им. М.В. Ломоносова, в Московском физико-техническом институте в 80-е годы прошлого столетия. Усилия участников этой научной школы были вложены в построение качественной теории нелинейного уравнения теплопроводности с объемным источником, так называемой модели тепловых структур [4,5,33,34]

Tt — d\v{k{T) grad Т) + Q(T).

Качественная теория, отражающая в основном эффекты, понятые с помощью компьютерного моделирования, потребовала новых математических идей, существенно опирающихся на то, что мы имеем дело с одной переменной Г, а не с их набором. В отличии от стационарных диссипатив-ных структур, которые изучались в брюссельской школе под руководством И.Р. Пригожина, в научной школе С.П. Курдюмова исследовались нестационарные диссипативные структуры, развивающиеся в режиме с обострением. Под режимом с обострением понимают такие законы изменения параметров исследуемой системы, когда одна или несколько описывающих ее величин неограниченно возрастает за ограниченное время. В научной школе С.П. Курдюмова было открыто явление локализации тепла, обнаружены и исследованы так называемые собственные функции нелинейной среды, описывающие, как правило, волны горения, сохраняющие в процессе эволюции свою форму. Они описываются автомодельным решениями исходного нелинейного уравнения теплопроводности, которое имеет вид Т = g{t) f{xl (p{t)), где функция g(t) задает закон роста амплитуды, возникающей диссипативной структуры, <p(t) — закон изменения ее полуширины, а функция / - форму [33].

Парадигма динамического хаоса

В 1963 году - американский метеоролог Эдвард Лоренц предложил простейшую модель, описывающую конвекцию воздуха (она играет важную роль в динамике атмосферы). Целью этой работы был ответ на вопрос: почему стремительное совершенствование компьютеров, математических моделей и вычислительных алгоритмов не привело к созданию методики получения достоверных среднесрочных (на 2-3 недели вперед) прогнозов погоды.

Эта модель описывается внешне очень простыми уравнениями [35] системы Лоренца привел к „ . . „ r г Рис 1. Аттрактор Лоренца принципиальному результату. Такая картина, полученная на компьютере

Им был открыт - динамиче- (Р^чет проводился при г=28, а=10, 6=8/3), убедила Э. Лоренца, что он открыл новое явление -ский хаос, т.е. непериодиче- динамический хаос. Этот клубок траекторий, называемый сейчас аттрактором Лоренца, опи-ское движение в детермини- сывает непериодическое движение с конечным горизонтом прогноза. рованных системах (то есть в таких, где будущее однозначно определяется прошлым), имеющее конечный горизонт прогноза.

Увиденное Лоренцем показано на рис. 1. С точки зрения математики, можно считать, что любая динамическая система, что бы она ни моделировала, описывает движение точки в фазовом пространстве. Важнейшая характеристика этого пространства - его размерность, или, попросту говоря, количество чисел, которые необходимо задать для определения состояния х = -сг(х + у) у = —xz + гх — у, £ = ху — bz где переменная х характеризует поле скоростей, у и z - поле температур жидкости. Здесь г = R/Rc, где R - число Рэлея, а Rc - его критическое значение; а - число Прандтля; b - постоянная, связанная с геометрией задачи.

Компьютерный анализ

-20 системы. С математической и компьютерной точек зрения не так уж и важно, что это за числа - количество рысей и зайцев на определенной территории, переменные, описывающие солнечную активность или кардиограмму, или процент избирателей, поддерживающих определенного кандидата. Если считать, что точка, двигаясь в фазовом пространстве, оставляет за собой след, то динамическому хаосу будет соответствовать клубок траекторий. Например такой, как показан на рис. 1. Здесь размерность фазового пространства всего 3 (это пространство x,y,z). Замечательно, что такие удивительные объекты существуют даже в трехмерном пространстве. Для установившихся колебаний, соответствующих динамическому хаосу, Д. Рюэль и Ф. Такенс в 1971 году предложили название - странный аттрактор.

Пророчество Анри Пуанкаре о том, что в будущем можно будет предсказывать новые физические явления, исходя из общей математической структуры описывающих эти явления уравнений, компьютерные эксперименты превратили в реальность.

Система Лоренца имеет конечный горизонт прогноза. Почему? Можно пояснить это следующим образом. Если мы вновь возьмем две близкие траектории, показанные на 1, то они расходятся. Одна уходит от второй. Скорость расходимости определяется так называемым ляпуновским показателем, и от этой величины зависит интервал времени, на который может быть дан прогноз. Можно сказать, что для каждой системы есть свой горизонт прогноза.

Парадигма сложности

В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и/или нетривиальных связей между ними. А с другой стороны, речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны.

Хотя строгого и общего определения сложности не существует, опыт развития синергетики и изучения конкретных систем, интуитивно определяемых нами как сложные, позволяет высказать некоторые общие соображения о свойствах любой сложной системы на разных уровнях описания.

Системы с простой структурой, к примеру - иерархической, могут демонстрировать очень сложное нетривиальное поведение [37].

Многие системы обладают простой иерархической структурой, фрагмент которой изображен на рис. 2. Например, литосферу Земли можно представить как систему блоков, разделенных разломами. Каждый из этих блоков делится на более мелкие, те, в свою очередь, на еще более мелкие и т.д. Геофизики выделяют более 30 иерархических уровней в земной коре от тектонических плит протяженностью в тысячи километров до зерен горных пород миллиметрового размера. Большие землетрясения обычно сопровождаются многочисленными повторными толчками — афтершока-мщ которые каскадом перераспределяют напряжение вниз по иерархии разломов. А подготовка землетрясения происходит посредством обратного каскада передачи напряжения, восходящего с нижних уровней иерархии к верхним.

Напрашивающимся примером иерархической системы, связанной с деятельностью человека, служит система административного или военного руководства. Успех в решении задач на некотором уровне управления определяется эффективностью функционирования нижележащих уровней.

Иерархической системой является и электорат. Он также делится на несколько групп со своими интересами. Каждая из них складывается из более мелких подгрупп и т.д. - вплоть до отдельного избирателя.

•

1 м М | М М М | j II |

Рис. 2. Фрагмент иерархической системы

Каждый элемент /-го уровня состоит из трех элементов (/-1)-ого уровня. Элементы системы могут быть исправны или дефектны (показаны заливкой). Состояние каждого элемента определяется состоянием образующих его элементов предыдущего уровня, а также его собственной восприимчивостью к дефектам.

Мы можем наблюдать поведение иерархических систем только на верхних уровнях иерархии (землетрясения, исполнение распоряжений, результаты голосования). Однако причины событий лежат на нижних уровнях, и важно представлять, как происходит взаимодействие уровней.

Но, как говорилось ранее, сложное поведение системы может наблюдаться и при простых процессах протекающих в ней. В такой ситуации сложность в системе обосновывается сложностью структуры системы. Именно такой сложности и посвящена настоящая диссертационная работа.

Структура и краткое содержание диссертационной работы

На протяжении последних пятнадцати лет в Институте прикладной им. М.В. Келдыша РАН по инициативе МЧС России совместно с другими академическими институтами проводились исследования, которые легли в основу концепции управления рисками. Особое внимание в новой концепции уделяется подходам и методам, распространенным в нелинейной динамике.

Одно из центральных мест в исследованиях по управлению рисками занимает анализ кризисов, то есть ситуаций, когда система оказывается не в состоянии в полном объеме выполнять возложенные на нее функции.

Системы (технические, социально-экономические и т.п.), рассматриваемые в теории управления риском, могут быть подвержены внешнему влиянию (воздействию) на протяжении небольшого промежутка времени. Нередко такие воздействия являются внезапными и интенсивными, а поэтому рассматриваемые системы не всегда могут "противостоять" этим поражающим факторам. Поражающие воздействия, приложенные к системе, могут приводить к ухудшению ее функционирования, а порой и к кризисам.

Классическая теория надежности не предоставляет необходимых инструментов для исследования (оценки состояния системы в целом, прогнозирования поведения системы под влиянием поражающих факторов, методов повышения или сохранения сопротивляемости систем, функционирующих в условиях поражающих воздействий, и т.д.) качества функционирования сложных систем в "зоне форс-мажорных обстоятельств". Пребывание систем именно в этой зоне приводит к необходимости разработки соответствующих математических моделей.

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

Живучесть системы, ее способность функционировать в условиях внешних поражающих воздействий будем называть стойкостью системы. С введением этого понятия очерчивается новая задача в рамках теории управления рисками — обеспечение стойкости сложных систем.

Важнейшую роль в формальном представлении сложных систем играет ее структура - порядок межэлементных связей системы. Это наглядно подтверждает цикл работ научной школы профессора В.В. Кульбы , посвященный управлению риском. В работах этой научной школы для моделирования поведения систем со сложной структурой используются методы теории взвешенных ориентированных графов. Такой подход уже позволил обнаружить ряд синергетических эффектов в поведении систем со сложной структурой. Несомненно, от структуры системы зависит ее стойкость. Важно знать также, какие изменения в структуре системы приведут к улучшению или ухудшению функционирования рассматриваемого объекта.

Все исследования, проведенные в настоящей работе, используют методы и подходы дискретной математики и теории графов, в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач, связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем.

Кроме того, в работе используются методы когнитивного моделирования, связанные с анализом динамики нелинейных процессов, развивающихся на ориентированных графах. Используются методы нелинейной динамики, теории вероятности, имитационного моделирования и теории фракталов.

Диссертация состоит из введения и трех глав, изложенных на 118 страницах, содержит 23 рисунка и библиографию из 102 наименований.

Основные результаты диссертации

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

2. Решены задачи проектирования сложных масштабно-инвариантных структур с заданными количественными характеристиками, определяющими живучесть. Обнаружено и изучено явление структурного хаоса.

3. Для класса предфрактальных графов построены параллельные алгоритмы решения

- задачи поиск кратчайшего пути,

- задачи поиск остовного дерева минимального веса,

- задачи поиска совершенного паросочетания. Предложенные алгоритмы существенно эффективней стандартных методов.

1. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. - М.: Физматлит, 2001.

2. Моисеев Н.Н. Алгоритмы развития. М.: Наука, 1987.

3. Моисеев Н.Н. Математика ставит эксперимент. М.: Наука, 1979.

4. Компьютеры, модели, вычислительный эксперимент. Введение в информатику с позиций математического моделирования. М.: Наука, 1988.

5. Компьютеры и нелинейные явления. М.: Наука, 1988.

6. Павловский Ю.Н. Декомпозиция моделей управляемых систем. М.: Знание, 1985.

7. Моисеев Н.Н. Математика ставит эксперимент. М.: Наука, 1979.

8. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. М.: Радио и связь, 1981.

9. Еленин Г.Г., Синько М.Г. Математическое моделирование явления на поверхности. М.: Знание, 1988.

10. Иваницкий Г. Р. Ритмы развивающихся сложных систем. М.: Знание,1988.

11. Краснощекое П.С., Петров А.А. Введение в математическое моделирование. М.: Наука, 1984.

12. МориДж. Нелинейные дифференциальные уравнения в биологии: Лекции о моделях. М.: Мир, 1983.

13. Арнольд В.И. "Жесткие" и "мягкие" математические модели. М.: МЦНПО, 2000.

14. Митин Н.А. Математическое моделирование информационных процессов: Автореф. дис. . канд. физ.-матем. наук. М.: ИПМатем. им. М.В. Келдыша РАН, 1999.

15. Анисимова С.А. Рефлексивные модели субъекта, совершающего моральный выбор. Препринт ИПМ им. М.В. Келдыша РАН, № 60. М., 2003.

16. Анисимова С.А. Психотехнологии в культурных организациях и теория рефлексии. Препринт ИПМ им. М.В. Келдыша РАН, № 51. М., 2004.

17. Бурцев М.С. Исследование новых типов самоорганизации и возникновения поведенческих стратегий: Автореф. дис. . канд. физ.-матем. наук. М.: ИПМатем. им. М.В. Келдыша РАН, 2005.

18. Burtsev M.S. Tracking the Trajectories of Evolution // Artificial Life 10(4), 2004. стр. 397-411.

19. Малков А.С. О математическом моделировании. Препринт ИПМ им. М.В. Келдыша РАН, №11. М., 2005.

20. Малков А.С., Коротаев А.В., Халтурина Д. А. Математическая модель роста населения Земли,экономики, технологии и образования. Препринт ИПМ им. М.В. Келдыша РАН, № 13. М., 2005.

21. Малков А.С., Малинецкий Г.Г., Чернавский Д.С. Оматематическом моделировании исторических процессов: аграрные общества// Информационные технологии и вычислительные системы. №2. 2005. С. 51-60.

22. Арнольд В. И. Теория катастроф. М.: Едиториал УРСС, 2004.

23. МарсденДж., Мак-Кракен М. Бифуркация удвоения цикла и ее приложения. М.: Мир, 1980.

24. ГарелД. Гарел О. Колебательные химические реакции. М.: Мир,1986.

25. НеймаркЮ.И., ЛандаП.С. Стохастическое и хаотическое колебания. -М.: Наука, 1987.

26. Хакен Г. Синергетика. М.: Мир, 1980.

27. Хакен Г. Информация и самоорганизация. М.: Мир, 1991.

28. Занг В.-Б. Синергетическая экономика. Время и перемены в нелинейной экономической теории. М.: Мир, 1999.

29. Хакен Г. Тайны природы. Синергетика: учение о взаимодействии. -Москва-Ижевск: Институт компьютерных исследований, 2003.

30. Безручко Б.П., Короновский АА., Трубецков Д.И., Храмов А.Е. Путь в синергетику. Экскурс в десяти лекциях. М.: КомКнига, 2005.

31. Малинецкий Г.Г. Математические основы синергетики. Хаос, структуры, вычислительный эксперимент. М.: КомКнига, 2005.

32. Гленсдорф П., Пригожим И. Термодинамическая теория структуры, устойчивости и флуктуаций. М.: Едиториал УРСС, 2003.

33. Режимы с обострением. Эволюция идеи: Законы коэволюции сложных структур. М.: Наука, 1998.

34. Князева Е.Н., Курдюмов С.П. Основания синергетики. Синергетиче-ское мировидение. М.: КомКнига, 2005.

35. LorenzE.N. Deterministic nonperiodic flow// Journ. of the Atmospheric Science. 1963. V.20 P. 130-141.

36. Пределы предсказуемости. M.: Центрком, 1997.

37. Малинецкий Г.Г., Курдюмов С.П. Нелинейная динамика и проблемы прогноза // Вестник РАН, 2001, т.71, №3. С.210-224.

38. Владимиров ВА., Кулъба В.В., Малинецкий Г.Г, Maxymoe Н.А. и др. Управление риском. -М.: Наука, 2000.

39. Курдюмов С.П., Малинецкий Г.Г. Синергетика и системный синтез // Новое в синергетике: взгляд в третье тысячелетие. М.: Наука, 2002.

40. Новое в синергетике: взгляд в третье тысячелетие / Под ред. Малинец-кого Г.Г, Курдюмова С.П. М.: Наука, 2002.

41. Кулъба В.В., Кононов Д.А., Косяченко С.А., Шубин А.Н. Методы формирования сценариев развития социально-экономических систем. М.: СИНТЕГ, 2004.

42. Ахромеева Т.С., Курдюмов С.П., Малинецкий Г.Г., Самарский А.А. Нестационарные структуры и диффузионный хаос. М.: Наука, 1992.

43. Малинецкий Г.Г. Базовые модели и ключевые идеи синергетики. Препринт ИПМ им. М.В. Келдыша РАН, №70. М., 1994.

44. КастиДж. Большие системы. Связность, сложность и катастрофы. -М.: Мир, 1982.

45. Эйген М. Гиперцикл. М.: Мир, 1984.

46. Острейковский В. А. Теория надежности. М.: Высшая школа, 2003.

47. Райншке К Модели надежности и чувствительности систем. М.: Мир, 1979.

48. Барлоу Р., Пропит Ф. Математическая теория надежности. М.: Советское радио, 1969.

49. Барлоу Р., Прошан Ф. Статистическая теория надежности и испытание на безотказность. -М.: Наука, 1984.

50. Куюнджич С.М. Разработка и анализ моделей надежности и безопасности систем. М.: Физматлит, 2001.

51. Райншке К, Ушаков И.А. Оценка надежности систем с использованием графов. — М.: Радио и связь, 1988.

52. Рябинин И.А. Надежность и безопасность структурно-сложных систем. -СПб.: Политехника, 2000.

53. Моделирование живучести систем энергетики: методология, модель, реализация. Сообщения по прикладной математике. М.: ВЦ АН СССР, 1986.

54. Кочкаров А.А., Кочкаров Р.А. Предфрактальные графы в проектировании и анализе сложных структур. Препринт ИПМ им. М.В. Келдыша РАН, №10. М., 2003.

55. Архипова Н.И., Кулъба В.В. Управление в чрезвычайных ситуациях. -М.: РГГУ, 1998.

56. Кочкаров А.А., Малинецкий Г.Г. Концепция стойкости для социально-экономических и технических систем. Труды Международной конференции "Математическое моделирование социальной и экономической динамики". М.: РГСУ, 2004.-с. 151-154.

57. Кочкаров А.А., Малинецкий Г.Г. Стойкость и обоснование стойкости сложных технических и социально-технических систем. Труды XI Международной конференции "Проблемы управления безопасностью сложных систем". Часть 1. М.: РГГУ, 2003. С. 50-53.

58. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

59. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

60. Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. М.: Эдиториал УРСС, 2000.

61. Николис Г., Пригожий И. Познание сложного. Введение. М.: Мир,1990.

62. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

63. Харари Ф. Теория графов. М.: Мир, 1973.

64. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. Новосибирск: Наука, 1998.

65. Евстигнеев В.А., Касьянов В.Н. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

66. Кестен X. Теория просачивания для математиков. М.: Мир, 1986.

67. Применение теории графов в химии / Под ред. Зефирова Н.С., Кучано-ва С.И. Новосибирск: Наука, 1988.

68. Химические приложения топологии и теории графов. Под ред. Кинга Р.-М.: Мир, 1987.

69. Миркин Б.Г., Родин С.Н. Графы и гены. М.: Наука, 1977.

70. Розенблит А.Б., Голендер А.Е. Логико-комбинаторные методы в конструировании лекарств. Рига: Зинатне, 1983.

71. Применение теории графов связи в технике / Под ред. КернопаД., Ро-зенберга Р. М.: Мир, 1974.

72. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

73. Волконский В.И., Груздов В.В., Сомик КВ. Связные информационные структуры метод интеграции экономики будущего. - М.: Полтекс, 2001.

74. Авондо-БодиноДж. Применение в экономике теории графов. М.: Прогресс, 1966.

75. Коробков С.А. Применение теории графов в геодезии. М.: Недра,1976.

76. Кулъба В.В., Назаретов В.М., Чухров И.П. Модифицированные функциональные графы как аппарат моделирования сложных динамических систем. Препринт. М.: Институт проблем управления, 1995.

77. Кулъба В.В., Кононов Д.А., Ковалевский С.С. и др. Сценарный анализ динамики поведения социально-экономических систем. Препринт. М.: Институт проблем управления, 2002.

78. Кононов Д.А., Кулъба В.В. и др. Синтез формализованных сценариев и структурная устойчивость сложных систем (синергетика и аттрактивное поведение). Препринт. М.: Институт проблем управления, 1998.

79. Кулъба В.В., Кононов Д.А., Косяченко С.А., Шубин А.Н. Методы формирования сценариев развития социально-экономических систем. М.: СИНТЕГ, 2004.

80. Малинецкий Г.Г. Хаос. Структуры. Вычислительный эксперимент: Введение в синергетику. / Сер. "Кибернетика: неограниченные возможности и возможные ограничения". М.: Наука, 1997.

81. Махутов Н.А., Гаденин М.М. Научные исследования и подготовка специалистов по обеспечению защищенности критически важных объектов // Машиностроение и инженерное образование. 2004. - № 1.

82. S. Milgram. The small world problem // Psychology Today. 1967. №2. Pp. 60-67.

83. Манделъброт Б. Фрактальная геометрия природы. М.: ИКИ, 2002.

84. Бандман О.Л. Методы параллельного микропрограммирования. Новосибирск: Наука, 1981.

85. Горбунова Е. О. Формально-кинетическая модель бесструктурного мелкозернистого параллелизма // Сибирский журнал вычислительной математики. 1999. Т. 2. № 3. С. 239-256.

86. Бандман O.JI. Мелкозернистый параллелизм в вычислительной математике // Программирование. 2001. №4. С. 5-20.

87. Бочаров Н.В. Технологии и техника параллельного программирования // Программирование. 2003. №1. С. 5-23.

88. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.

89. Кузюрин Н.Н. Параллельный алгоритм для задачи о балансировке множеств // Дискретная математика. 1991. Т.З. В.4. С. 153-158.

90. Bader D.A., Illendula А.К., Moret В.М.Е., Weisse-Bernstein N.R. Using PRAM algorithms on a uniform-memory-access shared-memory architecture. WAE2001. LNCS 2141. 2001. P. 129-144.

91. Agbaria A., Ben-Asher Y„ Newman I. Communication-processor tradeoffs in a limited resources PRAM. Algorithmica. 2002. № 34. P. 276-297.

92. Макконелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера,2002.

93. Metaxas P. Parallel Algorithms for Graph Problems. PhD dissertation, Dartmouth College, 1991.

94. Han Y., Pan V.Y., Reif J.H. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Algorithmica. 1997. № 17. P. 399^115.

95. King V., Poon Ch.K., Ramachandran V., Sinha S. An optimal EREW PRAM algorithm for minimum spanning tree verification. Information Processing Letters. 1997. №62. P. 153-159.

96. Sajith G., Saxena S. Optimal parallel algorithm for Brook's colouring bounded degree graphs in logarithmic time on EREW PRAM. Discrete Applied Mathimatics. 1996. № 64. P. 249-265.

97. Johnson D.B., Metaxas P. Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree. Algorithmica. 1996. № 16. P.633-648.

98. ChenZ.-Z., He X. Parallel algorithms for maximal acyclic sets. Algorithmica. 1997. № 19. P. 354-368.

99. Непомнящая А.Ш. Представление алгоритма Эдмондса для нахождения оптимального ветвления графа на ассоциативном параллельном процессоре // Программирование. 2001. №4. С. 43-52.

100. Кочкаров A.M. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН С АО, 1998.

101. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001.