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

•тв 0 л

т — У;.^ .' На правах рукописи

Марлей Владимир Евгеньевич

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

Специальность 05.13.16.. "Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях."

Автореферат диссертации на соискание ученой степени доктора

технических наук.

Санкт-Петербург. 1998

Работа выполнена в Санкт-Петербургском институте информатики и автоматизащ Российской Академии Наук.

Официальные оппоненты:

- доктор технических наук, профессор Пономарев В.М.

- доктор физико-математических наук, профессор Братчиков Б.Л.

- доктор технических наук, профессор Полуэктов P.A.

Ведущее предприятие - Санкт-Петербургский государственный электротехничесю университет.

Защита состоится ¿¿^^¿l^ftcX 1998г. в _ часов на заседай

специализированного совета Д.003.62гб1 в Санкт-Петербургском институте информатики автоматизации РАН по адресу: 199178, Санкт-Петербург, 14-я линия, д.39.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан ■¿F" cc&j^

1998г.

Ученый секретарь специализированного совета,

доктор физико-математических наук Копыльцов A.B.

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

Актуальность темы.

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

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

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

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

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

Цель работы.

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

1) Сформулирована концептуальная модель процесса алгоритмического моделирования на основе распределенных алгоритмических сетей.

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

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

3) Получены алгоритмы реализации операций и распознавания отношений для нераспределенных и распределенных алгоритмических сетей. Доказаны их свойства, определена оценка верхней границы сложности разработанных алгоритмов.

4) Определена формальная модель процесса вычислений на распределенных алгоритмических сетях. Осуществлено формальное доказательство свойств процесса вычислений для распределенных и нераспределенных алгоритмических сетей.

5) Разработаны методы преобразования алгоритмических моделей (распределенных и нераспределенных) на основе преобразования алгоритмических сетей при формировании структуры алгоритмических моделей, анализе их поведения и поиске решений.

6) Разработана концепция и укрупненная структура системы автоматизации алгоритмического моделирования на основе распределенных алгоритмических сетей.

Практическая ценность.

1) Разработанные методы и модели позволили повысить эффективность разработок новых версий системы автоматизации алгоритмического моделирования, повысить степень автоматизации процесса алгоритмического моделирования в этих системах, обеспечить, на основе распределенных алгоритмических сетей, сетевые режимы эксплуатации алгоритмических моделей (система автоматизации моделирования КОГНИТРОН, версия 2.0, разработана в СПИИРАН в 1997г. при непосредственном участии автора).

2) Разработанные алгоритмы были использованы при создании в СПИИРАН, при участии автора, версии системы автоматизации алгоритмического моделирования КОГНИТРОН 2.0, использовавшейся в Комитете по сельскому хозяйству при правительстве Ленинградской области, в Ивановском энергетическом университете, в .Региональном информационно-вычислительном центре С-ЗНЦ РАСХН.

Апробация работы.

Основные результаты исследований докладывались на 2-ой международной конференции Советской ассоциации искусственного интеллекта (Минск, 1990г.), международной конференции "Искусственный интеллект - промышленное применение" (Ленинград, 1990г.), международных конференциях "Региональная информатика" (С-Петербург, 1994-1996, 1998), международной конференции "Информатика и управление" (С-Петербург, 1997), "Первой международной конференции по проблемам самоорганизации и управления в сложных коммуникационных пространствах" (С-Петербург, 1997), на семинарах и рабочих совещаниях во время заграничных командировок в 1988-1990гг. в ЧССР (Integrated energy systems. 1IASA, Praga, 1988) и ГДР. Публикации.

По теме диссертации опубликовано 31 печатная работа. Структура работы.

Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложения, изложена на 178 страницах машинописного текста, 30 рисунков, список литературы 145 наименований. 2. Содержание работы. Первая глава.

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

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

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

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

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

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

Процедура алгоритмического моделирования представляется в виде следующе) последовательности действий:

Шаг 1. Формулировка решаемой проблемы и составление первоначальной словесного описания, сценария моделируемого процесса.

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

Шаг 3. Формирование нового сценария процесса в терминах выделенных явлений и ггношений, упорядочение сценария на основании выявленных в пункте 2 отношений (может 5ыть сделано в виде некоторого ориентированного графа, например вершины - явления, дуги ■ отношения следования).

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

Шаг 5. Формирование на основании полученных вычислительных зависимостей и описания задачи алгоритмической сети модели.

Шаг 6. Формирование задания для вычислительного эксперимента над моделью и сбор информации необходимой для его выполнения.

Шаг 7. Проведение вычислительного эксперимента и анализ его результатов.

Здесь и далее под сценарием будем понимать некоторое словесное структурированное и частично упорядоченное описание вариантов последовательностей явлений имеющих место в ходе моделируемого процесса.

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

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

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

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

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

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

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

Формальное описание АС представляется следующим образом:

Определение 1

АС ::= <Р, О, X, Б, Р-»Р, (}-»Х>

где:

Р - множество вершин сети {р,};

<3 - множество дуг сети {як};

X - множество переменных {х^}, при этом:

Х= X; - множество переменных 1-ой вершины, I - множество всех индексов 1 €1

вершин;

Р - множество операторов {

Р->Р - изоморфное отображение Р на Р, то есть индекс оператора можно считать также и индексом вершины;

<3-»Х - отображение С} наХ. Если сеть не пуста, то все множества не пустыеЛ Примеры АС приведены на Рис. 1. Определение 2

Оператор £ в множестве Б описывается:

