Опыт преподавания дискретной математики: сети Петри
1
УДК 519.1
Опыт преподавания дискретной математики:
сети Петри
© Н.В. Золотова, Р.С. Исмагилов
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Статья посвящена изложению одного из многочисленных приложений общих по-
нятий дискретной математики. В качестве примера излагаются начала теории
сетей Петри. Даны определения основных понятий этой теории. Описана работа
сетей Петри на языке теории графов (наглядное описание) и затем на языке ли-
нейных операций над векторами с целочисленными координатами. Затронута
теория графов (и деревьев) маркировок. Отмечена проблема алгоритмической
разрешимости задач, связанных с графами маркировок. Объяснено, каким образом
сети Петри применяются для описания сложных систем, а также для описания
работы сложных систем взаимодействующих устройств. Подробно рассмотрен
пример составления сети Петри такого рода. Изложение не требует предвари-
тельных знаний по данной теме. Для восприятия излагаемого материала необхо-
димы только элементарные сведения по теории графов и начала линейной алгеб-
ры. Материал статьи может быть использован в качестве тем для внеаудитор-
ной работы студентов.
Ключевые слова:
сети Петри, позиции, переходы, графы, деревья, маркированные
сети, векторы, линейная алгебра.
Введение.
Приступая к изучению дискретной математики, сту-
денты сталкиваются с новым для них языком математики. Их преды-
дущий опыт связан с «непрерывными» величинами, функциями и пр.
Действия над ними достаточно привычны (еще со времен обучения в
школе). Столь же привычны и геометрические образы, с которыми
связано изучение аналитической геометрии и линейной алгебры, и
вполне стандартные действия с векторами и т. д. В дискретной мате-
матике несколько иной уровень абстракции и при изучении теории
формальных языков нет опоры на привычные интуитивные образы.
Далее, в знакомой студенту «непрерывной» математике имеются
вполне понятные мотивировки — ответы на вопрос, для чего это
надо; вычисляются площади и объемы, скорости движения и прой-
денные пути, решаются уравнения и системы уравнений и делаются
прочие полезные вещи. Переходя к дискретной математике, обычно
сообщают студенту, что это все окажется полезным в дальнейшем —
для целей вычислительной техники и пр. [1–7]. Но этим не приобре-
тается интуитивное ощущение «нужности» предмета.
Нам хотелось показать студентам, что «абстрактные» понятия
дискретной математики могут быть применены к вполне конкретным
