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

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

Старостин Петр Александрович

ИССЛЕДОВАНИЕ АЛГЕБРАИЧЕСКИХ СЕТЕЙ, ПОРОЖДАЮЩИХ СОВОКУПНОСТЬ ВЫЧИСЛИТЕЛЬНЫХ МОДЕЛЕЙ

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

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

ООЗ161721

Москва-2007

003161721

Работа выполнена в отделе теории алгоритмов и математических основ кодирования Отделения кибернетики Вычислительного центра им А А Дородницына РАН.

Научный руководитель-

доктор физико-математических наук, профессор Столяров Лев Николаевич

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

доктор физико-математических наук, профессор Цурков Владимир Иванович кандидат физико-математических наук Бершадский Андрей Вячеславович

Ведущая организация

ИнЬтшуг систем энергетики им JIA Мелентьева СО РАН

Защита состоится » ноября 2007 г в часов на заседании диссертационного совета К212 156.02 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл, г Долгопрудный, Институтский пер 9, ауд 903 КПМ.

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

Автореферат разослан « & » октября 2007 г.

Ученый секретарь диссертационного совета К212 156 02 кф -м н

Федько О.С

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Понятие алгебраических сетей (АС) появилось в конце 60-х - начале 70-х годов XX века в работах Э Тыугу АС представлялась набором уравнений, связанных общими переменными В зависимости от различного определения переменных - как аргументов (входные переменные), так и результатов (выходные переменные) - возникали разные задачи, которые решались с помощью АС Необходимость решения таких задач диктовалась сложными инженерными расчетами Например, при проектных расчетах одни переменные были выходными, а при повторных - входными, и требовалось оценить точность расхождения Потребность в АС и генерируемых с их помощью вычислительных моделях была так велика, что группа Э Тыугу создала специальный язык «Утопист», в котором использовалась обычная алгебра действительных чисел Вычислительные сети Тыугу в 70-х годах были использованы во многих институтах РАН, в частности в Институте Систем Энергетики СО РАН

В 80-х годах в своих работах по теории моделей Ч Чен предложил использовать идею Э Тыугу в других алгебраических системах с нечисловыми алгебрами, работающими с объектами немеханической природы

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

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

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

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

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

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

Апробация работы Результаты диссертации докладывались на следующих научных конференциях и семинарах XLII научной конференции Московского физико-технического института (гДолгопрудный, 1999 г), Байкальских всероссийских конференциях с международным участием «Информационные технологии в энергетике, экономике, экологии», «Информационные и математические технологии в науке и управлении» (г Иркутск, 2003, 2007 гг ), Всероссийской конференции с международным участием «Методы современной науки Моделирование сложных систем» (гКиров, 2006 г), XXXIV международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, г Гурзуф, 2007 г), научных семинарах отдела теории алгоритмов и математических основ кодирования Отделения кибернетики Вычислительного центра им. А А Дородницына РАН (г Москва, 2003-2007 гг)

Результаты работы были использованы в следующих проектах РФФИ № 03-07-90356, «Исследование моделей ситуационной комнаты, управляемой событиями, которые передаются через Internet», 2003-2005 гг, № 06-07-89076,

«Модели асинхронного управления распределенными процессами в реальном времени, использующие распознающие сети с памятью», 2005-2007 гг

Публикации По теме диссертации опубликовано 11 работ, в том числе одна в издании из списка, рекомендованного ВАК РФ Структура диссертации

Диссертация состоит из введения, шести глав, заключения и библиографии Объем диссертации - 102 страницы Список использованных источников содержит 38 наименований В работу включены 75 рисунков и таблиц

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Вычислительная сеть Э. Тыугу. Понятие вычислительной сети впервые появилось в работе Э Тыугу «Концешуальное программирование» и, по существу, использует понятие АБ с обычной алгеброй для операций «+», «-», «*», «/» В качестве предикатов выступают обычные алгебраические выражения, задающие отношения из различных предметных областей Алгебраическая сеть Э Тыугу представляется в виде неориентированного графа с вершинами двух типов- переменными и выражениями, связывающими эти переменные Если переменная входит в отношение, то соответствующие вершины соединяются дугой На алгебраических сетях можно решать задачи следующего вида, задав значения одних переменных в сети, построить путь вычисления других переменных Решение задачи - суть процесс расстановки стрелок на графе, определяющих порядок вычисления одних переменных через другие. Алгебраическая сеть с расставленными стрелками называется вычислительной алгебраической сетью На рис 1 1 и рис 2 1 приведены иллюстрирующие примеры

