Автоматическая верификация и оптимизация потоков работ

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

Оглавление.
Введение.

Актуальность темы.

Цель и задачи работы

Основные результаты работы

Научная новизна работы

Практическая значимость.

Доклады и печатные публикации.

Структура и объем диссертации.

Краткое содержание работы.

Глава 1 Потоки работ, двустороннее отображение между формулами потоков работ и их графовым представлением
1.1 Обзор языков описания потоков работ, системы управления потоками работ
1.2 Промежуточные представления потоков работ
1.2.1 Размеченные фафы анализа потоков работ
1.2.2 Формальный язык описания потоков работ
1.2.3 Сети потоков работ
1.2.4 Графы потоков работ.
1.2.5 Выразительные возможности промежуточных представлений потока
1.3 Двустороннее отображение между Формальным языком описания потоков работ и Размеченными графами анализа потоков работ
1.3.1 Алгоритм построения Размеченного графа анализа потока работ по
Формальному описанию потока работ.
1.3.2 Алгоритм построения Формального описания потока работ по
Размеченному графу анализа потока работ
1.4 Выводы.
Глава 2 Алгоритмы анализа и преобразования потоков работ.
2.1 Алгоритм верификации Размеченных графов анализа потоков работ, сопоставление с другими известными алгоритмами верификации потоков работ.
2.1.1 Структурные конфликты и алгоритмы верификации потоков работ
2.1.2 Алгоритм булевой верификации АБВ потоков работ.
2.1.2.1 Структурные конфликты в Размеченных графах анализа потоков работ без ориентированных циклов.
2.1.2.2 Алгоритм булевой верификации потоков работ АБВ для графов без ориентированных циклов.
2.1.2.3 Вычислительная сложность Алгоритма булевой верификации АБВ потоков работ для графов без ориентированных циклов
2.1.2.4 Алгоритм булевой верификации потоков работ АБВ для рафов с ориентированных циклами
2.1.2.5 Сравнение АБВ с другими алгоритмами верификации потоков работ.
2.2 Алгоритм структурной оптимизации потоков работ
2.2.1 Алгоритм структурной оптимизации Размеченных графов анализа потоков работ.
2.2.2 Вычислительная сложность алгоритма структурной оптимизации Размеченных графов анализа потоков работ.
2.2.3 Получение Формального описания потока работ по оптимизированному Размеченному графу анализа потока работ
2.3 Обоснование алгоритмов верификации и оптимизации потоков работ
2.3.1 Обоснование алгоритма булевой верификации АБВ для графов без ориентированных циклов.
2.3.2 Обоснование алгоритма структурной оптимизации Размеченных графов анализа потоков работ
2.4 Выводы.
Глава 3 Применение алгоритмов верификации и оптимизации потоков работ
3.1 Преобразование процессов в Формальное описание потоков работ
3.1.1 Xпредставление Формального языка описания потоков работ
3.1.2 Основные конструкции языка
3.1.3 Преобразование процесса в Формальное описание потока работ
3.1.4 Получение процесса по Формальному описанию потока работ
3.2 Реализация и применение алгоритмов анализа потоков работ.
3.2.1 Система автоматической верификации и оптимизации потоков работ.
3.2.2 Система управления электронной библиотекой Научное наследие России
3.2.3 Анализ процесса удаления книги в Электронной библиотеке Научное Наследие России.
3.3 Выводы.
Заключение.
Литература


Следует отметить, что не существует одного общего стандарта для описания потоков работ, существуют методы и средства, использующие различные языки моделирования и терминологию. Для более полного представления о разнообразии базовых концепций моделирования потоков работ рассмотрим наиболее известные стандарты и методы описания потоков работ. Метод i i i создан еще в г и поддерживается Министерством обороны США, которое было инициатором разработки семейства стандартов I I iii . Этот метод реализован в одном из стандартов этого семейства I0, который был утвержден в качестве федерального стандарта США в г. Базовым элементом описания является функциональный блок, описывающий конкретную функцию в рамках моделируемого потока работ Рис. Рабочий Петров И. Рисунок 1. Необходимые для выполнения функции данные, а так же результаты ее работы обозначены интерфейсными дугами стрелками. Левая стрелка представляет собой входной поток данных, а правая выходной. Верхняя стрелка обозначает управляющее воздействие, нижняя необходимые для выполнения функции ресурсы. В описании этой методологии указано, что все диаграммы модели БЛЭТ взаимосвязаны и организованы в иерархию. Вершина иерархии представляет систему в целом, это самое общее определение системы, а листья самые детализированные. После формирования модели системы в целом проводится разбиение ее на крупные фрагменты. Этот процесс называется функциональной декомпозицией, а диаграммы, которые представляют каждый фрагмент и взаимодействие фрагментов, называются диаграммами декомпозиции. После декомпозиции контекстной диаграммы проводится декомпозиция каждого большого фрагмента системы на более мелкие и так далее до достижения нужного уровня подробности описания Рис. Рисунок 1. В конце х годов был разработан метод моделирования ГОЕРЗ, являющийся частью семейства стандартов ШЕР. Предполагалось использование этого метода для ВВС США. После его появления стало возможным моделировать последовательность действий в рамках некоторого процесса на основе методологии БАОТ. Основой модели ШЕРЗ служит так называемый сценарий процесса, который выделяет последовательность действий и подпроцессов анализируемой системы. Главной единицей модели ШЕРЗ является диаграмма Рис. Рисунок 1. Другой важный компонент модели действие, или в терминах I3 единица работы. Каждое действие имеет идентификатор, между действиями существуют связи однонаправленные стрелки, один из возможных типов связей это временное предшествование. Также для описания потоков работ используется подход моделирования потоков данных. Диаграммы потоков данных i представляют собой иерархию процессов, которые связаны между собой потоками данных. Эти диаграммы показывают, как обрабатывает информацию каждый процесс, как процессы связаны друг с другом, а также как работает сама система, каким образом она обрабатывает поступающие данные Рис. Рисунок 1. Диаграммы деятельности ii i ivi i отражают эволюцию технологий моделирования потоков работ в сторону более подробного описания потока управления. Именно хорошо описанный поток управления позволяет обеспечить автоматизированное выполнение потока работ. Диаграмма деятельности представляет набор действий, связанных между собой стрелками. При выполнении действий поток работ проходит через ряд состояний. При
i
этом поток работ имеет точки входа и точки завершения. Могут встречаться конструкции условного ветвления, параллельного запуска ветвей потока работ с последующей синхронизацией. Диаграмма деятельности иМЬ позволяет определять роли участников потока работ с помощью элементов описания плавательная дорожка. На рисунке 1. УМЬ. Рисунок 1. В настоящее время наиболее распространенным графическим стандартом описания потоков работ является нотация i i , которая впервые была предложена в году, она включила в себя все основные конструкции известных ранее графических стандартов описания потоков работ, таких как ivi i, I и других. Графическое представление производственного процесса имеет свои преимущества оно понятно всем участникам процесса, также по графическому описанию может быть автоматически построен исполняемый поток работ. Нотация 2.