Исследование алгебраических сетей, порождающих совокупность вычислительных моделей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Старостин, Петр Александрович

• Старостин, Петр Александрович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Старостин, Петр Александрович

ВВЕДЕНИЕ.

ГЛАВА 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. Рассмотрены примеры решения практических задач, использующих механизмы работы с алгебраическими сетями.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Старостин, Петр Александрович, 2007 год

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.