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

• Автор: Старостин, Петр Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

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

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

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

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

1.4.Семантические сети Ван-Хао

ГЛАВА 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.Моделирование операции «Террористы против пограничников»
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Диссертационная работа посвящена разработке новых математических объектов, названных алгебраическими сетями, и их практическому использованию для широкого круга задач, начиная от задач инженерного проектирования, до задач принятия коллективных решений. Основная научная идея, заложенная в диссертацию, состоит в том, что из системы отношений (либо уравнений), связывающих предметные переменные, можно получить множество вычислительных моделей, решающих различные задачи. Для этих целей вводится абстрактный объект - алгебраическая сеть (АТ4), который представляется графом с двумя типами вершин: вершин отношений (уравнений) и вершин переменных, которые соединены ребрами. Граф содержательно интерпретируется условием: переменные входят (принадлежат) в отношение. Вычислительная модель служит для решения конкретной задачи, которая определяется входными и выходными переменными. АЫ названа алгебраической, т.к. для порождения вычислительных моделей для различных задач используются эквивалентные преобразования, которые определяет соответствующая алгебра. Для этих целей для каждой АИ вводится, сопряженная с ней алгебраическая система (Ав).
В работе построены элементы теории алгебраических сетей, которые с единых позиций рассматривают методику порождения вычислительных моделей для различных алгебраических систем. Основная проблема, которую решает теория - выводимость вычислительной модели из алгебраической сети.
В работе рассмотрены следующие алгебраические сетевые модели:
1) вычислительные сети Э.Тыугу;
2) поведенческие модели;
3) рассуждающие сети (ИМ);
4) рефлексивные рассуждающие сети (МШ);
5) алгебраические сети на конечных множествах.
Актуальность темы. Алгебраические сети могут применяться для моделирования широкого круга задач в различных предметных областях. На алгебраической сети, построенной для конкретной предметной области, можно ставить различные задачи, можно анализировать возможность существования решения задачи до составления алгоритма ее решения, а также, в случае разрешимости задачи, составлять вычислительную модель. Одна алгебраическая сеть может порождать множество вычислительных моделей, решающих различные задачи.
Научная новизна работы.
Научная новизна диссертации заключается в том, что предложен и разработан единый подход математического моделирования сложных
5.6.Интерпретированные АВМ. Основанная теорема АИ.
В предыдущих параграфах мы использовали понятие абстрактной вычислительной модели. Напомним, что вычислительную модель мы назвали абстрактной, так как мы не рассматриваем сами отношения. В этом разделе с абстрактного уровня мы спускаемся на уровень отношений и интерпретируем каждую конкретную элементарную вычислительную модель, как некоторую функцию, вычисляющую выходную переменную.
Определение 8. АВМ называется интерпретированной или просто вычислительной моделью, если каждая входящая в формулу переменная вычисляется при помощи функций, определенных в некоторой алгебраической системе (АБ).
Сформулируем критерий разрешимости для вычислительной модели.
Критерий разрешимости. Задача называется разрешимой, если она имеет разрешимую по входу и выходу АВМ и каждая переменная вычисляется элементарной операцией в некоторой алгебраической системе (АБ).
Определение 9: Система интерпретаций называется полной, если каждой элементарной абстрактной функции, полученной циклическими перестановками переменных, существует элементарная функция, полученная из отношения Я с помощью эквивалентных алгебраических преобразований из АБ.
В самом общем виде АБ задается четверкой АБ = <М, Б, Р, А >, где М - произвольное множество, Б - множество функций на М, Р - множество предикатов первого порядка, задающих различные отношения на множестве М, А - алгебра, имеющая список тождественных преобразований.
Например, алгебраическая система для простых сетей Тыугу АБ = (мн-во действительных чисел, {+,*}, {=}, алгебра определяется полем над действительными числам}. Так как в этой алгебре для всех элементарных функций {+,*} существуют обратные {-, /}, а отношения задаются линейными относительно переменных уравнениями, то любое отношение разрешимо относительно любой переменной в него входящей. Поэтому такая система интерпретаций называется полной.
Алгебраическая система для АВМ - является полной по определению.
Для поведенческих моделей, рассмотренных в главе 1, система интерпретаций является полной, если правила представляют собой т.н. Туэвскую систему продукций.
При переходе от элементарной абстрактной вычислительной модели к ее интерпретации (элементарной вычислительной модели) могут возникнуть следующие проблемы: