Новости
Новости ИСП РАН
Научный семинар по системному программированию под руководством Аветисяна А.И.
21 марта 2018 г. (в среду) в 17:00 в ИСП РАН (ауд. 110) состоится научный семинар по системному программированию под руководством Аветисяна А.И.
Докладчик: Шершаков Сергей Андреевич, соискатель ученой степени кандидата тех. наук по специальности: 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей». ЛПОИС ФКН НИУ ВШЭ.
Тема работы: «Методы и инструменты повышения эффективности алгоритмов Process Mining».
Руководитель: проф., д.ф.-м.н. И. А. Ломазова.
В докладе будут представлены результаты исследования, которое проводилось автором в лаборатории ПОИС ФКН НИУ ВШЭ в последние годы. Данная работа относится к области process mining, основными задачами которой являются синтез моделей процессов и проверка соответствия моделей процессов их реальному поведению на основании информации, хранящейся в журналах событий.
Основные проблемы при решении этих задач – большие объемы обрабатываемых данных и экспоненциальная сложность основных алгоритмов. В частности, наиболее теоретически обоснованный метод синтеза, базирующийся на теории регионов, использует построение системы переходов в качестве промежуточного шага. Задача синтеза результирующей модели – сети Петри – по системе переходов является NP-полной. Поэтому на практике метод регионов оказывается применим только для небольших по размеру систем переходов.
Данная работа посвящена повышению эффективности существующих решений в двух направлениях. Во-первых, разработан алгоритм редукции системы переходов, который позволил уменьшить размер системы переходов при сохранении приемлемого уровня ее точности. Во-вторых, разработаны архитектура и принципы реализации программных средств для эффективной работы с журналами событий больших размеров, на основе которых реализованы библиотека и программный инструмент для решения задач и автоматизации экспериментов в области process mining. Это позволило получить существенное сокращение по потребляемым ресурсам (времени выполнения алгоритмов и занимаемой памяти) по сравнению с известными решениями, что подтверждается экспериментами на реальных данных.