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

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

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

Понятия и определения Дискретная система – такая система, у которой дискретны множества внутренних состояний, входных и выходных сигналов, а также множество моментов времени, в которые поступают входные сигналы, меняются внутренние состояния и выдаются выходные сигналы. Вероятностный конечный автомат – это такой конечный автомат, для которого функции переходов и функции выходов соответственно принимают вид δ : A × Z × p A и λ : A × Z × p W, где случайная величина, определяющая переход.

Понятия и определения (продолжение) Сеть вероятностных автоматов – это шестёрка Z – входной алфавит {S i = (A i, Z i, δ i )}, 1 i n – множество компонентных автоматов сети W – выходной алфавит сети {f i }– множество функций соединения компонентных автоматов сети. { ψ i } – множество входных функций. g – выходная функция сети.

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

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

Множество ортогональных разбиений. Множество ортогональных разбиений – это множество разбиений, при перемножении которых получается тривиальное разбиение. Пример p 1 ={a 1, a 2 ; a 3, a 4, a 5, a 6 } p 2 ={a 1, a 2, a 3 ; a 4, a 5, a 6 } p 3 ={a 3, a 6 ; a 2, a 5 ; a 1, a 4 } При перемножении данных разбиений получается тривиальное разбиение {a 1 ; a 2 ; a 3 ; a 4 ; a 5 ; a 6 }

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

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

Вспомогательные окна программы

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

Окно моделирования

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

Заключение (продолжение) Разработанный алгоритм и основные сущности, связанные с предметной областью (вероятностный автомат, сеть и т.п.) были реализованы в виде.NET-библиотеки, что позволяет использовать её в составе программных комплексов, предназначенных для анализа дискретных систем. Также, в ходе исследований, проведённых в рамках данной квалификационной работы, были изучены количественные и качественные характеристики разработанного алгоритма.

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

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