Рис 1 I Правильная расстановка стрелок в вычислительной сети для задачи: «вычислить по (х=2, у=3)»

и!Х+у + г = 5 и2 у + г+ц/ = 3

О] х+у + г = 5 II2 у + г + у» = 3 и3 х + г + и'=3

Рис 2 1 Неправильная расстановка стрелок Неоднозначный вывод переменная м> - вычислима двумя разными способами

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

Вычислительные сети Тыугу нашли широкое применение при инженерных расчетах сложных конструкций, а в последнее время при аудите финансовых потоков в сложных экономических объектах Для вычислений на алгебраических сетях Тыугу был сделан язык «Утопист», где проверка выводимости (вычислимости) была реализована автоматически Алгебраические вычислительные сети с циклической структурой. Вычислительные сети, описывающие решения практических задач, часто имеют циклическую структуру На рисЗ 1,3 2 показано, как для АС при расстановке стрелок возникает циклическая структура, и как в этом случае перейти к вычислительной модели

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

Повторяющийся фрагмент

Рис.3 2 Циклическая структура, развернутая в бесконечную сеть с повторяющимся фрагментом вычислений

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

Во второй главе рассматриваются асинхронные алгебраические сети

для моделирования взаимодействия независимых процессов и проведения асинхронных вычислений Пусть заданы два независимых процесса, которые определяются каждый своей системой уравнений, представленной в виде алгебраической сети Каждый процесс имеет собственный процессор, в котором разворачивается одна из возможных вычислительных моделей, определенная на АС Каждая элементарная функция имеет физическую длительность выполнения Процессы связаны поставками общих переменных, понятно, что без этих поставок они должны остановить свое движение Такие процессы называются асинхронными Они синхронизируются только общими поставками информации, ожидают этих поставок и продолжают свою работу в момент получения информации от другого процесса Существует несколько моделей, описывающих такое взаимодействие Наиболее известные из них 1) взаимодействие последовательных процессов Хоара, 2) сети Петри и их модификация - Joiner - сеть В дальнейшем для описания взаимодействия процессов, будь они физическими, социальными, политическими или бизнес-процессами, будем всегда использовать сети Петри

Рассмотрим пример асинхронной алгебраической сети Существует два процесса П] и П2 Процесс П] описывается уравнениями и Л3 с

переменными 1,2,3,5 Процесс П2 описывается уравнениями Я5 и Яв с переменными 4,5,6,2 Через Э2, 03, , Об обозначим действия вычисления функций вычислительной модели Каждое действие имеет определенную длительность выполнения Длительности действий фиксированы Э2 = 3, Э3 = 3, 05 = 3, Б6 = 2 Алгебраическая сеть для данного примера показана на рис 1 2

Рис 1.2 Алгебраическая сеть для постановки задач

Формулируются следующие две задачи Задача №1 известны <1, 4> вычислить <3, 6>, при этом действия Б2 и 05 начинаются произвольно Задача №2 известны <1, 3, 6> вычислить <4>, действия Б2, Б3, Бб могут начинаться произвольно Для каждой задачи необходимо построить диаграмму Ганта ее решения На рис 2 2а показана вычислительная модель для задачи №1, на рис 2 26 для задачи №2

а)

4*

5

5

4

Рис 22 а) Вычислительная модель для задачи №1- «известны <1,4> вычислить <3,6>»

б) Вычислительная модель для задачи №2 «известны <1,3,6> -> вычислить <4>»

На рис 3 2а и 3 26 для задач №1 и №2 показаны сети Петри с соответствующими начальными условиями Переходы в сети соответствуют действиям процессоров, события означают окончание действий и обозначаются буквой ф с соответствующим индексом, * - отмечаются входные события

Рис 3 2 Модели взаимодействия процессов в задачах №1 и №2 а) Сеть Петри для задачи №1 б) Сеть Петри для задачи №2

На рис 4 2 показаны диаграммы Ганта (ДГ) возможных решений задач №1 и №2.

Ф2 Фг& Фг ф3 Ф^02=3 Ф2 ф2&фз;з.3 Фз

t_* * 3 * I_*

^*05=3 4,5 0 2 ф6* 06=2 Фбп=3 Ф5

