Властивості мереж Петрі.. Методичні вказівки до лабораторної роботи з Основи автоматизованого проектування складних об’єктів і систем. Робота № 400267

Перехід до торгівельного партнера Binance

Властивості мереж Петрі.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Системи автоматизованого проектуваня

Інформація про роботу

Рік:

2004

Тип роботи:

Методичні вказівки до лабораторної роботи

Предмет:

Основи автоматизованого проектування складних об’єктів і систем

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка" Властивості мереж Петрі. МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 з курсу "Основи автоматизованого проектування складних об’єктів і систем" для студентiв базового напрямку 6.0804 "Комп'ютернi науки" Затверджено на засiданнi кафедри (Системи автоматизованого проектування" Протокол N 1 вiд 27.08.2004р. Львiв 2004 Властивості мереж Петрі. Методичні вказівки до лабораторної роботи №6 з курсу “Основи автоматизованого проектування складних об`єктів і систем” для студентiв базового напрямку 6.0804 - "Комп'ютернi науки" / Укл. А.Б.Керницький - Львiв: НУ “ЛП”, 2004. - 13с. Укладач: А.Б.Керницький, др.–інж.т.н. Вiдповiдальний за випуск С.П.Ткаченко, канд.техн.наук, доц. Рецензенти: Ю.В.Стех, канд.техн.наук, доц. I.I.Мотика, канд.техн.наук, доц. 1. МЕТА РОБОТИ Мета роботи – ознайомититися з основними властивостями мереж Петрі.. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Модель — це представлення, як правило, у математичних термінах найхарактерніших рис об'єкту або системи, що вивчається. Для побудови складних систем обробки інформації та моделювання асинхронних інформаційних потоків потрібна математична модель, зручна в описі керування роботою таких систем. Історично першою для такого моделювання використовувалася теорія автоматів. Автомати застосовують для моделювання послідовних алгоритмічних систем — коли система (автомат) послідовно переходить зі стану в стан відповідно до заданої функції переходу і здійснює наступний крок алгоритму. Але існують і неалгоритмічні паралельні системи з недетермінованою поведінкою, в якій компоненти функціонують незалежно і взаємодіють час від часу. Прикладами таких систем є багатопроцесорні обчислювальні машини, паралельні програми, що моделюють паралельні дискретні системи, мультипрограмні операційні системи. Такі системи не описуються адекватно в термінах класичної теорії автоматів. Наприклад, неможливо описати ці системи за допомогою таких термінів, як стан автомату, глобальна функція переходу. Мережі Петрі (МП) це інструмент для математичного моделювання і дослідження складних систем. Мета представлення системи у вигляді мережі Петрі і подальшого аналізу цієї мережі полягає в отриманні важливої інформації про структуру і динамічну поведінку модельованої системи. Ця інформація може використовуватися для оцінки модельованої системи і вироблення пропозицій по її удосконаленню. Вперше мережі Петрі запропонував німецький математик Карл Адам Петрі [1]. 2.1. Природа систем, які моделюються мережами Петрі. Мережі Петрі призначені для моделювання систем, які складаються з безлічі компонент, які взаєодіють між собою. При цьому компонента сама може бути системою. Діям різних компонент системи властивий паралелізм. Прикладами таких систем можуть бути обчислювальні системи, у тому числі і паралельні, комп'ютерні мережі, програмні системи, що забезпечують їх функціонування, а також економічні системи, системи управління дорожнім рухом, хімічні системи тощо. Мережі Петрі притаманні такі риси: МП використовується для опису модельованої системи, іце може бути застосовано для специфікацій (для побудови систем)або опису системи. Поведінку МП можна проаналізувати як моделюванням(що еквівалентно виконанню програми та її налагодженню), такі формальнішими методами аналізу (що відповідає програмнійперевірці). Процес створення опису та виконання аналізу допомагає краще зрозуміти модельовану систему самому моделювальнику. 2.2. Підходи до проектування систем за допомогою МП. Мережі Петрі використовуються, як допоміжний інструмент аналізу в одному з підходів до проектування і аналізу систем. Тут для побудови системи використовуються загальноприйняті методи проектування. Потім побудована система моделюється за допомогою мереж Петрі, і модель аналізується. Якщо в ході аналізу у проекті знайдені недоліки, то з метою їх усунення проект модифікується. Модифікований проект потім знову моделюється і аналізується. Даний цикл повторюється доти, доки аналіз, що проводиться, не приведе до успіху. Інший підхід передбачає побудову проекту одразу у вигляді мереж Петрі. Методи аналізу застосовуються мережі для створення проекту, що не мережі помилок. Потім мережі Петрі перетвориться в реальну робочу систему. У першому випадку необхідна розробка методів моделювання систем мережами Петрі, а у другому випадку повинні бути розроблені методи реалізації мереж Петрі системами. ОСНОВНІ ВИЗНАЧЕННЯ 2.3. Теоретико-множинне визначення мереж Петрі. Нехай мультимножина це множина, яка допускаєе входження декількох екземплярів одного і того самого елемента. Визначення 2.1. Мережа Петрі PN є четвіркою PN=(P,Т,I,O), де P={p1, p2,...,pn} — скінчена множина позицій, n(0; T={t1, t2,...,tm} — скінчена множина переходів, m(0; I: T ( P* — вхідна функція, яка співставляє переходу мультимножину його вхідних позицій (графічно представляється вхідними дугами переходу); О: T ( P* — вихідна функція, яка співставляє переходу мультимножину його вихідних позицій (графічно представляється вихідними дугами переходу). Позиція p(P називається входом для переходу t(T, якщо p(I(t). Позиція p(P називається виходом для переходу t(T, якщо p(O(t). Структура мережі Петри визначається її позиціями, переходами, вхідною і вихідною функціями. Приклад 2.1. Мережа Петрі. PN =(P,T,I,O), P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4, t5} I(t1)={ p1}, O(t1)={ p2, p3}, I(t2)={ p2}, O(t2)={p4}, I(t3)={ p3}, O(t3)={p5}, I(t4)={ p4}, O(t4)={p2}, I(t5)={ p4, p5}, O(t5)={p1}. Використовування мультимножини вхідних і вихідних позицій переходу, а не множин, дозволяє позиції бути кратним входом і кратним виходом переходу відповідно. При цьому кратність визначається кількістю екземплярів позиції у відповідній мультимножині. 2.4. Графи мереж Петрі. Найнаочнішим представленням мережі Петрі є її графічне представлення. Графічне представлення МП - дводольний орієнтований граф. Нагадаємо, що дводольний граф - це такий граф, безліч вершин якого розбивається на дві підмножини і не існує дуги, що сполучає дві вершини з однієї підмножини. Граф мережі Петрі володіє двома типами вузлів: круг (, який представляє місце мережі Петрі; і планка (, яка представляє перехід мережі Петрі. Орієнтовані дуги цього графа (стрілки) сполучають перехід з його вхідними і вихідними позиціями. При цьому дуги направлені від вхідних позицій до переходу і від переходу до вихідних позицій. Кратним вхідним і вихідним позиціям переходу відповідають кратні вхідні і вихідні дуги. Приклад 2.2. Граф мережі Петрі, яка визначена у прикладі 2.1. 2.5. Маркування мереж Петрі. Маркування — це розміщення у позиціях мережі Петрі фішок, які зображені на графі мережі Петрі крапками. Фішки використовуються для визначення виконання мережі Петрі. Кількість фішок у позиції при виконанні мережі Петрі може змінюватися від 0 до безмежності. Визначення 2.2. Маркування М мережі Петрі N=(P,T,I,О) є функцією, яка відображає множину позицій P у множину невід’ємних цілих чисел Nat (де число з Nat позначає кількість фішок, які розміщуються у відповідну позицію). Маркування М, може бути також визначене як n-вектор М=<Мp1,Мp2…,М(pn)> где n=(P( – кількість позицій у мережі Петрі і для кожного 1(i(n справедливоМ(pi)(Nat. – кількість фішок у позиції pi. Визначення 2.3. Маркована мережа Петрі N=(P,Т,I,О,М) визначається сукупністю структури мережі Петрі (P,T,I,О) і маркування М. Приклад 2.3. Графічне представления маркованої мережі Петрі. MPN =(P,T,I,O), P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4, t5} I(t1)={ p1}, O(t1)={ p2, p3}, I(t2)={ p2}, O(t2)={p4}, I(t3)={ p3}, O(t3)={p5}, I(t4)={ p4}, O(t4)={p2}, I(t5)={ p4, p5}, O(t5)={p1}. M1 = (1, 0, 0, 0, 0) Множина всіх маркувань мереж Петрі бзмежне. Якщо фішок, які розміщуються у позицію надто багато, то зручніше не рисувати фішки у крузі цієї позиції, а вказувати їхню кількість. 2.6. Правила виконання мереж Петрі. Мережа Петрі виконується засобами запусків переходів. Запуск переходу керується фішками у його вхідних позиціях і супроводжується видаленням фішок з цих позицій і додаванням нових фішок у його вихідні позиції. Перехід може запускатися лише у тому випадку, коли він активізований. Перехід називається активізованим, якщо кожна з його вхідних позицій містить кількість фішок, яка не менша, ніж кількість дуг, які ведуть з цієї позиції у перехід (або кратності вхідної дуги). Нехай функція А: P(T(Nat для довільних позицій p(P і переходу t(Т задає значення А(p,t), яке співпадає с кратністю дуги, яка веде з p у t, якщо така дуга існує, і з нулем, у протилежному випадку. Нехай функція А: T( P (Nat для довільних позицій p(P і переходу t(Т задає значення А(t,p), яке співпадає с кратністю дуги, яка веде з t у p, якщо така дуга існує, і з нулем, у протилежному випадку. Визначення 2.4. Перехід t(T у маркованій мережі Петрі MPN=(P,T,1,О,M) активізований, якщо для всіх p(I(t) справедливо Мp(А (p,t). Запуск активізованого переходу t(T із своєї вхідної позиції p(I(t) видаляє А(p,t) фішок, а у свою вихідну позицію p’(O(t) додає А(t,p’) фішок. Приклад 2.5. Запуск активізованого переходу у мережі Петрі. Мережа Петрі до запуску переходу t1. Мережа Петрі після запуску переходу t1. Визначення 2.5. Перехід t у маркованій мережі Петрі з маркуванням М може бути запущений кожного разу, коли він активізований і у результаті цього запуску утворюється нове маркування М', яка визначається наступним співвідношенням: М'(p)= М(p) – А(p,t) + А(t,p). для всех p(P. Запуски можуть здійснюватися доти, поки існує хоча б один активізований перехід. Коли не залишиться жодного активізованого переходу, виконання припиняється. Якщо запуск довільного переходу t перетворює маркування мережі Петрі в нове маркування М', то будемо говорити, що М' досяжна из М шляхом запуску перехода t і позначати цей факт, як М (t М '. Це поняття очевидним чином узагальнюється для випадку послідовності запусків активізованих переходів. Через R(MPN,М) позначимо множину всіх досяжних маркувань із початкового маркування М у мережі Петрі MPN. Приклад 2.6. Преретворення маркування мережі Петрі у прикладі 2.5. Перехід t1 перетворює маркуванняМ=<6,2> у маркування М’=<3,4>. 3. АНАЛІЗ МЕРЕЖ ПЕТРІ Моделювання систем мережами Петрі, перш за все, зумовлене необхіднітю проведення глибокого дослідження їхньої поведінки. Для проведення такого дослідження необходні методи анализу властивостей самих мереж Петрі. Цей підхід передбачає зведення дослідження властивостей реальної системи до аналізу визначених властивостей моделюючої мережі Петрі. 3.1. Властивості мереж Петрі. Обмеженість. Визначення 3.1. Позиція p(P мережі Петрі PN=(P,Т,I,O) з початковим маркуванням М є k-обмеженою, якщо М’(p)(k для будь-якого досяжного маркування М’(R(PN,М). Позиція називається обмеженою, якщо вона є k-обмеженою для певного цілого значення k. Мережа Петрі обмежена, якщо всі її позиції обмежені. Безпека. Визначення 3.2. Позиція p(P мережі Петрі PN =(P,Т,I,O) з початковим маркуванням М є безпечною, якщо вона є 1-обмеженою. Мережа Петрі безпечна, якщо безопечні всі позиції мережі. Збереження. Визначення 3.3. Мережа Петрі PN =(P,Т,I,O) з початковим маркуванням М є зберігаючою, якщо для будь-якого досяжного маркування М’(R(PN,М) справедливе наступне. М’(p) = М(p). Активність. Тупик в мережі Петрі — це перехід (або множина переходів), які не можуть бути запущені. У зв’язку із поняттям тупика визначимо для мережі Петрі PN із початковим маркуванням М наступні рівні активності переходів: Рівень 0: Перехід t володіє активністю рівня 0 і називається мертвим, якщо він ніколи не може бути запущений. Рівень 1: Перехід t володіє активністю рівня 1 і називається потенційно живим, якщо існує таке М’(R(PN,М), що t є дозволеним в М’. Рівень 2: Перехід t володіє активністю рівня 2 і називається живим, якщо для бідь-якого М’(R(PN,М) перехід t є потенційно живим для мережі Петрі PN з початковим маркуванням М’. Мережа Петрі називається живою, якщо всі її переходи є живими. Досяжність і покриваємість. Задача долсяжності: Для даної мережі Петрі з початковим маркуванням М і маркуванням М’ визначити: М’(R(PN,М)? Задача покриваємості. Для даної мережі Петрі з початковим маркуванням М і маркуванням М’ визначити, чи існує таке досяжне маркування М”(R(PN,М), що М"(М’. (Відношення М"(М’ є істинним, якщо кожний елемент маркування М" не менше відповідного елемента маркування М’.) Еквівалентність і включення. Мережі Петрі притаманна деяка поведінка, яка визначається множиною її можливих послідовностей запусків переходів або її множиною досяжних маркувань. Поняття еквівалентності мереж Петрі може бути визначене через рівеність множин досяжних маркувань. Визначення 3.5. Мережа Петрі PN=(P,Т,I,O) із початковим маркуванням М і мережа Петрі PN’=(P’,Т’,I’,O’) із початковим маркуванням М’ є еквівалентними якщо справедливо R(PN,М)=R(PN’,М’). Поняття еквівалентності мереж Петрі може бути визначено також через рівність множин можливих послідовностей запусків переходів. Слабшим, у порівнянні еквівалентністю, є властивість включення, визначення якого співпадає з визначенням еквівалентності, з точністю до заміни = на (. 4. ЛАБОРАТОРНЕ ЗАВДАННЯ 4.1. Побудуйте графи наступних мереж Петрі: (а) C={P,T,I,O}, P={p1,p2,p3,p4,p5,p6}, T={t1,t2,t3,t4,t5}; I(t1)={p1}; I(t2)={p3}; I(t3)={p2,p3}; I(t4)={p4,p5,p5,p5};I(t5)={p2}; O(t1)={p2,p3}; O(t2)={p3,p5,p5}; O(t3)={p2,p4}; O(t4)={p4};O(t5)={p6}; (б) C={P,T,I,O}, P={p1,p2,p3,p4,p5,p6,p7,p8,p9}, T={t1,t2,t3,t4,t5,t6}; I(t1)={p1}; I(t2)={p8}; I(t3)={p2,p5}; I(t4)={p3}; I(t5)={p6,p7}; I(t6)={p4,p9}; O(t1)={p2,p3}; O(t2)={p1,p7}; O(t3)={p6}; O(t4)={p4};O(t5)={p9}; O(t6)={p5,p8}. 4.2. На графах мережі Петрі із задачі 1, вкажіть маркування: (а) m=(1,0,2,0,3,1) для мережі Петрі (а); (б) m=(1,2,3,4,34,0,0,0,1) для мережі Петрі (б). Примітка: Індивідуальний варіант задається викладачем. 5. ЗМІСТ ЗВІТУ Мета роботи. Теоретичний аналіз опрацьованого матеріалу. Відповіді на контрольні запитання. Індивідуальне завдання. Аналіз отриманих результатів і висновки. Список використаної літератури. 6. СПИСОК ЛІТЕРАТУРИ Дж. Питерсон. Теория сетей Петри и моделирование систем. М. Мир, 1984. Котов В.Е. Сети Петри. М.: Наука, 1984. Ч.Хоар. Взаимодействующие последовательные процессы. М. Мир, 1989 г. Bacceli, Francois, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley, Chichester, England, 1992. Cassandras, Christos G., Discrete Event Systems, Richard D. Irwin, Inc., Homewood, IL, 1993. David, R. and H. Alla, Petri Nets and Grafcet: Tools for Modeling Discrete Event Systems, Prentice-Hall, London, 1992. Jensen, Kurt, Coloured Petri Nets, Springer-Verlg, Berlin, 1992 Peterson, James L., Petri Net Theory and the Modeling of Systems, Prentice Hall, Englewood Cliffs, NJ, 1981. Reisig, Wolfgang, Petri Nets, An Introduction, Springer-Verlg, Berlin, 1985. Zhou, MengChu, and Frank DiCesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers, Boston, 1993. А.В. Катренко Системний аналіз об’єктів та процесів комп’ютеризації: Навчальний посібник. – Львів: “Новий світ”. - 424с. НАВЧАЛЬНЕ ВИДАННЯ Властивості мереж Петрі Методичні вказівки до лабораторної роботи № 6 з курсу “Основи автоматизованого проектування складних об`єктів і систем” для студентiв базового напрямку 6.0804 - "Комп'ютернi науки" Укладач Керницький Андрій Богданович Редактор Черничевич О.

Методичні вказівки до лабораторної роботи Основи автоматизованого проектування складних об’єктів і систем

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись