Декомпозиция сложных дискретных систем, формализованных в виде вероятностных МП-автоматов. квалификационная работа Выполнил: Шляпенко Д.А., гр. ИУ7-83 Руководитель: Рудаков И.В., к.т.н., доцент

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

Классификация методов декомпозиции дискретных систем В отчётной квалификационной работе рассмотрен объектный метод декомпозиции с помощью вероятностных конечных автоматов. 3

Вероятностный автомат Вероятностный конечный автомат – это такой конечный автомат, для которого функции переходов и функции выходов соответственно принимают вид δ : A × Z × p A и λ : A × Z × p W, где случайная величина, определяющая переход. p [0;1] 4 Вероятностный автомат Входной символ Z Выходной символ W Случайная величина p

Сеть вероятностных конечных автоматов Сеть вероятностных автоматов – это семёрка Z – входной алфавит {Si = (Ai, Zi, δ i)}, 1 i n – множество компонентных автоматов сети W – выходной алфавит сети. {fi}– множество функций соединения компонентных автоматов сети. { ψ i} – множество входных функций. G – выходная функция сети. p – случайная величина, p [0;1]. 5

Алгоритм декомпозиции вероятностных конечных автоматов 6

Множество ортогональных разбиений. Множество ортогональных разбиений – это множество разбиений, при перемножении которых получается тривиальное разбиение. π(0) = {a 1 ; a 2 ; … a n ;} 7

Критерий оценки множества ортогональных разбиений. n - число элементов во множестве ортогональных разбиений, N - число элементов во множестве состояний исходного автомата, bj - количество элементов в j-ом блоке, оцениваемого разбиения, k - количество блоков, оцениваемого разбиения, ki - количество блоков i-ого разбиения. 8

Структура программного комплекса 9

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

Пример табличного задания автомата 11 a1a2a3a4a5a6 z1 (a1, w2) - 0,5(a5, w2) - 0,3(a1, w1) - 0,6(a6, w1) - 1(a1, w3) - 1(a2, w2) - 0,6 (a2, w1) - 0,5(a1, w2) - 0,2(a2, w1) - 0,2 (a1, w2) - 0,1 (a2, w2) - 0,3 (a3, w3) - 0,1 (a4, w3) - 0,1 (a5, w1) - 0,1 z2 (a6, w2) - 1(a1, w1) - 0,2(a5, w3) - 0,8(a2, w2) - 0,8(a1, w1) - 0,3(a6, w2) - 1 (a2, w2) - 0,2(a2, w3) - 0,1 (a2, w2) - 0,7 (a3, w3) - 0,2 (a4, w3) - 0,2 z3 (a6, w1) - 1(a1, w1) - 1(a5, w1) - 0,9(a2, w2) - 0,6(a2, w3) - 0,8(a5, w3) - 0,7 (a6, w1) - 0,1 (a3, w3) - 0,2(a6, w3) - 0,3 z4 (a2, w3) - 1(a5, w3) - 0,7(a1, w1) - 0,5(a6, w3) - 1(a4, w1) - 0,9(a3, w1) - 1 (a6, w2) - 0,3(a2, w2) - 0,5

Главное окно программы 12

Результат декомпозиции 13

Результаты сравнения работы исходного автомата и результирующей сети. 14 Распределения по множеству состояний, полученной в результате декомпозиции сети и исходного автомата при различных последовательностях случайных чисел (слева) – различаются менее чем на 10%; при одинаковых последовательностях случайных чисел (справа) – идентичны;

Экономическая эффективность График чистого дисконтированного дохода Срок окупаемости составляет 5 месяцев 15

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

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

Благодарю за внимание. 18