£ ::=< ¡п(Г0, Г, оЩ(С)>

где:

Г - символ операции или функции, символ уникален для каждой операции; I - индекс (номер) операции в вычислительной схеме; т(Г|) - множество входных переменных оператора (возможно ¡п(£)=0); ои1(1'|) - множество выходных переменных оператора (всегда оиОД)*0)); Х*= т^иои^й) - множество всех переменных оператора, при этом ¡п(^)пои1(^)::-0; ¡п® я ои1(Щ содержат только те переменные, которые используются в выражениях описывающих Г, в ¡п(Г|) и оиКТ) может быть задан частичный порядок для их элементов. □

В общем случае ( может быть именем программного модуля или другой АС, операторы могут быть определены над действительными числами, логическими переменными, скалярами, векторами, матрицами, структурами и т.п.

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

Структура АС удовлетворяет следующим ограничениям:

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

- для любых пар вершин, ои1(ГОлоШ(^)*0, если и только если \='у,

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

НАГ—^

{дК—о

а)

Р1:х2=х1+х3 Р2: Х5=Хг-х, Р1: хг-х^х^

Р1: х,С0-х,(1>+х2(1) Р2: х5(0=х,(0-*,Ш Р1: х2(1+1)»х5(1)

Р.

- X

б)

о

Рис. 1. Примеры допустимых (а) и недопустимых конструкций (6) в АС.

оШ(АС)= и ои1(Г,) - множество всех вычисляемых переменных АС,

I е1

и»(АС) = и ВД \ и оиОД - множество входных переменных АС.

■ «1 ■ ЕI

Алгоритмическая модель (АМ) отображает принятый сценарий моделируемого [роцесса, отражает, причинно-следственные связи между его явлениями, при этом юнкретного процесса, поэтому помимо собственно АС, содержит также информацию об штерпретации переменных АС в терминах предметной области, данных, необходимых для 1асчета, об объекте предметной области. С учетом сказанного:

Определение 3

Алгоритмическая модель определяется:

АМ::=<1М, ОРО, 10, ОР, АС, Т, МО, Х->Т, Р-»Г>

где:

1М - идентификатор модели;

ОРО - описание предметной области;

Ю - описание объекта, для которого разработана модель;

ОР - описание процесса, для которого разработана модель;

АС - алгоритмическая сеть (описание структуры модели);

Т - множество терминов предметной области, используемых в модели, ТсТРО, где ГРО - множество всех терминов предметной области, ТРО=Т1иТ;ги...иТр0, где ро - общее число моделей одной предметной области;

МО - множество вариантов законов изменения значений переменных модели;

Х->Т - отображение множества переменных АС модели в множество терминов предметной области, используемых в модели, возможно Х'-»Т, где Х'сХ;

Р->Т - отображение множества операторов АС модели в множество терминов предметной области, используемых в модели, возможно где Р'сР;

Х->Тпр-»Т=0;

если модель не пуста, то всегда не пусты 1М и АС, остальные объекты описания могут быть пусты. □

С учетом изоморфности отображения Р->К, аналитически АС, если не учитывать особенностей ее графического представления, может быть задана одним множеством Г н все операции и отношения на АС определяются как некоторые преобразования Е.

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

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

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

Две АС равны (АС]=АС^), если и только если их множества Б равны (Р|=1^).

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

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

АС1 изоморфно вкладывается в АС2, если АС2 содержит подграф изоморфный АС1 (обозначается АС^АСг).

Над произвольными АС определяются следующие операции.

Пересечение АС1ПАС2, равно АС включающей все совпадающие вершины исходных.

Объединение АС|иАСг, равно АС включающей все вершины той и другой АС при условии выполнения условий: нет пресечения множеств выходных переменных для вершин исходных АС не входящих в пересечение АС, и связывание вершин исходных АС между собой не приводит к образованию контуров без вершин с операторами "задержка", иначе результат операции пуст. Если при объединении ряда АС АС=АС1и...иАС„ , хотя бы для одной пары произвольно взятых объединяемых АС их объединение пусто АС^АСр0, то АС=АС1и...иАС„=0.

Разность АСДАСг, равна первой АС без подграфа соответствующего пересечению исходных АС.

Агрегация А^АС), соответствует замене некоторого подграфа исходной АС одной вершиной содержащей оператор, в котором объединены выражения соответствующие всем операторам агрегируемого подграфа, внешние дуги такой вершины соответствуют внешним дугам агрегируемого подграфа, т.е. дугам, которыми он соединялся со своим дополнением в исходной АС и внешним дугам исходной АС, которые были в данном подарафе, а также выходным дугам, соответствующим промежуточным расчетным переменным агрегируемого подграфа, {р,} - множество вершин агрегируемого подграфа.

Дезагрегация ОАр^АС), операция обратная агрегации, соответствует замене некоторой вершины АС подграфом построенным на основании набора выражений определяющих оператор приписанный вершине, р - дезагрегируемая вершина.

Преобразование описания вершины СЬчр,(АС)-/0, если математическое выражение описывающее оператор в вершине допускает равносильные преобразования не приводящие к частичному обращению АС (приведение подобных, вынесение за скобки, раскрытие скобок, разделение на промежуточные выражения, поглощение промежуточных выражений), результатом является новая АС'=СЬчр1(АС) с другим выражением описывающим оператор £ и, возможно с другими множествами ¡п(АС), ои1(АС). р, - преобразуемая вершина, q -описание преобразования.

Частичное обращение АС'=ОЬ&(АС), результат операции новая АС, где т(АС')=11 и для некоторого подмножества вершин исходной АС, на основании Я и связей между вершинами выполнена операция частичного обращения (разрешение выражения соответствующего оператору в вершине относительно другой переменной). Возможны следующие варианты результата операции:

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

- набор недостаточен, произошло не полное частичное обращение (т.е. только подграфа исходной АС), результат не пуст (если подграф не пуст), т(ЛС')сК;

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

Вершины с операторами задержки всегда однонаправлены. При выполнении операции частичного обращения вершины с операторами задержки рассматриваются только после того как операция проведена для всей остальной части АС.

Выделение подграфа по заданным подмножествам входных н выходных для него дуг АС'=8°|(АС), где О - множество переменных исходной АС, все соответствующие которым дуги будут внешними выходными дугами получаемого подграфа, I - множестве переменных исходной АС, все соответствующие которым дуги будут вешними входными дугами получаемого подграфа, РсК, Х'сХ, 1ст(АС'), ОсоЩ(АС');

возможны следующие случаи:

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

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

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

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

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

Особо следует отметить следующее, определение операции объединения вноси: парадокс, когда АСи0=АС, но, если АС|иАСг=0, то АС^АС^иАСз^АСз, а АС1иАС2иАСз=0. Таким образом соотношения АС, аналогичные теоретико-множественным, в которых участвует операция объединения АС справедливы только, когда операция объединения имеет не пустой результат. Если учитывается возможность пустогс результата операции объединения, это оговаривается особо. Приводимая теорема уточняет условия применения операции объединения АС.

Теорема 1.

Если объединение некоторого множества АС не пусто АС=АС 1 и..то:

1. Объединение любого подмножества АС из данного множества, где хоть одна из оставляющих не пуста, также не пусто.

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

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

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

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

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

Для всех операций разработаны алгоритмы реализации имеющие верхнюю границу щенки сложности пропорциональную квадрату числа вершин исходных АС. Разработаны )бщие алгоритмы распознавания отношения равенства, включения одной АС в другую, «оморфности, изоморфного вложения, эквивалентности по обращения. Данные алгоритмы шегот экспоненциальную оценку сложности (для равенства и включения квадратичные). %1Я отношения эквивалентности по реализуемой функции разработана процедура с жспоненциальной оценкой сложности позволяющая в отдельных случаях распознать это угиошение.

Определение 4.

Множество алгоритмических сетей и операции определяют алгебру АС:

А=<{АС},П>

где:

{АС} - множество всех возможных АС;

€1 - множество операций над АС. □

Вычисление значений переменных АС осуществляется повершинно, вычисления производятся только в тех вершинах, для которых известны значения всех перемененных входящих в и все вычисления соответствующие вершине полностью выполняются, то есть становятся известны значения всех переменных входящих в оШ(£). Множество 'V/ известных переменных АС пополняется переменными рассчитанными в вершине, и т.д., пока не будут вычислены все переменные во всех вершинах АС за исключением вершин с операторами типа "задержка". Все рассчитанные значения будут соответствовать одному шагу моделируемого процесса, после этого срабатывают операторы задержки и переводят модель на следующий шаг моделирования, при этом переменные соответствующие их выходам принимают значения переменных, соответствующим их входам. Далее вводятся исходные данные для следующего шага, и процесс расчета АС повторяется для нового шага и т.д. Вычисление значений переменных АС всегда выполняется для всех вершин АС, для всех переменных входящих в оШ(АС), считается, что исходные данные заданы для всех переменных из ¡п(АС), значения переменных соответствующих выходам вершин с операторами задержки известны, если это не выполняется результат вычислений пуст.

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

Шагом расчета АС называется однократное проведение расчетов для всех ее вершин без операторов задержки и однократное срабатывание операторов задержки во всех вершинах, которым они сопоставлены.

Теорема. 2.

АС вычислима тогда и только тогда, когда заданы значения всех переменных входящих в ¡п(АС).

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

На основании плана вычислений формируется программа расчета по АС на шаге вычислений. Программный код соответствующий £ подставляется вместо соответствующей вершины в плане вычислений.

Программа расчета АС на все заданные шаги будет получена из программы шага вычислений, введением внешнего цикла по числу заданных шагов.

Если операторы в вершинах. АС дают однозначный результат, то результат вычисления всей АС однозначен. Третьи глава.

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

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

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

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

АМ считаются равными на заданном уровне абстрагирования, АМ1=АМ2, когда все элементы описания АМ, учитываемые на заданном уровне абстрагирования совпадают.

АМ считаются изоморфными на заданном уровне абстрагирования, АМ]~АМ2 тогда и только тогда, когда изоморфны их АС.

На основании имеющегося практического опыта выделяются следующие основные функции работы с АМ: формирование структуры АМ; исследование поведения АМ; поиск и принятие решений на основе АМ.

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

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

1) Формирование АС модели.

2) Задание интерпретации АМ.