I I Т , I Т 6,2 Г , , , ■ , I ■ 1, ■3 I ,

ф2&ф5 ф2&ф6* Фб

Рис 4.2 Диаграммы Ганта различных задач, построенных на одной АС а) ДГ для решения задачи №1, б) ДГ для решения задачи №2.

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

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

В третьей главе вводится понятие рассуждающей сети RN (Reasoning net) Идея такой сети была выдвинута Ч Ченом для поиска сущностей в семантической сети, но так и не была реализована Рассуждающая сеть определяется следующим образом. RN = <Х, R >, где X = {x,jc2, л} булевские переменные, R = {RbR2,R3 ,Rk} - множество предикатов, каждый из которых определен в пространстве X Предикаты R могут быть заданы в виде булевской формулы В(хь. ,х„), таблицы истинности, или в виде диаграммы Вейча, или карт Карно, либо покрытий на гиперкубе X

Рассмотрим пример рассуждающей сети, представленной на рис.1 3 На рис 1 За показана, так называемая, предикативная сеть из трех предикатов Rb R2, R3 и связывающих их четырех переменных х, у, w Предикативные сети являются аналогом алгебраических сетей в дискретном пространстве

Рис 1 3 Рассуждающая сеть а) Предикативная сеть б) Вычислительная сеть На рис 1 36 показана вычислительная сеть, полученная расстановкой стрелок так, что она представляет собой некоторую вычислительную модель из двух функций связанных переменными, как это показано на рис 2 3

Рис 2 3 Вычислительная модель или рассуждающая сеть На рис 3 3 показана таблица истинности для предикатов Я1 = 112 и соответствующие функции

X У г

0 0 1

0 1 0

1 0 0

1 1 0

в) У)= Щу, г)

У г и>

0 0 0

0 1 0

1 0 0У 1

1 1

На наборе (1,0) - возможны два значения -неоднозначность На наборе (1,1) - функция не определена

Рис 3 3 а) Вид предикатов Ш= Я2 б,в) Рассуждающие функции

Сделаем важное замечание функция может определяться не обязательно на всех наборах аргументов Так, например, на рис 3 3 функции определены на двух аргументах из трех Полученные функции могут содержать противоречивые наборы (на одних и тех же наборах аргументов иметь

Для рефлексивной рассуждающей сети для всех возможных вариантов (вычислительных задач) определим правила принятия решений П и Т по изменению маршрута, как показано на рис 3 4

Правила рассуждений для пограничников П

1 ((Я = Р)*(Т- Г)), ->■ (Я = Г)м Если П идут по реке (Я = Р), а Т по горам (Г = Г), то П пойдут в горы за Т (П = Г) П всегда следуют за Т

2 ((Я - Г)»(Т= Г)), —(Я = Г)м 3. ((Я = Г) • (Г = Р))г (Я = Р)м 4 ((Л = Р)»(Г = Р)),-*(Л = Р)М Правила рассуждений для террористов Т

1 («Г = Г) • (Я = Г)), -> (Я = Г)м) -> (Г = Р)м Если П идут по горам и Т идут по горам, то П будут продолжать идти по горам, поэтому Т пойдут по реке

2 («Г = Р). (Я = Г)), -> (Я = Г)м )->(Т = Р)м

3 (((Г = Г). (Я = />)), (Я = Р)1+1) -> (Г = Г)„

