Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Моделювання систем
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
ІМІТАЦІЙНЕ МОДЕЛЮВАННЯ ПРОЦЕСУ
ФУНКЦІОНУВАННЯ СКІНЧЕНОГО ДИСКРЕТНОГО
СТОХАСТИЧНОГО АВТОМАТА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
з дисципліни "Моделювання систем"
для студентів базового напрямку 6.050101 “Комп’ютерні науки”
Львів 2011
Імітаційне моделювання процесу функціонування скінченого дискретного стохастиного автомата. Методичні вказівки до лабораторної роботи з дисципліни “Моделювання систем” для студентів базового напрямку 6.050101 “Комп’ютерні науки”/ Укладач: к.т.н., доцент кафедри АСУ Кузьмін О.В. – Львів, Національний університет “Львівська політехніка”, 9 с.
Укладач: Кузьмін Олександр Васильович
Відповідальний за випуск: к.т.н., доцент Шпак З.Я.
Рецензент: д.т.н., професор Різник В.В.
Методичні вказівки затверджено на засіданні кафедри АСУ
Протокол № 2-2011/2012 від 20 вересня 2011 р.
Мета роботи - вивчити процес функціонування дискретного скінченого стохастичного автомата та знайти його ймовірностні характеристики за даними експерименту.
І. ОСНОВНІ ПОЛОЖЕННЯ.
Математичні моделі автоматів вивчаються у розділі теоретичної кібернетики - теорії автоматів. Основним у цій теорії є представлення системи у вигляді автомата, який опрацьовує дискретну інформацію та змінює свої внутрішні стани в допустимі моменти часу. Автомат - це деякий пристрій, на вхід якого поступають вхідні сигнали, під дією яких залежно від внутрішнього стану на виході формуються вихідні сигнали, і відбувається перехід в інший внутрішній стан. Скінченим називається автомат, у якого множини внутрішніх ста нів, вхідних та вихідних сигналів скінченні. Скінченний автомат, харак теризується скінченими множинами вхідних сигналів X (вхідний алфа віт), вихідних сигналів Y (вихідний алфавіт), станів Z (алфавіт станів), функціями виходів та переходів.
1.1. Дискретні детерміновані автомати.
Дискретні детерміновані автомати (F-схеми) описуються у вигляді шістки , де X, Y, Z - множини відпо відно вхідних, вихідних сигналів та станів, Z0 - початковий стан, , - відповідно функції переходів та виходів.
Автомат, який описується F-схемою, функціонує в дискретному авто матному часі. У момент часу ti автомат знаходиться в стані , сприймає на вході сигнал , генерує на виході сигнал , і після цього переходить у стан , . Описана послідовність дій відбувається миттєво.
Таким чином реалізується деяке відображення символів вхідного алфа віту в множину символів вихідного.
Автомат Мілі описується за допомогою таких функцій переходів та виходів:
(1)
Для автомата Мура функції виходів та переходів мають вигляд
(2)
За характером відліку дискретного часу автомати поділяються на синхронні та асинхронні. В синхронних автоматах моменти часу дії вхідних сигналів синхронізуються сигналом повної частоти (наприклад, ЕОМ). Асинхронний автомат може сприймати вхідні сигнали в довільні моменти часу (наприклад, автомат для продажу газет та журналів).
Функціонування F-автомата може бути описане одним з трьох способів: табличним, графічним та матричним.
Табличний спосіб вимагає побудови таблиць переходів та виходів (табл. 1, 2).
Таблиця 1
Таблиця переходів F-автомата
X
Z
...
...
Таблиця 2 .
Таблиця виходів F -автомата
X
Z
...
...
У графовому представленні F-автомата, вершини графу відповідають станам автомата, а дуги, які їх з’єднують, тим чи іншим переходам автомата із стану в стан. Якщо вхідний сигнал, Хк викликає перехід з стану Zi в стан Zj, то дуга, яка з’єднує Zj з Zi, позначається Хk. Для задання функції виходів дуги графа необхідно помітити вихідними сигналами. Для автомата Мілі розмітка здійснюється так: якщо вхідний сигнал Хk діє на автомат, що знаходиться в стані Zi, то дугу, яка виходить з Zi і помічена Хk, додатково помічають вихідним сигналом . Для автомата Мура розмітка здійснюється так: якщо вхідний сигнал Xk діє на автомат, що знаходиться в стані Zi, викликає перехід в стан Zj, то дугу, яка направлена в Zj і помічена Xk, додатково помічають вихідним сигналом .
При розв’язуванні задач моделювання найбільш зручною є матрична форма представлення автомата. Матриця станів автомата С являє собою квадратну матрицю , рядки якої відповідають вихідним ста нам, а стовпці - станам переходу. Елемент , який знахо диться на перетині і-го рядку та j-го стовпця, у випадку автомата Мілі відповідає вхідному сигналу Xk, що викликає перехід із стану Zi в стан Zj, та вихідному сигналу ys, який при цьому генерується.
Для F-автомата Мура Cij дорівнює множині вхідних сигналів на переході , а вихід описується вектором виходів , і-a компонента якого - вихідний сигнал, що відповідає стану Zi.
1.2. Диcкретно-стохаcтичні автомати.
У загальному випадку ймовірнісний автомат являє собою дискретний потактний перетворювач інформації з пам’яттю, функціонуван ня якого в кожному такті залежить лише від стану пам’яті і може бути описаний статистично.
Застосування схем ймовірнісних автоматів (Р-схем) має важливе значення для розвитку методів проектування дискретних систем, які виявляють статистично закономірну поведінку, обгрунтування алгоритмічних можливостей таких систем та доцільності їх використання, а також для розв’язування задач синтезу дискретних стохастичних систем за обраним критерієм з урахуванням обмежень.
Математично Р-автомат описується з використанням основних понять F-автомату. Розглянемо множину G, елементами якої є різноманіт ні пари , де xi та zs - елементи підмножини відповідно вхідних сигналів X та станів Z. Якщо існують дві такі функції φ та ψ, за допомогою яких здійснюється відображення G(Z та G(Y, то п'я тірка P=<Z, X, Y, φ, ψ> відображає детермінований автомат.
Розглянемо більш загальну математичну схему. Нехай Ф - множина різноманітних пар виду , де yj - елемент Y. Поставимо вимо гу, щоб довільний елемент множини G спричиняв на множині Ф деякий закон розподілу:
Елементи з Ф
(xi,zs) b11 b12 ... bk,j-1 bkj
При цьому , bkj - ймовірності переходу автомата в стан Zk та генераці вихідного сигналу yj, якщо він знаходився в стані Zs та на його вхід в цей момент прийшов сигнал xi.
Число таких розподілів, які подаються у вигляді таблиць, дорівнює числу елементів множини G. Позначимо множину таких таблиць В і отримаємо опис стохастичного дискретного автомата в вигляді четвірки .
Нехай елементи множини G спричиняють на множинах Y та Z деякі закони розподілу:
Елементи з Y
(xi,zs)
Елементи з Z
(xi,zs)
При цьому , , де pk та qj - ймовірності переходу автомата в стан Zk та генерації вихідного сигналу yj відповідно за умови, що Р-автомат знаходився в стані Zs та на його вхід прийшов сигнал xi. Якщо для всіх k та j справедливе співвідношення , то такий автомат будемо називати стохастичним автоматом Мілі. Ця вимога є умовою незалежності розподілів для нового стану Р-автомата та його вихідного сигналу.
Нехай визначення вихідного сигналу Р-автомата залежить лише від того стану, в якому знаходится автомат в поточному такті. Іншими словами, нехай кожен елемент вихідної множини Y спричиняє розподіл ймо вірностей виходів виду:
Елементи з Y
де , Si - ймовірність генерації вихідного сигналу уi, за умови, що Р-автомат знаходився в стані Zk.
Якщо для всіх k та i справедливе співвідношення , то такий автомат називається стохастичним автоматом Мура.
Таким чином, поняття Р-автоматів Мілі та Мура введені аналогічно до відповідних детермінованих автоматів.
Окремий випадок Р-автомата - це автомат, у якого перехід в новий стан або вихідний сигнал визначаються детермі новано. В першому випадку такий автомат називається Z-детермінованим стохастичним автоматом, в другому - Y-детермінованим.
Приклад 1.
Розглянемо Y-детермінований P-автомат, який заданий таблицею переходів (табл. 3) та виходів:
Таблиця З
Таблиця переходів Y-детермірнованого Р-автомата
Zk
Zk
Z1
Z2
...
Zk-1
Zk
Z1
Z2
...
Zk
p11
p21
...
pk1
p12
p22
...
pk2
...
...
...
...
p1(k-1)
p2(k-1)
...
pk(k-1)
p1k
p2k
...
pkk
Таблицю переходів можна в цьому випадку представити у вигляді квадратної матриці перехідних ймовірностей Р:
.
При цьому має виконуватися умова, що .
Для повного опису Y-детермінованого Р-автомата необхідно також визначити початковий розподіл ймовірностей виду
де dk - ймовірність того, що на початку роботи Р-автомат знаходиться в стані Zk.
До початку функціонування Р-автомат знаходиться в стані Z0 і в нульовий такт часу змінює стан згідно з розподілом D. Подальший про цес зміни станів автомата визначається матрицею переходів Р. Можливе також введення інформації про початковий стан в матрицю Р шляхом збільшення її розмірності на одиницю до . Перший рядок цієї матриці відповідає початковому стану Z0 і має вигляд , а перший стовпчик буде нульовим.
З точки зору математичного апарату цей автомат еквівалентний дискретному марківському ланцюгу.
Приклад 2.
Заданий Y-детермінований Р-автомат, для якого необхідно побудувати граф переходів
Z
Y
0
0
1
1
0
Граф переходів цього автомату зображений на рисунку.
2. ОПИС РОБОТИ АЛГОРИТМУ ІМІТАЦІЙНОГО МОДЕЛЮВАННЯ Y-ДЕТЕРМІНОВАНОГО Р-АВТОМАТА.
Припустимо, що треба відтворити процес функціонування Y-детермінованого Р-автомата, описаного в прикладі 2, і знайти ймовірності перебування автомата у станах та ймовірність, з якою на виході автомата буде отримуватися вихідний сигнал, рівний 1. За початковий стан приймемо стан Z0.
Послідовність дій для кожного такта моделювання автомата наступна.
Генерується випадкове число на інтервалі (0,1) за рівномірним законом розподілу.
На основі цього числа визначається стан, в який перейде автомат, за наступною схемою. Якщо в попередньому такті автомат знаходився, припустимо, в стані Z3 і значення випадкового числа дорівнює 0.5, то виконується цикл по j від 0 до 4. Z:=Zj. Якщо 0.5<, то робота цикла припиняється і стан переходу автомата визначається змінною Z. Для нашого прикладу станом переходу буде стан Z2.
В матриці В розмірністю 5х5, елементи якої на початку моделювання онулюються, до елемента в32 додається 1. В наступному такті стан автомата є Z2.
Пункти 1-3 повторюються для заданої кількості тактів.
Після закінчення моделювання елементи матриці В містять кількість переходів між відповідними станами автомата, загальна кількість яких дорівнює кількості тактів моделювання.
Для обчислення ймовірностей перебування автомата у станах необхідно знайти суми елементів кожного стовбця матриці В, який відповідає певному стану, і розділити кожну суму на загальну суму елементів.
Для визначення ймовірності появи на виході автомата вихідного сигнала, рівного 1, слід просумувати ймовірності перебування автомата у станах, які відповідають одиничному вихідному сигналу. Для нашого прикладу це стани Z2 і Z3.
3. ПОРЯДОК ВИКОНАННЯ РОБОТИ.
По виданому викладачем завданню скласти програму моделювання Y-детермінованого Р-автомата і відлагодити її.
Провести моделювання автомата для заданої кількості тактів.
Отримати результати моделювання: матрицю В, ймовірності перебування автомата у станах, ймовірність появи на виході автомата вихідного сигнала, рівного 1.
Оформити звіт за результатами виконаної роботи.
4. ЗМІСТ ЗВІТУ.
Мета роботи.
Основні положення.
Вихідні дані варіанту індивідуального завдання.
Результати моделювання.
Текст програми.
Екранні форми.
Висновки.
5. ВАРІАНТИ ІНДИВІДУАЛЬНИХ ЗАВДАНЬ.
6. КОНТРОЛЬНІ ЗАПИТАННЯ
І. Що являє собою скінченний автомат?
2. Основні види скінченних автоматів та їх особливості.
3. Чим відрізняються між собою автомати Мілі та Мура?
4. Яким чином функціонує дискретний стохастичний автомат?
5. Як будується матриця В кількості переходів Y-детермінованого Р-автомата?
7. ЛІТЕРАТУРА.
Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. - М.: Сов. радио, 1973, 440 с.
Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2. Основы кибернетических моделей. Учеб. пособие для вузов. – М.: Энергия, 1979.- 584 с.
Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов по спец. “Автоматизированные системы управления”. – М.: Высш. шк., 1985.- 271 с.
Трахтенброт Б.А. Алгоритмы и выислительные автоматы. – М.: Сов. радио, 1974.- 200 с.
19.02.2013 22:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора