русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Сетевые модели (N-схемы). Сети Петри


Дата добавления: 2013-12-23; просмотров: 2898; Нарушение авторских прав


Лекция №6.

Основные соотношения.Для формального описания структуры и взаимодействия параллельных систем и процессов, а также анализа причинно-следственных связей в сложных системах используются сети Петри (англ. Petri Nets), называемые N-схемами.

Графы специального вида, получившие в дальнейшем название “Сети Петри” были впервые введены Карлом Петри в 60-х годах. В следующем десятилетии начался “бум” разработок в этом направлении. Популярность сетей Петри вызвана удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделированию.

 

Формально N-схема задается четверкой вида

N = <B, D, I, O>,

где В – конечное множество символов, называемых позициями, B ¹ O;

D – конечное множество символов, называемых переходами D ¹ O,

B Ç D = O;

I – входная функция (прямая функция инцидентности), I: B ´ D ® {0, 1};

О – выходная функция (обратная функция инцидентности),

О: B ´ D ® {0, 1}.

I - переход dj в множество входных позиций bj Î I(dj),

O - переход dj в множество выходных позиций bj Î О(dj).

 

 

Для каждого перехода dj Î D

I(dj) = { bi Î B | I(bi, dj) = 1 },

O(dj) = { bi Î B | O(dj, bi) = 1 },

i = ; j = ; n = | B |, m = | D |.

 

Для каждой позиции bi Î B

I(bi) = { dj Î D | I(dj, bi,) = 1 },

O(bi) = { dj Î D | O(bi, dj) = 1 }.

 

 

Таким образом входная функция I отображает переход dj в множество входных позиций bj Î I(dj), а выходная функция O отображает переход dj в множество выходных позиций bj Î О(dj). Для каждого перехода dj Î D можно определить множество входных позиций перехода I(dj) и выходных позиций перехода O(dj) как

Аналогично для каждой позиции bi Î B вводятся определения множеств входных переходов позиции I(bi) и выходных переходов позиции O(bi):



 

Графически N-схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 1). Граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые O и | соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.

 

 
 

 

 


Рис. 1. Графическое изображение N-схемы

Пример.Представим формально N-схему, показанную в виде графа на рис. 1:

N = <B, D, I, O>,

B = <b1, b2, b3, b4, b5>,

D = <d1, d2, d3, d4>.

Входные позиции перехода Выходные позиции

перехода

I(d1)={b1}, O(d1)={b2, b3, b5},

I(d2)={b2, b3, b5}, O(d2)={b5},

I(d3)={b3}, O(d3)={b4},

I(d4)={b4}. O(d4)={b2, b3}.

Возможные приложения N-схем.Приведенное представление N-схемы может использоваться только как отражение статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) позиций М: В ® {0, 1, 2, …}. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин позиций соответствующего числа точек (когда количество точек велико, ставят цифры).

М: В ® {0, 1, 2, …}.

 

Маркированная (размеченная) N-схема может быть описана в виде

 

NМ = <B, D, I, O, M>.

М0: В ® {0, 1, 2, …}.

 

Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как Смена разметок происходит в результате срабатывания одного из переходов dj Î D сети.



<== предыдущая лекция | следующая лекция ==>
Методы теории массового обслуживания. | Правило срабатывания перехода


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.