WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

тоді: а) в випадку існування розмітки М =М, яка знаходиться на деякому шляху із М0 в М, то М оголошується кінцевою вершиною;
б) якщо два довільних розмітки М та Мне співпадають, а - список всіх переходів, які можуть спрацювати із М і приводять до розміток , то із М випускаються дуги, які помічені переходами , але в якості вершин, в які вони ведуть, беруться не як вище, а модифіковані розмітки .
Теорема 6.2
Мережа N обмежена тоді і тільки тоді, коли -дерево не містить символа ні в одній із позицій і ні в одній із вершин.
2.4 РОЗШИРЕНІ МЕРЕЖІ ПЕТРІ
Прості мережі Петрі, що були тут представлені, повністю забезпечують цілий ряд різноманітних застосувань. Проте за допомогою трьох простих розширень вони стають суттєво продуктивнішими. Як показано Хопкрофтом і Ульманом, "розширені мережі Петрі (навіть без додатково введених нижче вагі дуг) Зі, своєю ефективністю дорівнюють машині Тьюрінга [16], тобто вони можуть застосовуватисі як загальна модельобчислюваності.
Розширення. 1. Багаторазове маркування
відповідає
4
Кожен вузол може мати будь-яку кількість маркувань (при зображенні мережі Петрі допускається маркування коротко позначати числом). Правила активізації та перемикань змінюються відповідно:
o перехід активізований тільки тоді, коли число, що відповідає кількості маркувань кожного його вхідного вузла, є більшим за одиницю або дорівнює їй;
o якщо активізований перехід перемикається, то числа-маркування усіх вхідних вузлів цього переходу зменшуються на одиницю, а усіх вихідних вузлів - збільшуються на одиницю.
За цим способом кількість маркувань одного вузла може бути як завгодно великою, але відповідне число не може бути меншим від нуля.
2. Дуги-заперечення
Дуги-заперечення в мережах Петрі зображаються кружечком на кінці замість стрілки (рис.16) і не мають дугової ваги; дуги, що були визначені раніше, розглядаються як позитивні дуги.
рис. 16. Дуга-заперечення
Вони завжди можуть бути направлені тільки від деякого вузла до деякого переходу, зворотного напрямку не дозволяється. Введення дуг-заперечень зумовлює оновлені пристосування правил активізації та перемикань:
o перехід активізований тільки тоді, коли кількість маркувань кожного вхідного вузла з позитивною дугою більша або дорівнює одиниці і коли кількість маркувань кожного вхідного вузла з дугою-запереченням дорівнює нулю (на рис. 16 перехід t активізований, якщо Р1 маркований і Р2 не маркований);
o якщо активізований перехід перемикається, то кількість маркувань усіх вхідних вузлів з позитивними дугами цього переходу зменшується на одиницю, в той час як кількість маркувань вхідних вузлів з дугами-запереченнями залишається незмінною. Числа, що відповідають кількості маркувань усіх вихідних вузлів, як і раніше, збільшуються на одиницю.
3. Вага дуг
Кожна дуга, що не є дугою-запереченням, може мати постійну цілочислову вагу, що більша або дорівнює одиниці (число, що використовується по замовчуванні, рис. 17). Для активізації і перемикання переходу як правило:
o перехід активізований тоді і тільки тоді, коли кількісні маркувань кожного його вхідного вузла більший або дорівнкх відповідній вазі дуги, а для дуги заперечення дорівнює нулю,
рис. 17. Вартості дуг
o при перемиканні переходу кількість маркувань кожного вхідного вузла зменшується на вазі відповідної вхідної дуги (вона залишається незмінною для дуг-заперечень); кількість маркувань кожного вихідного вузла збільшується на вагу відповідної вихідної дуги.
Розділ 3
3.1. ПЕРЕВІРКА МЕРЕЖІ ПЕТРІ НА ІСНУВАННЯ ТУПИКОВОЇ РОЗМІТКИ (ДЕДЛОКУ)
В зв'язку з виникненням проблем з використанням мереж Петрі потрібно розробляти мережу таким чином, щоб в ній були відсутні різного роду проблеми, наприклад проблема пере накопичення фішок в якомусь місці, або виникнення такого явища як дедлок. Саме для цього була розроблена програма яка перевіряє класичну мережу Петрі з заданою початковою розміткою на існування дедлок. Працює вона наступним чином: задається мережа, кількість місць, переходів, множина стрілок які йдуть від місць до переходів та від переходів до місць, потім програма перебирає всі можливі варіанти спрацювання переходів для отримання нової розмітки, якщо жоден перехід не може більше спрацювати в нас отрималась розмітка яка є тупиковою.
В нашому випадку розглянемо наступну мережу
рис 18. Приклад мережі Петрі
Ми маємо мережу Петрі з трьома вершинами, чотирма переходами, чотирма стрілками які ведуть від вершин до переходів та чотирма стрілками, що ведуть від переходів до вершин, тобто множини:
P {p1, p2, p3};
T {a, b, c, d,};
Чотири стрілки множини F;
Чотири стрілки множини H;
Та початкова розмітка, яку позначають вектором М0(1, 0, 3).
Для початку перевірки потрібно, задати ці множини в програму, в відповідні поля які підписані і натиснути кнопку "Перевірити", для того щоб програма візуально відображала роботу заданої мережі в процесі її дослідження на існування тупікової розмітки, потрібно поставити галочку напроти напису "візуальне представлення".
Після натиснення на кнопку "Перевірити" програма збирає дані з відповідних полів і заносить їх значення в відповідні масиви:
type T=record
name:string[4];
num:integer;
end;
Даний тип використовується для створення масивів стрілок множин F та H. В програмі вводяться обмеження на довжину назв як вершин так і переходів, максимальна довжина 4 символи, цієї довжини достатньо. Поле name використовується для зберігання назви переходу або вершини, а поле num це співставлення даній вершині певного числового еквіваленту. Програма працює саме з числами і через них відбувається зворотній зв'язок з назвами вершин чи переходів якщо це необхідно.
M0=array[1..5]of integer;
Даний тип використовується для зберігання початкової розмітки.
F=array[1..20,1..2]of integer;
H=array[1..20,1..2]of integer;
Ці типи використовуються для роботи з вже числовими еквівалентами множин F та Н.
var bol:boolean;
VCX: array [1..5] of integer;
VCY: array [1..5] of integer;
PCX: array [1..8] of integer;
PCY: array [1..8] of integer;
l1,l2,oldbkMode:integer;
rozmitka:M0;
Змінна використовується для роботи з початковою розміткою.
strDoPer:F;
strVidPer:H;
Ці змінні використовуються для роботи з стрілками.
mis:array[1..10]of T;
per:array[1..20]of T;
В цих змінних зберігаються назви вершин та переходів та їхні числові еквіваленти.
s:string;
i:=1;
while form1.StringGrid4.Cells[i,1]'' do
begin
if form1.StringGrid4.Cells[i,1]='' then exit;
mis[i].name:=form1.StringGrid4.Cells[i,1];
mis[i].num:=i;
kilk:=i;
inc(i)
end;
Даний фрагмент програми зберігає введену користувачем назву вершини та
Loading...

 
 

Цікаве