Математические модели последовательных вычислений

Обязательный курс для студентов 618 групп на 12 семестре обучения.

Лекционная нагрузка — 18 ч.

Курс читает профессор В. А. Захаров.

Лекции

Лекция 1. Сети Петри: происхождение, основные понятия, область применения, свойства вычислений.

Лекция 2. Проблемы ограниченности и безопасности для обыкновенных сетей Петри. Деревья покрытия разметок сетей Петри. Метод проверки свойства ограниченности вычислений обыкновенных сетей Петри при помощи деревьев покрытий разметок. Проблема достижимости для обыкновенных сетей Петри и ее варианты. Проблема живости для обыкновенных сетей Петри. Взаимная сводимость проблем живости и достижимости.

Лекция 3. Проблема R-эквивалентности для обыкновенных сетей Петри. Диофантовы уравнения и некоторые их свойства. Моделирование многочленов обыкновенными сетями Петри. Неразрешимость проблемы R-эквивалентности для обыкновенных сетей Петри. Языки, порождаемые сетями Петри. Примеры языков, порождаемых сетями Петри. Сравнение класса языков, порождаемых обыкновенными сетями Петри, и классов языков иерархии Хомского.

4. Разнообразие классов сетей Петри. Ординарные сети Петри. Моделирование обыкновенных сетей Петри ординарными сетями. Автоматные сети Петри. Синхронизационные сети Петри. Сети потоков работ. Ингибиторные сети Петри. Моделирование счетчиковых машин Минского ингибиторными сетями Петри. Раскрашенные сети Петри. Вложенные сети Петри

Программа курса

Сети Петри

1. Сети позиций и переходов. Мультимножества и операции над ними. Разметки. Сети Петри.
2. Условия срабатывания переходов. Отношение срабатывания переходов. Вычисления обыкновенных сетей Петри. Достижимые и тупиковые разметки. Граф достижимых разметок обыкновенной сети Петри.
3. Сравнение разметок. Теорема о свойстве монотонности вычислений обыкновенных сетей Петри.
4. Свойства ограниченности, безопасности и консервативности сетей Петри.
5. Свойства живости и устойчивости сетей Петри.
6. Проблемы достижимости и R-эквивалентности для сетей Петри.

Литература

1. Котов В.Е. Сети Петри - М.: Мир, 1984. - 160 с.
2. Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984.- 264 с.
3. Ломазова И.А. Вложенные сети Петри: моделирование м анализ распределенных систем с объектной структурой - М.: Научный мир, 2004. - 207 с.
4. Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. - Springer, 2013. - 211 p.
5. Котов В.Е., Сабельфельд В.К. Теория схем программ - М.: Мир, 1983. - 270 с.