4 (((Г = Р)»(П = />)), _> (Я = Г)м) -> (Г =

Рис 3 4. Правила рефлексивных рассуждений для П и Т.

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

I-----

уПР* ;

к

Задача № Г Дано

УТР* = 3, уТГ* = 2 , уЯГ*=3,

уЯР*=2,

<?"„* = О,

Г„* = Г,

х* = (3,5,7),

Найти

¡Тк, гЯк - 7

Рис 4 4 Рассуждающая рефлексивная сеть для задачи №1

На рис 5 4 показана диаграмма Ганта для задачи №1 и результат ее решения

П = Ц

П=Р Т=Г Т=Р ■

: г* = (3,5,7) -

последовательность ; времени ' обнаружения

тк=ю

#1=8

О 3 5 7 8 10 х, сутки

Рис.5 4 Диаграмма Ганта для задачи №1

Вариант постановки другой задачи (задача №2) и ее решение показаны на рис.6 4

Задача №2

Т

к

Рис 6 4 Рассуждающая сеть для задачи №2 «Пограничники против террористов»

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

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

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

Каждая функция может быть интерпретирована как некоторое рассуждение.

если х • у = истина, то г = истина Из \У если у : = истина , то п> = истина

дополнена значением м> = истина, а семантика задачи такова, что может быть выбрано № = ложь для строки у = истина и г = ложь Для задачи на рис 2 3 будет записано такое рассуждение ((х • у) • >>) = ложь При любых значениях х и у переменная ш принимает значение «ложь»

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

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

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

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

Т, Я, Т„, 7'„, Я„, Як е {Г- горная тропа, Р -тропа вдоль реки}

/Я„, /Г„, 1ТК -время старта и окончания операции для П и Т соответственно Ян, Як, Гн, Тк- начальные и конечные значения переменных для П и Т соответственно vTP,vTГ, уПРуПГ- скорости движения П и Т вдоль реки (Р) и по горам (Г) соответственно

VПР

уТГ чТР

Ят- уравнения в виде правил для террористов

уравнения в виде правил для пограничников

Рис 1 4 Алгебраическая сеть для задачи «Террористы против пограничников»

Рефлексивная модель рассуждений Лефевра выглядит так, как показано на рис 2 4

б)

Рассуждение П о Т является фантомом Т

Рис 2 4 Рефлексивная модель рассуждений Лефевра а) Для пограничников П. б)Для террористов Т

2. Теорема о нахождении (выделении) дерева вывода функции (выходной переменной) По своей сути она позволяет определить возможность решения задачи х — X {у у ,и>к), где х - выходная переменная (результат), (у*ь • ,у*„) - входные переменные (заданные), (м>ъ ,м>щ - промежуточные переменные

3 Теорема о неоднозначности выходной переменной х и промежуточной переменной ч>1=(м>и ,м<к)

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

В шестой главе представлены модели применения алгебраических сетей для решения конкретных практических задач

1.Модель бизнес-процесса, основанного на рефлексивном менеджменте.

Рассматривается рефлексивное управление рынком на примере менеджмента, который использовал на автомобильном рынке Ли Якокка (пример взят из книги Ли Якокка «Карьера менеджера») Ли Якокка был первым, кто применил рефлексивные способы управления рынком При принятии решений он учитывал не только текущее состояние рынка и своей организации, но и возможные действия других производителей и их влияние на рынок Такой подход позволял Ли Якокке всегда бьггь на шаг впереди конкурентов

На рис 1 6 представлена рефлексивная модель управления производством (схема Лефевра), которую держит в голове Ли Якокка

РР - Представление (модель) Ли Якокки о собственном производстве

РРС - Представление Ли Якокки о поведении рынка продажи собственных автомобилей фирмы И - «Форд» РН - Представление Ли Якокки о производстве фирмы Н — «Шевроле»

ЬНС - Представление (модель) Ли Якокки о представлении фирмой Н поведения рынка продажи собственных автомобилей

У' ч

Рис 1 6 Рефлексивная модель управления производством в голове Ли Якокки На рис 2 6 показана продукгово-информационная модель производства и продажи автомобилей фирмами «Р» и «Н»

F Н

F Н

----тЫ -а--.

CF

рынок

сн

F, Н -модели предприятий «Форд» и «Шевроле»

CF,CH - модели рынка продажи автомобилей «Форд» и «Шевроле» f, h 6 {(0,0),(0,1),(1,0),(1,1)} -векторы событий изменения цены и характеристик автомобиля cf, ch е {Т - продажи увеличились, 4- - продажи уменьшились}

Рис 2 6 Продуктово-информационная модель производства и продажи автомобилей фирмами «Б» и «Н»

Переменные £, И принадлежат множеству {(0,0),(0,1),(1,0),(1,1)}, элементы которого - упорядоченные пары, где первая компонента отвечает за событие изменения цены, а вторая - за изменения характеристик выпускаемого автомобиля Например, £ = (01)( означает, что «Форд» улучшил

характеристики выпускаемого автомобиля по сравнению с М, но цена осталась прежней, Ь,=(10) означает, что «Шевроле» увеличил цену, оставив неизменными характеристики автомобиля Переменные с!-, сЬ отражают реакцию рынка Взаимосвязь переменных и моделей представлена на рис 3 6 в виде алгебраической (вычислительной) сети АС.

Рис 3 6 Алгебраическая сеть для моделирования бизнес-процессов

Рис 4 6 Решение классической задачи управления Ли Якокки

Классическая задача управления Ли -Якокки - выбрать для производства в момент времени 1+1 такой тип автомобиля , который, в зависимости от поведения рынка и других производителей, удовлетворяет некоторому критерию оптимальности Решение этой задачи показано на рис 4 6 По поводу критерия оптимальности можно сказать следующее Он есть, на его основе принимается решение, которое отражается в правилах, но конкретный вид не приводится, тем более, что в различные моменты времени существования критерии были разными в зависимости от поведения рынка

Вычислительная модель для решения данной задачи приведена на рис 5 6

Рис 5 6 Вычислительная модель для задачи Ли Якокки

Функции для вычислительной модели Ли Якокка определяет следующим

образом

1) ФСР — модель поведения покупателей автомобилей марки «Б» с точки зрения Ли Якокки Рис 6 6.

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

2) ФН - модель поведения покупателей марки «Н» с точки зрения Н в представлении Ли Якокки. Рис 7.6

