Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки
Предмет:
Моделювання систем
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
МЕТОДИЧНІ ВКАЗІВКИ
З практичних робіт
з дисципліни "Моделювання систем"
для студентів базового напрямку 6.050101 “Комп’ютерні науки”
Львів 2011
Імітаційне моделювання процесу функціонування скінченого дискретного стохастиного автомата. Методичні вказівки до лабораторної роботи з дисципліни “Моделювання систем” для студентів базового напрямку 6.050101 “Комп’ютерні науки”/ Укладач: к.т.н., доцент кафедри АСУ Кузьмін О.В. – Львів, Національний університет “Львівська політехніка”, 9 с.
Укладач: Кузьмін Олександр Васильович
Відповідальний за випуск: к.т.н., доцент Шпак З.Я.
Рецензент: д.т.н., професор Різник В.В.
Методичні вказівки затверджено на засіданні кафедри АСУ
Протокол № 2-2011/2012 від 20 вересня 2011 р.
ПРАКТИЧНЕ ЗАНЯТТЯ 2. ДИСКРЕТНО-ДЕТЕРМІНОВАНІ МОДЕЛІ (F-СХЕМИ).
Особливості дискретно-детермінованого підходу розглянемо на прикладі використання в якості математичного апарату теорію автоматів. На основі цієї теорії система представляється у вигляді автомата, який перетворює дискретну інформацію і змінює свій внутрішній стан лише в допустимі моменти часу. Абстрактний скінчений автомат можна представити як математичну схему, яка характеризується шістьма елементами: скінченою множиною х вхідних сигналів (вхідний алфавіт), скінченою множиною y вихідних сигналів (вихідний алфавіт), скінченою множиною z внутрішніх станів (внутрішній алфавіт), початковим станом z0, функцією переходів (z,x), функцією виходів (z,x).
Автомат задається:
F(z, x, y, , , z0). (4.1)
Цей автомат функціонує в дискретному автоматному часі, моментами якого є такти, кожному з яких відповідають постійні значення вхідних, вихідних сигналів і внутрішній стан. Робота скінченого автомата виконується по наступній схемі:
в кожному t+1 такті на вхід автомата, який знаходиться в стані z(t), подається деякий сигнал x(t+1), на який він реагує переходом в t+1 такті в новий стан z(t+1) з видачею деякого вихідного сигнала. Для F-автомата першого роду, який називається автоматом Мілі, можна записати такі співвідношення:
z(t+1)= [z(t), x(t+1)], t=0,1,2, ... (4.2)
y(t+1)= [z(t), x(t+1)], t=0,1,2, ... (4.3)
Скінчений автомат другого роду можна представити:
z(t+1)=[z(t), x(t+1)], t=0,1,2, ... (4.4)
y(t+1)=[z(t+1), x(t+1)], t=0,1,2, ... (4.5)
Якщо y(t)= [z(t)] , то такий автомат другого роду називається автоматом Мура.
По кількості станів розрізняють скінчені автомати з пам’ятю і без пам’яті. Автомати з пам’ятю мають більше одного стану, а автомати без пам'яті (комбінаційні, логічні схеми) мають лише один стан. Робота комбінаційної схеми згідно (4.6) заключається в тому, що вона ставить у відповідність кожному вхідному сигналу x(t) певний вихідний сигнал Y(t), тобто реалізує логічну функцію виду:
y(t)=[x(t)], t=0,1,2, ... (4.6)
Ця функція називається булевою, якщо алфовіти x та y складаються з двох літер. По характеру відліку дискретного часу скінчені автомати поділяються на синхронні і асинхронні.
В синхронних F- автоматах моменти часу, в які автомат зчитує вхідні сигнали визначаються примусово синхронізуючими сигналами. Після чергового синхронізуючого сигнала з врахуванням зчитаного і у відповідності з рівняннями (4.2)-(4.5) відбувається перехід в новий стан і видача сигнала на виході, після чого автомат може сприймати наступне значення вхідного сигналу. Асинхронний F-автомат зчитує вхідний сигнал неперервно і тому, реагуючи на достатньо довгий вхідний сигнал постійної величини x він може, як випливає з рівнянь (4.2)-(4.5), декілька разів змінювати свій стан видаючи відповідну кількість вихідних сигналів, поки не перейде в стійкий, який вже не може бути змінений даним вхідним сигналом.
Існує декілька способів задання роботи F- автоматів, але найчастіше використовується табличний, графічний та матричний. Найпростіший - табличний спосіб задання скінченого автомата, який базується на використанні таблиць переходів і виходів, стрічки яких відповідають вхідним сигналам автомата, а стовбці - його станам. При цьому перший зліва стовбець відповідає початковому стану z0. На перетині i-тої стрічки і к-того стовбця таблиці переходів розміщується відповідне значення функції (zk,xi), а в таблиці виходів - функції (zk,xi).
Для F- автомата Мура обидві таблиці можна сумістити, отримавши так звану відмічену таблицю переходів, в якій над кожним станом zk автомата стоїть відповідний цьому стану згідно (4.5) вихідний сигнал (zk).
Таблиця переходів та виходів F-автомата Мілі.
Таблиця переходів
Таблиця виходів
Зведена таблиця для F- автомата Мура.
При іншому способі задання скінченого автомата використовується поняття направленого графа. Граф автомата представляє собою набір вершин, які відповідають різним станам автомата і з’єднуючих вершини дуг графа, які відповідають тим чи іншим переходам автомата. Якщо вхідний сигнал хк викликає перехід із стану zi в стан zj, то на графі автомата дуга, яка з’єднує вершину zi позначається xk. Для того, щоби задати функцію виходів дуги графа необхідно відмітити відповідними вихідними сигналами.
Для автоматів Мілі ця розмітка відбувається наступним чином. Якщо вхідний сигнал хк діє на стан zi, то, згідно сказаному вище, отримується дуга, яка виходить з zi і помічається хк. Цю дугу додатково відмічають вихідним сигналом y=(zi,xk).
Для автомата Мура ця розмітка така. Якщо вхідний сигнал хк, який діє на деякий стан автомата, викликає перехід в стан zj, то дугу, яка направлена в zj і помічену хк додатково відмічають вихідним сигналом y=(zj,xk).
Розглянемо приклади представлення графом.
F-автомат Мілі
Таблиця переходів
Таблиця виходів
F-автомат Мура
При рішенні задач моделювання систем часто зручнішою формою є матричне задання. При цьому матриця , стрічки якої відповідають біжучим станам, а стовбці - станам переходу, містить елементи ci,j =xk /ys, де xk - вхідний сигнал, ys - вихідний сигнал.
Для F-автомата Мілі відповідна матриця буде виглядати наступним чином:
Якщо перехід із стану zi в стан zj відбувається під впливом декількох сигналів, елемент матриці ci,j представляє собою множину пар вхід-вихід для цього переходу, які з’єднані знаком диз’юнкції “V”. Для F- автомата Мура елемент ci,j дорівнює множині вхідних сигналів на переході zi - zj, а вихід описується вектором виходів:
i-та компонента якого - вихідний сигнал, який відповідає стану zi.
Для розглянутого F- автомата Мура матриця з’єднань і вектор виходів має вигляд:
Для детермінованих автоматів виконується умова однозначності переходів, тобто автомат, який знаходиться в деякому стані, під дією будь-якого вхідного сигналу не може перейти в більш ніж в один стан. Стосовно до графічного опису F- автомата, це означає, що на графі автомата з будь-якої вершини не можуть виходити два і більше ребра, помічених одним і тим самим вхідним сигналом. Розглянемо вид таблиці переходів і граф асинхронного скінченого автомата. Для F- автомата стан zk називається стійким, якщо для будь-якого вхідного сигналу xi, для якого виконується умова (zk,xi)=zk, існує (zk,xi)=yk . Таким чином F- автомат називається асинхронним, якщо кожен його стан zk, який належить множині z, є стійким.
Асинхронний F- автомат Мура.
В якості об’єктів, які описуються F-автоматами можна назвати елементи і вузли ЕОМ, пристрої контролю, регулювання і управління. Для всіх цих об’єктів характерними є дискретний характер роботи у часі.
Питання:
До якого виду моделювання відносяться F- схеми?
Як задається F-автомат?
Яка різниця між F-автоматами Мілі і Мура?
Навести способи опису F-автоматів?
Який автомат називається синхронним, а який – асинхронним?
19.02.2013 22:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора