Тезис к статье "ОБ APLLY-ОПЕРАЦИИ УМНОЖЕНИЯ ДЛЯ УБДР ФУНКЦИЙ"

Ибрагимова Сусанна Замировна

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

Изначально УБДР являются графическим представлением булевой функции. Для УБДР имеет место APLLY-операция, которая строит булеву функцию с использованием алгебраических операций функций-аргументов. В работе Е. Лукьяновой, А. Дерезы «Имитационная модель единого ресурса алгоритмических схем» решена задача комбинирования последовательного и параллельного выполнения процессов с использование APLLY-операции при совмещении различных функционирующих схем в один работающий комплекс. Приведено решение конкретной модельной задачи, в которой выполнялось последовательное использование двух комплексов.

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

Для исследований были выбраны две булевы функции и , для каждой из которых было построено дерево решений. Для полученных деревьев решений применены преобразования редукции: склеивание листов-дубликатов, склеивание внутренних вершин дубликатов, исключение лишних тестов, и получены соответствующие редуцированные УБДР. К редуцированным УБДР была применена APLLY-операция умножения, конструирующая функцию :

,

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

Результат выполнения APLLY-операции умножения для УБДР функций и есть следующая результирующая УБДР

На рисунке буквы , , , соответствуют вершинам УБДР соответственно функций и .

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

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

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