3) Ф1Ш — модель поведения производителя марки «Н» в представлении Ли Якокки Рис 8 6

4) ФР - модель принятия решений Ли Якоккой о выпуске автомобиля марки «Р» в зависимости от поведения конкурента «Н» и рынка сбыта Функция задается машиной состояний, где И.}, К.2, К< — конкретные рассуждения Рис 9 6

ЛЬ 00 ох 10 IX

00 * * т т

ох Т * т т ь 00 ОХ ХО XX

10 * сЬ т Т 1 4-

XI 1 4- т *

Рис 6 6. Функция с£ = = ФСР (4 Ь,) Рис 7 6 Функция сИ, = ФН (Ь,)

„ 01 Яз

ь, 00 01 хо IX 004. N А,1 "

сИ( Т 00 10 00 00 /

1 11 * 11 * 10 ^

я»

Рис.8 6 Функция Ь 1+1= ФЯНф 1, сЬО Рис 9 6 Машина состояний, задающая

функцию £+1=ФР (^„с^сЬ,,^,)

На основании вычислительной модели строится событийная сеть Петри (рис 10 6), где <р6 <рь , <рсЬ фсГ - события изменения переменных £ Ь, с£ сЬ соответственно. Заметим, что сеть Петри в данном примере бесконечна, т к функционирует всегда

Рис 10 6 Событийная сеть Петри для задачи менеджмента Ли Якокки.

На рис 116 показан пример расписания последовательности выполнения действий (диаграмма Ганта) процессорами в событийной сети. План действий для процессора «Р» - план работ для организации «Форд» Остальные процессоры - «живут» только в голове Ли Якокки Хотя их поведение является

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

СР |

сн

Рис 116 Пример диаграммы Ганта выполнения действий процессорами принятия решений в событийной сети

2. Моделирование операции «Буря в пустыне» (война между США и Ираком 1990 г) В этой модели учитывали принцип рефлексивного управления, который использовал генерал Шварцкопф, т н «Ловушка Шварцкопфа», когда он заставил Хусейна принять решение отвести войска к Персидскому заливу, специально демонстрируя Хусейну «трюки» с передвижением американских войск

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

В заключении сформулированы основные результаты диссертационной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

1 ПА Старостин Модели кризисных ситуаций в производстве ГГ-продуктов // Труды Всероссийской конференции "Математические и информационные технологии в энергетике, экономике, экологии" /ИСЭМ СО РАН -Иркутск, 2003 -С 90-98

2 ПА Старостин Визуальное ситуационное пространство для планирования работ со случайным внешним потоком заданий // Моделирование процессов управления Сб научных трудов / Моек физ -тех ин-т -М, 2004.

-С 174-182

3 ПА Старостин Моделирование боевых операций с помощью рассуждающих сетей Петри (на примере операции «Буря в пустыне») //Труды института системного анализа РАН Динамика неоднородных систем Выпуск 10(02) /- М • КомКнига, 2006 -С 414-419

4 ПА Старостин Рассуждающие сети для бизнес-процессов //Методология современной науки Моделирование сложных систем Тезисы докладов международной научной конференции / ВятГУ -Киров, 2006. -С 79

5 ЛН Столяров, ПА Старостин Рассуждающие сети, моделирующие психологию участников корпоративных решений // Моделирование процессов обработки информации Сб научных трудов

/Моек физ-тех ин-т -М, 2007-С 100-109

6 ПА Старостин Рассуждающие сети Петри для моделирования боевых операций // Моделирование процессов обработки Информации Сб научных трудов /Моек физ-тех ин-т -М,2007 -С77-91

7 ПА Старостин Моделирование рефлексивного управления на примере боевых операций //Труды XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении» / ИСЭМ СО РАН - Иркутск, 2007 - Часть 3 - С 158-151

8 ПА Старостин Сетевые модели принятия корпоративных решений, учитывающих психологию участников // Труды XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении» / ИСЭМ СО РАН - Иркутск, 2007 -Часть 3-С 161-170

9 Л Н Столяров, П А Старостин Анализ взаимосвязи логических рассуждений членов правительства // Информационные технологии в науке, социологии, экономике и бизнесе Приложение к журналу «Открытое образование» XXXIV международная конференция 1Т+8Е'07 / МЭСИ -М, 2007 -С 139-141.

10. Л Н Столяров, П А Старостин Логическая модель рассуждений Шварцкопфа в операции «Буря в пустыне» // Информационные технологии в науке, социологии, экономике и бизнесе Приложение к журналу «Открытое образование» XXXIV международная конференция ¡Т+БЕ'О? /МЭСИ-М., 2007.-С 141-143

11. Л Н Столяров, П А Старостин Рефлексивный менеджмент Ли Якокки // Информационные технологии в науке, социологии, экономике и бизнесе Приложение к журналу «Открытое образование» XXXIV международная конференция ГГ+БЕ'ОТ / МЭСИ.-М , 2007 -С 143-145

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25 09 2000 г. Подписано в печать 14 09 07 Тираж 70 экз Уел пл 1,5 Печать авторефератов (495) 730-47-74,778-45-60

ВВЕДЕНИЕ.

ГЛАВА 1. ВВЕДЕНИЕ В АЛГЕБРАИЧЕСКИЕ СЕТИ.

1.1 .Вычислительные сети Тыугу.

1.2.Поведенческие модели.

1.3.Сетевые модели с бинарными отношениями, заданными на одинаковых конечных алфавитах.

1 Асемантические сети Ван-Хао.

ГЛАВА 2. АСИНХРОННЫЕ АЛГЕБРАИЧЕСКИЕ СЕТИ.

ГЛАВА 3. РАССУЖДАЮЩИЕ СЕТИ (REASONING NET).

ГЛАВА 4. РЕФЛЕКСИВНЫЕ РАССУЖДАЮЩИЕ СЕТИ.

4.1.Теория и семантика рефлексивных систем Лефевра. Полиномы Лефевра.

4.2.Семантика RRN.

4.3.Структура взаимодействия процессов, реализующих «фантом» Лефевра.

4.4.Модели взаимодействия процессов.

4.5.Алгебраические RRN.

4.6.Пример рефлексивной рассуждающей сети.

ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГЕБРАИЧЕСКИХ СЕТЕЙ.

5.1.Основные определения теории алгебраических сетей.

5.2.Алгебра абстрактной вычислительной машины (АВМ) и формулы АВМ.

5.3.Теорема о нахождении (выделении) дерева вывода функции выходной переменной.

5.4.Критерий противоречивости и разрешимости задачи, поставленной на AN.

5.5.Рекурсивная (циклическая) АВМ.

5.6.Интерпретированные АВМ. Основанная теорема AN.

5.7.Представление вычислительной модели в виде ярусно-параллельной формы.

ГЛАВА 6. ПРИМЕНЕНИЕ АЛГЕБРАИЧЕСКИХ СЕТЕЙ ДЛЯ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ.

6.1. Моделирование рассуждений членов правительства, решающих единую задачу.

6.2. Модель бизнес-процесса, основанного на рефлексивном менеджменте.

6.3 .Моделирование операции «Буря в пустыне».

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

6.5.Моделирование операции «Террористы против пограничников».

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

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

В работе рассмотрены следующие алгебраические сетевые модели:

1) вычислительные сети Э.Тыугу;

