- •Введение
- •Глава 1. Основные понятия теории моделирования
- •1.1. Классификация видов моделирования
- •1.2. Жизненный цикл компьютерной модели
- •1.3. Вычислительный эксперимент
- •1.4. Наиболее известные методологии и системы компьютерного моделирования
- •1.4.1. Универсальные системы моделирования
- •1.4.2.Системы моделирования бизнес-процессов
- •1.5. О моделировании вычислительных систем
- •Глава 2. Введение в сети Петри
- •2.1. Обыкновенные сети Петри
- •2.1.1. Формальное определение
- •2.1.2. Графы сетей Петри
- •2.1.3. Пространство состояний сети Петри
- •2.1.4. Основные свойства сетей Петри
- •2.1.5. Некоторые обобщения сетей Петри
- •Инварианты сетей Петри
- •2.2. Раскрашенные (цветные) сети Петри
- •2.2.1. Мультимножества
- •2 2.2. Формальное определение cpn
- •2.2.3. Функционирование cpn
- •2.2.4. Расширения cpn
- •2.2.5. Сравнение формализмов обыкновенных и раскрашенных сетей Петри
- •2.2.6. О моделирующих возможностях сетей Петри.
- •2.3. Моделирование дискретных систем
- •2.3.1. Моделирование вычислительных систем
- •1. Простейшая система массового обслуживания.
- •2.3.2. Моделирование программ
- •1. Последовательная модель программирования
- •2. Модель параллелизма данных
- •3. Моделирование некоторых структур параллельного программирования. Семафоры
- •4. Метод асинхронного программирования
- •3 Моделирование протоколов передачи данных
- •1. Описание работы протокола
- •3. Временной механизм работы cpn
- •4. Описание работы cpn
- •2.3.4. Об исследовании сетей Петри с помощью эвм
- •Глава 3. Моделирование вычислительных Процессов с помощью цепей Маркова
- •3.1. Определение цепи Маркова
- •3.3. Классификация состояний цепей Маркова
- •3.4. Оценка длительности пребывания процесса в множестве невозвратных состояний
- •3.5. Исследование динамики цепей Маркова при большом числе шагов
- •4.1. Задачи и упражнения по главе 2
- •4.2. Задачи и упражнения по главе 3
- •1. Запуск программы и построение графа сети Петри
- •2. Задание цветовых множеств, переменных и начальной маркировки
- •Библиографический список
- •Глава 1.Основные понятия теории моделирования 5
- •Глава 2 Введение в сети Петри 21
- •Глава 4. Задания для самостоятельной работы 148
- •Глава 5. Лабораторный практикум 162
2.2.5. Сравнение формализмов обыкновенных и раскрашенных сетей Петри
Подведем некоторые итоги данного раздела. Мы весьма кратко рассмотрели теорию сетей Петри в двух вариантах:
• формализм классических или обыкновенных СП (РТ - сетей в терминологии К. Йенсена);
• формализм раскрашенных сетей Петри - CPN.
Нетрудно убедиться в том, что формализм описания структуры и функционирования CPN справедлив и для обыкновенных СП. При этом пункты 1, 3, 4 и 10 совпадают с описанием в разделе 2.1.1; цветовое множество всего одно и имеет единственный цвет; описание связей между узлами вместо матриц Fp и Ft следует задавать множеством дуг А, узловой функцией N(a) и выражениями на дугах Е(а). Функция С(р) тривиальна и поэтому не нужна, а функция G(t) всегда истинна.
Правила срабатывают и изменения маркировок (2.17) и (2.18) при сделанных предположениях совпадают соответственно с (2.6) и (2.7).
Для раскрашенных сетей Петри также могут быть построены инварианты (см. п. 2.1.6) - как по отдельным видам ресурсов, так и по их комбинациям [10].
В то же время очевидно, что формализм К. Йенсена при всех своих преимуществах в ряде случаев более громоздок и менее удобен по сравнению с формализмом классических обыкновенных сетей Петри. Поэтому при моделировании конкретных систем исследователь должен выбирать наиболее подходящую в данном случае методологию. Именно так и будем поступать в дальнейшем.
2.2.6. О моделирующих возможностях сетей Петри.
С точки зрения инженерных приложений наибольший интерес представляет анализ динамики изменения маркировок сети Петри и возникающих при этом ситуаций.
Однако важен и вопрос о том, насколько широкий класс объектов могут моделировать сети Петри. В п. 2.1.3. говорилось о свободном языке сети Петри, который представляет собой некоторое подмножество всех слов в алфавите Т. Множество свободных языков всех сетей Петри образует класс свободных языков сетей Петри.
В ряде случаев язык сети Петри можно изменить, связав с некоторыми переходами сети N определенные символы из алфавита А, и часть переходов оставить непомеченными (вернее, помеченными пустым символом λ). В этом случае говорят о помеченной сети Петри (PN, ∑ ), где ∑: Т → А – помечающая функция, ставящая в соответствие переходам tj € T символы ак € А. Ясно, что обычная сеть Петри есть частный случай помеченной сети Петри при Т = A={t1...tn}.
Помеченную сеть Петри можно рассматривать как генератор слов и изучать ее возможности с точки зрения математической лингвистики.
Рассмотренные в п. 2.1.5. расширения сетей Петри порождают другие классы языков.
Эти классы языков интересно сравнивать с языками, порождаемыми иными типами абстрактных систем, в частности с языками конечных автоматов и машин Тьюринга. Такое
сравнение позволяет характеризовать моделирующие возможности сетей Петри, их способность адекватно описывать системы со сложной динамикой функционирования.
В [8, 9] доказываются следующие утверждения:
1.Класс помеченных сетей Петри строго мощнее класса конечных автоматов и строго менее мощен, чем класс машин Тьюринга.
2.Классы ингибиторных сетей и сетей с приоритетами строго мощнее класса сетей Петри и равномощны классу машин Тьюринга.
3.Класс раскрашенных сетей при конечном количестве цветов равномощен классу сетей Петри.
4. Класс самомодифицируемых сетей эквивалентен классу ингибиторных сетей и сетей с приоритетами.