3) Формирование задания для вычислительного эксперимента на АМ.

4) Сбор недостающей и корректировка имеющейся исходной информации для проведения вычислительного эксперимента над АМ.

5) Проведение вычислительного эксперимента на АМ.

6) Анализ результатов вычислительного эксперимента на АМ.

Допускается параллельность процессов при выполнении функций и использование в при их реализации идентичных преобразований над АМ.

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

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

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

Задание интерпретации АМ заключается в формировании X—>Т и Р-»Т.

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

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

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

- в задании IV, РУ ;

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

- проведения требуемых преобразований АС модели, формирования плана вычислений и расчетной программы для проведения вычислительного эксперимента;

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

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

Сбор недостающей и корректировка имеющейся исходной информации для проведения вычислительного эксперимента над АМ заключается в поиске и задании значений элементов МГ) и 71, или их корректировке в соответствии с поставленной целью. Возможны различные варианты получения исходной информации:

- экспертные оценки;

- обработка имеющихся статистических данных;

- заимствование из МБ других АМ или из МБ данной модели из вариантов законов изменения значений переменных соответствующих другим вычислительным экспериментам;

- поиск информации в базах данных не связанных с АМ;

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

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

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

Анализ результатов вычислительного эксперимента на АМ заключается I представлении результатов расчета пользователю, формированию оценки результата расчет: в соответствии с поставленной целью и требуемой точности получения результата, 1 определении необходимых преобразований АС и МИ и возврату (если это требуется) 1 процессам проведения вычислительного эксперимента, сбора и корректировки информацщ или формирования задания на эксперимент.