2) поведенческие модели;

3) рассуждающие сети (RN);

4) рефлексивные рассуждающие сети (RRN);

5) алгебраические сети на конечных множествах.

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

Научная новизна работы.

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

1) класс рассуждающих сетей, позволяющих моделировать параллельные процессы рассуждений нескольких субъектов;

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

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

Логика построения работы и ее краткое содержание.

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

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

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

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

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

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

Основные результаты работы:

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

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

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

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

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

Заключение

1. Айзерман М.А. и др. Логика.Автоматы.Алгоритмы. -М.,Физматгиз, 1963.-556 с.

2. Ахо А.,Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

3. Гросс М.,Лантен А. Теория формальных грамматик.- М.: Мир,1971.-295 с.

4. Закрееский АД. Логические уравнения.-М.: Едиториал УРСС,2003.-96 с.

5. Закрееский АД. Логика распознавания.- М.: Едиториал УРСС, 2003.-144 с.

6. Клини С.К. Представление событий в нервных сетях и конечных автоматах. -М.: ИЛ, 1956.

7. Клаузевиц К. О войне. М.: Госвоениздат, 1934.

8. Крамер К.Х., Крайзер Т.Е. От предсказаний к рефлексивному управлению. Международный научно-практический журнал «Рефлексивные процессы и управление». №2 июль-декабрь, 2003, том 3.

9. Котов В.Е., Сабельфелъд В.К. Теория схем программ. М.: Наука, 1991.-248 с.

10. Ю.ЛефеврВ.А. Конфликтующие структуры. М.: Советское радио,1973.-158 с.

11. МЛефеврВ.А. Алгебра Совести. М.: Когнито-центр, 2003.

12. Мальцев А.И. Алгебраические системы. -М.: Наука, 1970.-392.

13. Ъ.Минский М. Структура для представления знания // Психология машинного зрения. М.: Мир, 1978. - С. 249-338.

14. Новиков ДА., Чхарташвили А.Г. Рефлексивные игры.-М.: СИНТЕГ, 2003. -160 с.

15. Новиков Ф.А. Дискретная математика для программистов.-СПб: Питер,2000. -304 с.1 б.Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.

16. М.Старостин П.А. Модели кризисных ситуаций в производстве IT-продуктов. // Труды Всероссийской конференции "Математические и информационные технологии в энергетике, экономике, экологии". /ИСЭМ СО РАН. -Иркутск, 2003. С. 90-98.

17. Старостин П.А. Визуальное ситуационное пространство для планирования работ со случайным внешним потоком заданий. // Моделирование процессов управления. Сб. научных трудов. / Моск. физ.-тех. ин-т. -М., 2004. -С. 174-182.

18. Старостин П.А. Моделирование боевых операций с помощью рассуждающих сетей Петри (на примере операции «Буря в пустыне»). //Труды института системного анализа РАН. Динамика неоднородных систем. Выпуск 10(02). /- М.: КомКнига, 2006. -С.414-419.

19. Старостин П.А. Рассуждающие сети для бизнес-процессов.

20. И.Старостин П.А. Рассуждающие сети Петри для моделирования боевых операций. // Моделирование процессов обработки информации. Сб. научных трудов. / Моск. физ-тех. ин-т. -М., 2007. С.77-91.

21. Старостин П.А. Моделирование рефлексивного управления на примере боевых операций. //Труды XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении». / ИСЭМ СО РАН. Иркутск, 2007. - Часть 3 - С. 158151.

22. ТахаХ.А. Введение в исследование операции. М.: Вильяме,2001.-612 с.

23. Тыугу Э.Х. Концептуальное программирование. -М.: Наука, 1984.-256 с.

24. ЪХ.Тыугу Э.Х. Решение задач на вычислительных моделях.- ЖВМ и МФ,т. 10, №5,1970.

25. Фридл Дж. Регулярные выражения. Библиотека программиста. -СПб. Литер, 2001.-352 с.

26. УЬХоар Ч. «Взаимодействующие последовательные процессы». -М.: Мир, 1983.-264 с.

27. ЗА.Чхарташвши А.Г. Теоретико-игровые модели информационного управления. -М.: ПМСОФТ, 2004. -227 с.

28. Чен Ч.Ч. Теория моделей. -М.:Мир, 1977. 616 с.3e.Shubert and Kraus. The Wirlwind War Center of Military History. Washington.-1995.

29. Petri C.A. Concepts of Net Theory // Mathematical Foundations, of Computer Science: Proc. Of Symposium and Summer School / Mathematical Institute of the Slovak Academy of Sciences. 1973.

30. ЪЪ.Petri C.A. Kommunication mit Automaten. Schriften fur des Rheinich-Westfalischen Inst. Fur Instrumentalle Mathematik. Univ. Bonn. - Bonn, 1962.