Основные принимаемые положения взаимодействия и преобразования АМ:

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

- одну и ту же АМ можно рассматривать на разных уровнях абстрагирования;

- операции выполняются только для АМ одного уровня абстрагирования;

- каждое преобразование АМ имеет свой максимально допустимый уровен абстрагирования, при котором выполнение преобразования возможно (при более высоко* уровне абстрагирования невозможно, при уровне ниже допустимого возможно;

- выполнение преобразований над АС моделей не изменяют уровня и: абстрагирования;

- выполнение преобразований над АМ (кроме абстрагирования) не повышает уровен; их абстрагирования (чаще уменьшают его);

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

Таким образом обобщенная процедура выполнения преобразований АМ, в юльшинстве случаев, будет иметь следующий вид:

1) Анализ уровня абстрагирования описания модели(моделей) на соответствие максимальному допустимому для требуемого преобразования.

2). Приведение всех взаимодействующих моделей к одному уровню абстрагирования если рассматривается несколько моделей).

3) Выполнение преобразований над АС модели (моделей).

4) Преобразование остальных элементов описания АМ в соответствии с результатом 1реобразований над АС.

5) Распространение результатов преобразования над АМ на более низкие уровни 1бстрагирования (если это возможно и необходимо).

При формирования модели АС в начале пуста. Далее происходит трудно формализуемый процесс экспликации, в данном случае выражения характеристик явлений, происходящих в ходе моделируемого процесса, в виде переменных, а причинно-:ледственных связей между явлениями в виде вычислительных зависимостей. В результате то сути одновременно формируются подмножества X, Р и Х->Т, Р-УГ. Далее происходит этображение на Р и X некоторой графической конструкции, т.е. строится подмножества Р, <3 а Р—>Р и (2->Х. Появляются некоторые фрагменты АС, которые далее объединяются друг с цругом в более крупные фрагменты и так далее, пока создатель модели не посчитает, что достаточно полно отобразил принятый им сценарий моделируемого процесса.

Если имеются ранее разработанные АМ, то процесс формирования структуры АМ, может быть частично автоматизирован. Пусть имеется некоторое множество АМ {АМ,}, для [«которых пар пересечение их множеств Т| не пусто (Т,п'Г^0). Требуется сформировать структуру АМ, для которой заданы подмножества исходных переменных W, расчетных переменных V', которые обязательно должны присутствовать в формируемой модели, подмножества терминов предметной области Т такое, что \У'->Т', V'—>Т' не пусты. Ищется такое подмножество из фрагментов АС имеющихся моделей, объединение которых даст АС , обеспечивающую максимальное включение элементов из V/' в ш(АС) и V' в оЩ(АС) и обеспечит их функциональную связь, для формируемой модели. Для элементов из W, и V' не вошедших в полученную таким образом АМ, использующий их фрагмент АС и АМ формируется вручную. Разработана процедура позволяющая автоматизировано получить АС модели из фрагментов АС других моделей.

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

(примененная к одной из сливаемых АС, она позволяет в ряде случаев получить не пустой результат, для сетей, которые давали пустой результат).

При создании АС модели пользователь с одной стороны стремится полнее отобразить принятый сценарий моделируемого процесса, с другой стороны сделать модель компактной и обозримой. Если среди ранее построенных моделей есть модели смежных процессов, построенные для того же объекта, с уже исследованными свойствами и подготовленными информационными массивами, то можно определить пересечение этих моделей и, если оно не пусто, то вычесть соответствующий подграф из формируемой модели. В формируемой модели входные переменные будут принимать значения рассчитанные в смежной модели. Можно производить равносильные преобразования с целью оптимизации структуры и над уже сформированной АС модели, с использованием операций агрегации, дезагрегации и преобразования выражения в вершине. В частности, когда структура модели сформирована, а исходная информация для расчетов известна не полностью, проводить вычислительные эксперименты с АМ уже можно. Для этого необходимо редуцировать АС модели. Дня части переменных из т(АС), законы изменения значений которых известны необходимо выполнить ОЬ1п(ас)'(АС), где ш(АС)' - часть ш(АС) с известными законами изменения значений. В результате будет выделена та часть АС модели, которая может быть рассчитана только на основе ¡п(АС)' и для нее может быть сформирован план вычислений и синтезирована расчетная программа. Когда законы изменения значений остальных переменных из т(АС)\т(АС)' станут известны, то, если законы изменения значений для переменных из т(АС)' можно принять неизменными, то из АС можно выделить АС\ОЬ|п(АСТ(АС), с которой и проводить дальнейшие вычислительные эксперименты. Таким образом можно работать с более обозримыми АС и в меньшей степени зависеть от наличия всей необходимой исходной информации.

При сборе исходной информации для проведения вычислительного эксперимента над АМ возможно заимствование ее из МО соответствующих другим вычислительным экспериментам над рассматриваемой моделью. Для поиска исходной информации в МБ других моделей применяется процедура аналогичная процедуре формирования АС модели из фрагментов АС других АМ.

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

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

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

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

Четвертая глава.

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

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

Определение 5.

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

Распределенная АС может состоять из одного фрагмента, тогда она буде соответствовать обычным АС.

Распределенная АС состоящая из непересекающихся фрагментов, называете распределенной АС канонического вида.

Все введенные для единых АС операции применимы и к распределенным, » возникают некоторые особенности, которых не было в обычных АС. Распределенная АС н имеет единого множества Р, а имеет множество множеств Р^ соответствующих фрагмента: составляющим распределенную АС, но все операции и отношения для распределенных А( реализуются так, как если бы существовала обычная АС составленная из имеющихс фрагментов АС'=АС|и„.иАС„*0 с единым множеством Р'=р1и...иРп/-0.

Обычная нераспределенная АС, которая была бы получена из фрагменто распределенной АС при их объединении согласно с определением объединения обычных А( АС'=АСIи.. .иАС„, называется замещающей АС.

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

Отношения и операции над распределенными АС определяются чере соответствующие отношения и операции над их замещающими АС. Однако есть некоторы отношения характерные только для распределенных АС.

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

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

Распределенная сеть АС1 вкладывается в АС2 по распределению, когда в АС2 имеется юдграф равный по распределению АС1.

Распределенная сеть АС1 изоморфно вкладывается в АС1 по распределению, когда в 1С2 имеется подграф изоморфный по распределению АС1.

Особенности алгоритмов реализации операций для распределенных АС проистекают □ того что поиск и преобразования происходят не в едином множестве F, а в множестве аких множеств. Разработаны алгоритмы реализации операций и распознавания отношений (ля распределенных АС. Те, которые имели для нераспределенных АС квадратичную юрхнюю оценку сложности, имеют полиномиальную от числа фрагментов и числа вершин, :оторые имели экспоненциальную также имеют экспоненциальную, с учетом числа фрагментов. Все теоремы сформулированные для операций над обычными АС будут :праведливы и для распределенных АС.

Все операции над распределенными АС сводятся к операциям над обычными АС, :сли взаимодействующие АС содержат по одному фрагменту и предполагается образование здиного множества F для результирующей АС.

Определение 6.

Множество распределенных и нераспределенных алгоритмических сетей и операции определяют алгебру распределенных АС:

А= <{АС}', Í2'>

где:

{АС}' - множество всех возможных (распределенных и обычных) АС;

О' - множество операций над АС. □

Алгебра обычных АС есть частный случай алгебры распределенных АС.

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

Распределенная АС вычислима, если заданы значения всех переменных из in(AC).

Рассмотрим вычисления на распределенных АС. Исходная распределенная АС вычислима при заданном in(AC), хотя бы в одном фрагменте есть хотя бы одна вершина вычисляемая только на основании in(OAC¡)nin(AC). Далее возможно, что вычисление данной вершины позволит вычислить еще ряд вершин в рассматриваемом фрагменте и т.д., но это приведет не к полному вычислению фрагмента, а только части его сети. Выполним

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

Число вычислительных подфрагментов во фрагментах распределенной АС и их структура однозначно определяется заданной декомпозицией исходной АС.

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

Определение 7.

Распределенной АМ называется множество АМ, которые обмениваются между собой информацией в процессе проведения расчетов и взаимодействие которых частично упорядочено. □

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

В пятой главе рассматриваются существующие возможности реализации предложенных методов на ЭВМ, на примере, оригинальной системы автоматизации на основе АС КОГНИТРОН и возможности частичной реализации преобразований над АС в крупноформатных электронных таблицах (ЕХСЕЬ). На основании разработанных методов преобразования АС и АМ разрабатывается укрупненная структура системы автоматизации

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

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

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

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

4. Уточнена формальная модель процесса вычислений на АС, рассмотрены условия однозначности результата вычислений и особенности синтеза программ по АС.

5. Сформулированы условия возможности сравнения и взаимодействия АМ, разработана общая схема преобразований АМ на основе преобразований АС.

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

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

8. Разработаны общие алгоритмы реализации введенных операций и распознавания отношений для распределенных АС.

9. Введена формальная модель процесса вычислений на распределенных АС, исследованы его свойства, даны алгоритмы организации процесса вычислений.

10. Введены преобразования распределенных АМ на основе соответствующих преобразований нераспределенных АМ.

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

Полученные результаты позволили автоматизировать и переложить на ЭВ\ процедуры ранее выполнявшиеся "вручную", что позволяет на порядок уменьшить врем: реализации алгоритмических моделей, реализуемые в разрабатываемой в СПИИРАН Hoeoi версии системы автоматизированного алгоритмического моделирования КОГНИТРОН Система КОГНИТРОН обеспечивает большую степень автоматизации, возможность рабоп с распределенными моделями и практически исключает кропотливую "ручную" работу пр: создании и эксплуатации моделей.

Практическое использование различных версий системы КОГНИТРОН созданны для различных приложений (сельское хозяйство, теория корабля, экономический анали деятельности предприятий и т.п.) показывает высокую эффективность полученных диссертации результатов. Так, например, использование системы для автоматизированног построения моделей в Госплане РСФСР позволило сократить процесс формировани сводного плана и, за счет этого, рассматривать не как обычно 1 -2 варианта, а 10-20 варианта плана.

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

4. Работы, опубликованные по теме диссертации.

1. В.В. Иванищев, М.Б. Егоров, В.Е. Марлей, В.П. Морозов. Проблемно-ориентированнь: решатель задач. Л.: ЛНИВЦ АН СССР, 1983,24 с, препринт.

2. V.V. Ivanischev, М.В. Egorov, V.E. Marley, V.P. Morozov. Problem-oriented tasksolver. Г LRCC AS USSR, 1983, 20 p.

3. B.B. Иванищев, В.Е. Марлей, В.П. Морозов. Диалоговая процедура автоматизацт построения программного обеспечения модели на основе матричного представления ее сет // Системы автоматизации в науке и производстве. М.: Наука, 1984, с.14-22.

4. В.В. Иванищев, В.Е. Марлей, В.П. Морозов. Язык алгоритмических сетей. Л.: ЛНИВЦ А СССР, 1984,37 с, препринт № 63.

50850000165. B.B. Иванищев, B.E. Марлей, В.П. Морозов. Проблемный пакет программ эссия-84. Л.: ЛНИВЦ АН СССР, 1984, 65 с.

В.Е. Марлей, В.П. Морозов. Интерпретация алгоритмических сетей как языковых иструкций. // Проблемы автоматизации в научных и производственных процессах. М.: ука, 1985, с. 37-46.

В.В. Иванищев, В.Е. Марлей, В.П. Морозов, Л.С. Ионова, В.А. Мещерин. Модель эномического и социального развития республики ("Русь"). Л.: ЛНИВЦ АН СССР, 1985, е., препринт №70.

В.В. Иванищев, В.Е. Марлей, В.П. Морозов. Модель экономического и социального звития республики. // Проблемы автоматизации в научных и производственных процессах. .: Наука,1985, с.5-9.

В.Е. Марлей, В.П. Морозов. Использование метода резолюций для планирования [числений на алгоритмических сетях. // Методы и системы автоматизации в задачах науки производства. М.: Наука, 1986, с.23-34.

'. В.Е. Марлей. Алгоритм планирования вычислений на алгоритмических сетях, пользующий ситуацию переопределенности. // Методы и системы автоматизации в задачах 1уки и производства. М.; Наука, 1986, с.34-38.

. В.А. Мещерин, Л.С. Ионова, В.В. Иванищев, В.Е. Марлей, В.П. Морозов. Пакет шкладных программ "Россия-84". И Интегрирование обработки плановой информация^ М.: »план РСФСР, 1986, с.5-9.

!. В.В. Иванищев, В.Е. Марлей, В.П. Морозов. Инструментальная экспертная система [нтеза программ для построения моделей плановой экономики. // III Всесоюзная иференция "Автоматизация производства систем программирования". Таллин: АН ЭССР, >86, с. 120-122.

1. В.В. Иванищев, В.Е. Марлей, В.П. Морозов. Система автоматизации моделирования АПФИР-Искра. Основы построения системы. Л.: ЛИИАН.1989, 63 е., препринт № 99. t. В.В. Иванищев, В.Е. Марлей, С.А. Машистов, В.П. Морозов, В.В. Тубольцева, Е.А. (екатихин. Алгоритмическая модель развития машиностроительного предприятия 1отенциал-86). Л.: ЛИИАН.1988,62 е., препринт № 65.

5. В.В. Иванищев, В.Е. Марлей. Типовые конструкции алгоритмических сетей. // Вопросы 1горитмического моделирования сложных систем. Л.: ЛИИАНД989, с 7-25.

16. B.B. Иванищев, B.E. Марлей, В.П. Морозов, JI.C. Ионова, В.А. Мещери Алгоритмические модели годового планирования республики. Л Вопросы алгоритмическо] моделирования сложных систем. JI.: ЛИИАН.1989, с 131-139.

17. V.R. Okorokov, V.V. Ivanischev, A.A. Bahorev, V.E. Marley. Comparative Simulation of Ne Power Technolgies. // INTEGRATED ENERGY SYSTEMS. Socioeconomic and Ecological Issue IIASA, 1989, p. 144-147.

18. B.E. Марлей. Входной язык системы САПФИР как язык программирования высоко! уровня. // II Всесоюзная конференция ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ - 90 Мине САМИ, 1990, с. 85-88.

19. V.V. Ivanischev, V.E. Mariey, V.P. Morozov, V.V. Tuboltzeva. Decision-making in tl SAPFIR simulation automation system. II International conference ARTIFICIAL INTELL1GENC - INDUSTRIAL APPLICATION. Leningrad: L1IAN, 1990, p. 231-233.

20. B.E. Марлей. Алгоритмические сети и параллельные граф-схемы алгоритмов. Проблемы информационной технологии и интегральной автоматизации производства. J; Наука, 1989, с 130-136.

21. В.В. Иванищев, А.П. Кругов, В.Е. Марлей, A.A. Петров, И.Г. Поспелов. Реализащ математической модели плановой экономики с элементами рынка в термин; алгоритмических сетей. Л.: ЛИИАН,1991, 59 с., препринт № 152.

22. В.В. Иванищев, В.Е. Марлей. Макроэкономическая модель развития региона в условия рынка. // Информатика и вычислительная техника. Выпуск 1,1994, с. 7-11.

23. В.Е. Марлей. Эквивалентность в алгоритмических моделях и алгоритмических сетях. IV С-Петербургская международная конференция "РЕГИОНАЛЬНАЯ ИНФОРМАТИКА 95. Тезисы докладов. Часть 1. С-Петербург: 1995, с. 75-76.

24. В.В. Иванищев, В.Е. Марлей, В.В. Михайлов. Рекуррентная модель технологическо1 процесса в терминах матричного представления. // IV С-Петербургская международна конференция "РЕГИОНАЛЬНАЯ ИНФОРМАТИКА - 95. Тезисы докладов. Часть 1. ( Петербург: 1995, с. 61-63.

25. В.Е. Марлей, В.Б. Скуратов. Концепция информатизации агропромышленного комплек( Нечерноземной зоны России. II IV С-Петербургская международная конференщ "РЕГИОНАЛЬНАЯ ИНФОРМАТИКА - 95. Тезисы докладов. Часть 1. С-Петербург: 1995, 25-26.

26. О.Ф. Королев, В.Е. Марлей. Вычисления на распределенных алгоритмических сетях. И Материалы первой международной конференции по проблемам самоорганизации и управления в сложных коммуникационных пространствах. С-П.: 1997, с 58-60.

27. В.В. Иванищев, В.Е. Марлей, В.П. Морозов, В.В. Михайлов, Я.А. Быков, С.М. Алексеев. Инструментальная система автоматизации моделирования КОГНИТРОН. // Информационные технологии и вычислительные системы. 1998, № 2, в печати (8 е.).

28. В.Е. Марлей. Алгебра алгоритмических сетей. Юбилейный сборник трудов СПИИРАН. С-Петербург: Наука,1998, в печати (14 е.).

29. V.E. Marley. Operations over algorithmic networks. II Interactional conference on informatics and control. Proceedings. ST.Peterburg: 1997, p 451-458.

30. В.Е. Марлей, О.Ф. Королев, П.И. Калашников. Функции оценки состояния системы. // Региональная информатика-98. РИ-98. Тезисы докладов. Часть 1. Санкт-Петербург: 1998, с.43-44.

31. В.Е. Марлей. Распределенные алгоритмические сети. // Региональная информатика-98. РИ-98. Тезисы докладов. Часть 2. Санкт-Петербург: 1998, с.31-32.



Санкт-Петербургский институт информатики и автоматизации РАН

14 „игШ> вв

' - ■: \ Щ • А к л Марлей Владимир Евгеньевич

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

$1.3.06

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

Специальность 05.13.16.. "Применение вычислительной техники, математического моделирования и математических методов в

научных исследованиях."

Диссертация на соискание ученой степени доктора

технических наук.

Санкт-Петербург. 1998

Содержание

Введение...........................................................................................................................4

Глава 1. Концепция алгоритмического моделирования на основе распределенных алгоритмических сетей..............................................9

1.1. Алгоритмическое моделирование и текущее состояние теории алгоритмических сетей...................................................................................................9

1.2. Концептуальная модель процесса алгоритмического моделирования

на основе распределенных алгоритмических сетей..............................................21

1.3. Обсуждение и выводы по главе 1.......................................................................25

Глава 2. Алгоритмические сети - формализм для описания структуры моделей сложных

систем........................................................................................................27

2.1. Алгоритмические модели и алгоритмические сети, основные определения....................................................................................................................27

2.2. Операции над алгоритмическими сетями и отношения на алгоритмических сетях.................................................................................................36

2.3. Вычисления на алгоритмических сетях.............................................................98

2.4. Обсуждение и выводы по главе 2......................................................................109

Глава 3. Преобразования алгоритмических моделей,

описанных на основе алгоритмических сетей в процессе

их разработки и эксплуатации..............................................................112

3.1. Преобразования алгоритмических моделей....................................................112

3.2. Методы формирования структуры алгоритмических моделей....................118

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

3.4. Методы принятия решений на алгоритмических моделях..........................146

3.5. Обсуждение и выводы по главе 3......................................................................156

Глава 4. Распределенные алгоритмические сети и алгоритмические модели......................................................................161

4.1. Операции, отношения и вычисления на распределенных алгоритмических сетях...............................................................................................161

4.2. Преобразования распределенных алгоритмических моделей....................185

4.3. Обсуждение и выводы по главе 4......................................................................189

Глава 5. Автоматизации моделирования на основе распределенных алгоритмических сетей...........................................191

5.1. Существующие возможности автоматизации моделирования

на основе алгоритмических сетей........................................................................191

5.2. Структура системы автоматизации моделирования на основе распределенных алгоритмических сетей...............................................................196

5.3. Обсуждение и выводы по главе 5.....................................................................200

Заключение..............................................................................................202

Литература...............................................................................................205

Введение

Актуальность темы.

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

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

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

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

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

1) Сформулирована концептуальная модель процесса алгоритмического моделирования на основе распределенных алгоритмических сетей.

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

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

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

3) Получены алгоритмы реализации операций и распознавания отношений для нераспределенных и распределенных алгоритмических сетей. Доказаны их свойства, определена оценка верхней границы сложности разработанных алгоритмов.

4) Определена формальная модель процесса вычислений на распределенных алгоритмических сетях. Осуществлено формальное доказательство свойств процесса вычислений для распределенных и нераспределенных алгоритмических сетей.

5) Разработаны методы преобразования алгоритмических моделей (распределенных и нераспределенных) при формировании структуры алгоритмических моделей, анализе их поведения и поиске решений.

6) Разработана концепция и укрупненная структура системы автомматизации алгоритмического моделирования на основе распределенных алгоритмических сетей. Практическая ценность.

1) Разработанные методы и модели позволили повысить эффективность разработок новых версий системы автоматизации алгоритмического моделирования, повысить степень автоматизации процесса алгоритмического моделирования в этих системах, обеспечить, на основе распределенных алгоритмических сетей, сетевые режимы эксплуатации алгоритмических моделей (система автоматизации моделирования КОГНИТРОН, версия 2.0, разработана в СПИИРАН в 1997г. при непосредственном участии автора).

2) Разработанные алгоритмы были использованы при создании в СПИИРАН, при участии автора, версии системы автоматизации алгоритмического моделирования КОГНИТРОН 2.0,

использовавшейся в Комитете по сельскому хозяйству при правительстве Ленинградской области, в Ивановском энергетическом университете, в Региональном информационно-вычислительном центре С-ЗНЦ РАСХН. Апробация работы.

Основные результаты исследований по теме диссертации докладывались на 2-ой международной конференции Советской ассоциации искусственного интеллекта (Минск, 1990г.), международной конференции "Искусственный интеллект - промышленное применение" (Ленинград, 1990г.), международных конференциях "Региональная информатика" (С-Петербург, 1994-1996, 1998), международной конференции "Информатика и управление" (С-Петербург, 1997), "Первой международной конференции по проблемам самоорганизации и управления в сложных коммуникационных пространствах" (С-Петербург, 1997), на семинарах и рабочих совещаниях во время заграничных командировок в 19881990гг. в ЧССР (Integrated energy systems. HAS A, Praga, 1988) и ГДР. Публикации.

По теме диссертации опубликовано 31 печатная работа. Структура работы.

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

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

последовательность этапов работ необходимых для достижения поставленной цели исследования.

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

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

В пятой главе рассматривается реализация операций на АС в крупноформатных электронных таблицах (EXCEL), системе автоматизации моделирования КОГНИТРОН, формируется структура сетевой системы автоматизации моделирования на основе распределенных алгоритмических сетей.

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

Глава 1. Концепция алгоритмического моделирования на основе распределенных алгоритмических сетей.

1.1. Алгоритмическое моделирование и теория алгоритмических сетей.

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

Функциональный подход фактически носит формально-математический характер [1] и требует от пользователя довольно высокого уровня математической подготовки, ориентирования в уже существующих формальных моделях и умения подгонять эти модели к реальному моделируемому процессу. Если пользователь не имеет такой подготовки, между ним и моделью возникает ряд посредников, но за результат все равно несет ответственность пользователь. Поэтому условием доверия пользователя к полученным результатам будет возможность содержательно понять суть модели, алгоритм, по которому получается результат, а, при необходимости, возможность выполнения части этапов получения результата вручную [2].

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

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

Алгоритмический подход породил понятие алгоритмической модели [4-5]. Под алгоритмической моделью здесь понимается формализованное описание сценария предметного специалиста для моделируемого процесса, структура которого сопоставима со структурой причинно-следственных и временных зависимостей между явлениями моделируемого процесса, вместе со всей информацией необходимой для ее программной реализации.

Провозглашенная в 1983г. разработка "новой информационной технологии" [2], привела к появлению в искусственном интеллекте направления "разработка дружественного интерфейса", ориентации разрабатываемого программного обеспечения непосредственно на конечного пользователя, минуя всех посредников. Разработка компьютерных технологий ориентированных на конечного пользователя, для различных отраслей народного хозяйства и социальной сферы, на основе использования методов искусственного интеллекта была одним из основных направлений исследований Санкт-Петербургского института информатики и автоматизации РАН (СПИИРАН) с его основания в 1977г. Это нашло свое отражение в выпущенных институтом сборниках трудов, организации научно-технических конференций, в участии в ряде программ, ориентированных на внедрение вычислительной техники в управление народным хозяйством. Ориентация на конечного пользователя привела к применению алгоритмического подхода, алгоритмического моделирования [4-5]. Алгоритмический подход может использовать различные методы формализации модели, одним из таких является метод представления алгоритмических моделей на основе алгоритмических сетей, разрабатываемый в СПИИРАН с 1978г. [6].

Алгоритмические сети (АС) используются для представления структуры алгоритмических моделей. Обычно, в имеющейся литературе [6-115], алгоритмические сети определялись как

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

Каждой дуге соответствует только одна переменная, переменной может соответствовать несколько дуг, множества выходных пременных вершин АС не пресекается, АС не содержит контуров, если в них нет хотя бы одной вершины с операцией задержки. Операция задержки служат в вершинах АС для задания исходного состояния моделируемого процесса и для описания перехода моделируемого процесса через шаг моделирования. Примеры алгоритмических сетей приведены на Рис. 1.1.1. Примеры разрешенных и запрещенных конструкций АС приведены на Рис. 1.1.2. АС на Рис. 1.1.1 .а представляет собой емкость, где: XI - состояние емкости на конец периода М или начало периода 1:; хг - приход в емкость в период 1:; хз - состояние емкости без учета расхода в период г; Х4 - расход в период 1:;

Х5 - состояние емкости �