1 ГОУ ВПО Уральский государственный технический университет – УПИ

2 Кафедра «Автоматика и управление в технических системах» направление – Автоматизация и управление МОДЕЛИРОВАНИЕ СИСТЕМ Лекция 4. Дискретно-детерминированные модели (F-схемы). Дискретно-стохастические модели (Р-схемы). Преподаватель: Трофимова Ольга Геннадиевна, доц., к.т.н.

3 Цель изучения материала: изучить особенности дискретно-детерминированного подхода при построении математических моделей на основе теории автоматов; научиться строить формальную модель объекта, используя типовую математическую F -схему; изучить особенности дискретно-стохастического подхода при построении математических моделей на основе теории автоматов; научиться строить формальную модель объекта, используя типовую математическую Р -схему. Компетенций, формирующиеся в процессе знакомства с материалом: приобретать новые знания, используя современные образовательные и информационные технологии; разрабатывать модели информационных систем, включая модели систем управления; использовать современные технологии моделирования систем.

4 Содержание лекции 4 Раздел 2. Математические схемы моделирования систем. Дискретно-детерминированные модели (F-схемы). Основные соотношения. Возможные приложения F-схемы. Дискретно-стохастические модели (Р-схемы). Основные соотношения. Возможные приложения F-схемы.

5 Основные соотношения В качестве математического аппарата дискретно- детерминированного подхода применяется теория автоматов. Система представляется в виде автомата – устройства с входными и выходными сигналами, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Конечный автомат – это автомат, у которого множества внутренних состояний, входных и выходных сигналов являются конечными множествами. Дискретно-детерминированные модели (F-схемы)

6 Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: - конечным множеством Х входных сигналов (входным алфавитом); - конечным множеством Y выходных сигналов (выходным алфавитом); - конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); - начальным состоянием z 0, z 0 Z; - функцией переходов (z, x); - функцией выходов (z, x). Дискретно-детерминированные модели (F-схемы)

7 Конечный автомат задается F-схемой: F = Z, X, Y,,, z 0. Конечный автомат функционирует в дискретном времени, моментами которого являются такты. Каждому t-му такту t = 0, 1, 2, …, соответствуют постоянные значения входного x(t) X сигнала, выходного y(t) Y сигнала и внутренние состояния z(t) Z. Начальное состояние z(0) = z 0. Абстрактный конечный автомат имеет один входной и один выходной каналы. Дискретно-детерминированные модели (F-схемы)

8 В каждый момент t = 0, 1, 2, … дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0) = z 0. В момент t, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(t) X и выдать на выходном канале сигнал y(t) = [z(t), x(t)], переходя в состояние z(t+1) = [z(t), x(t)], z(t) Z, y(t) Y. Дискретно-детерминированные модели (F-схемы)

9 Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z 0, подавать в некоторой последовательности буквы входного алфавита x(0), x(1), x(2), …, т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1), y(2), …, образуя выходное слово. Дискретно-детерминированные модели (F-схемы)

10 Таким образом, работа конечного автомата происходит по схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом (t+1)-го такта в новое состояние z(t+1) и выдачей некоторого выходного сигнала y(t). Дискретно-детерминированные модели (F-схемы)

11 Опишем это следующими уравнениями: для F-автомата первого рода, называемого автоматом Мили, z(t+1) = [z(t), x(t)], t = 0, 1, 2, …; (2.15) y(t) = [z(t), x(t)], t = 0, 1, 2, …; (2.16) для F-автомата второго рода z(t+1) = [z(t), x(t)], t = 0, 1, 2, …; (2.17) y(t) = [z(t), x(t – 1)], t = 1, 2, 3,….(2.18) Автомат второго рода, для которого функция выхода не зависит от входной переменной x(t), т.е. y(t) = [z(t)], t = 0, 1, 2, …,(2.19) называется автоматом Мура. Дискретно-детерминированные модели (F-схемы)

12 При этом, согласно (2.16), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определенный выходной сигнал y(t), т.е. реализует логическую функцию вида y(t) = [ x(t)], t = 0, 1, 2, …. Эта функция называется булевой, если алфавит X и Y, которым принадлежат значения сигналов x и y, состоят из двух букв. Уравнения (2.15)-(2.19), полностью задающие F-автомат, являются частным случаем уравнений (2.3) и (2.4), когда система детерминированная и на её единственный вход поступает дискретный сигнал X. Дискретно-детерминированные модели (F-схемы)

13 По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния. Автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. Дискретно-детерминированные модели (F-схемы)

14 В синхронных F-автоматах моменты времени, в которые автомат считывает входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учетом считанного и в соответствии с уравнениями (2.15)-(2.19) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Реакция автомата на каждое значение входного сигнала заканчивается за один такт. Длительность такта определяется интервалом между соседними синхронизирующими сигналами. Дискретно-детерминированные модели (F-схемы)

15 Асинхронный F-автомат считывает входной сигнал непрерывно. F-автомат реагирует на достаточно длинный входной сигнал постоянной величины x, поэтому, как следует из (2.15)-(2.19), он может несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое состояние, которое уже не может быть изменено данным входным сигналом. Дискретно-детерминированные модели (F-схемы)

16 Возможные приложения F-схемы Для задания конечного F-автомата опишем все элементы множества F =, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z 0, в котором автомат находится в состоянии t = 0. Существуют несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный. Дискретно-детерминированные модели (F-схемы)

17 В табличном способе задаются таблицы переходов и выходов. Строки таблицы соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый слева столбец соответствует начальному состоянию z 0. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение функции переходов (z k, x i ), а в таблице выходов – соответствующее значение функции выходов (z k, x i ). Для F-автомата Мура обе таблицы можно совместить. Дискретно-детерминированные модели (F-схемы)

18 Описание работы F-автомата Мили таблицами переходов и выходов иллюстрируется в таблице 2.1 X i z 0 z 1 …z k Переходы x 1 (z 0, x 1 ) (z 1, x 1 )… (z k, x 1 ) x 2 (z 0, x 2 ) (z 1, x 2 )… (z k, x 2 ) x i (z 0, x i ) (z 1, x i )… (z k, x i ) Выходы x 1 (z 0, x 1 ) (z 1, x 1 )… (z k, x 1 ) x 2 (z 0, x 2 ) (z 1, x 2 )… (z k, x 2 ) x i (z 0, x i ) (z 1, x i )… (z k, x i ) Дискретно-детерминированные модели (F-схемы)

19 Описание работы F-автомата Мура таблицей переходов иллюстрируется в табл x i (z k ) (z 0 ) (z 1 )… (z k ) z 0 z 1 …z k x 1 (z 0, x 1 ) (z 1, x 1 )… (z k, x 1 ) x 2 (z 0, x 2 ) (z 1, x 2 )… (z k, x 2 ) …………… x i (z 0, x i ) (z 1, x i )… (z k, x i ) Дискретно-детерминированные модели (F-схемы)

20 Пример 1 табличного способа задания F-автомата Мили F1 приведены в табл. 2.3, x i z k z 0 z 1 z 2 Переходы x 1 z 2 z 0 z 0 x 2 z 0 z 2 z 1 Выходы x 1 y 1 y 1 y 2 x 2 y 1 y 2 y 1 Дискретно-детерминированные модели (F-схемы)

21 Пример 2 табличного способа задания F-автомата Мура F2 представлен в табл ХY x i y 1 y 1 y 3 y 2 y 3 z 0 z 1 z 2 z 3 z 4 x 1 z 1 z 4 z 4 z 2 z 2 x 2 z 3 z 1 z 1 z 0 z 0 Дискретно-детерминированные модели (F-схемы)

22 При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x k вызывает переход из состояния z i в состояние z j, то на графе автомата дуга, соединяющая вершину z i c вершиной z j, обозначается x k. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Дискретно-детерминированные модели (F-схемы)

23 Для автоматов Мили эта разметка производится так: если входной сигнал x k действует на состояние z i, то получается дуга, исходящая из z i и помеченная x k ; эту дугу дополнительно отмечают выходным сигналом y = (z i, x k ). Для автомата Мура аналогичная разметка графа такова: если входной сигнал x k, действуя на некоторое состояние автомата, вызывает переход в состояние z j, то дугу, направленную в z i и помеченную x k, дополнительно отмечают выходным сигналом y = (z j, x k ). Дискретно-детерминированные модели (F-схемы)

24 Пример 1. На рис а приведен F-автомат Мили F1 заданный ранее табл. 2.3 Рис. 2.4, а Граф автомата Мили х 2 у 1 у 1 у 2 x 1 x 1 x 1 у 1 x 2 y 2 y 1 x 2 z0z0 z1z1 z2z2 Дискретно-детерминированные модели (F-схемы)

25 Пример 2. На рис б приведен F-автомат Мура F2, заданный ранее таблицей. Рис б Граф автомата Мура у 1 х 1 у 1 х 2 у 3 х 2 х 1 х 2 х 2 х 1 х 1 х 2 х 1 у 2 у 3 z0z0 z3z3 z2z2 z4z4 z1z1 Дискретно-детерминированные модели (F-схемы)

26 При матричном задании конечного автомата матрица соединений автомата квадратная С= с ij. Строки матрицы соответствуют исходным состояниям, а столбцы матрицы – состояниям перехода. Элемент с ij = x k / y s, стоящий на пересечении i-й строки и j-го столбца, для автомата Мили соответствует входному сигналу x k, вызывающему переход из состояния z i в состояние z j, и выходному сигналу y s, выдаваемому при этом переходе. Дискретно-детерминированные модели (F-схемы)

27 Пример 1. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид: x 2 / y 1 – x 1 / y 1 C 1 = x 1 / y 1 –x 2 / y 2. x 1 / y 2 x 2 / y 1 – Если переход из состояния z i в состояние z j происходит под действием нескольких сигналов, то элемент матрицы c ij представляет собой множество пар вход-выход для этого перехода, соединенных знаком дизъюнкции. Дискретно-детерминированные модели (F-схемы)

28 Для F-автомата Мура элемент с ij равен множеству входных сигналов на переходе (z i, z j ), а выход описывается вектором выходов (z 0 ) (z 1 ) …… = (z k ), …… (z K ) i-я компонента вектора – выходной сигнал, отмечающий состояние z i. Дискретно-детерминированные модели (F-схемы)

29 Пример 2. Для F-автомата Мура F2, рассмотренного выше, матрицы соединений и вектор выходов имеют вид: –x 1 – x 2 – –x 2 ––x 1 C 2 =–x 2 ––x 1 x 2 –x 1 –– у 1 =у 3 у 2 у 3 Дискретно-детерминированные модели (F-схемы)

30 Для детерминированных автоматов выполняется условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания F-автомата это означает, что в графе автомата из любой вершины не могут выходить два и более ребра, отмеченные одним и тем же входным сигналом. А в матрице соединений автомата С в каждой строке любой входной сигнал не должен встречаться более одного раза. Дискретно-детерминированные модели (F-схемы)

31 Для F-автомата состояние z k называется устойчивым, если для любого входа x i X, для которого (z k, x i ) = z k, имеет место (z k, x i ) = у k. F-автомат называется асинхронным, если каждое его состояние z k Z устойчиво. С помощью F-автомата можно описать объекты, для которых характерно наличие дискретных состояний, и дискретный характер работы во времени: - элементы и узлы ЭВМ, - устройства контроля, регулирования и управления, - системы временной и пространственной коммутации в технике обмена информацией и т.д. Дискретно-детерминированные модели (F-схемы)

32 Основные соотношения Вероятностный автомат – Р-схема (англ. probabilistic automat) – дискретный потактовый преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем, и может быть описано статистически. Используя математическое описание для F-автомата, формализуем Р-автомат. Дискретно-стохастические модели (Р-схемы)

33 Автомат детерминированного типа был формализован в виде множества G с элементами всевозможных пар (x i, z s ), где x i и z s – элементы входного подмножества Х и подмножества состояний Z соответственно, а также двух функций и, осуществляющих отображения G Z и G Y : F = Дискретно-стохастические модели (Р-схемы)

34 Для более общей математической схемы: Ф – множество всевозможных пар вида (z k, y i ), где у i – элемент выходного подмножества Y. Любой элемент множества G с элементами всевозможных пар (x i, z s ) индуцирует на множестве Ф некоторый закон распределения следующего вида: Элементы из Ф: (z 1, y 2 ) (z 1, y 2 )... (z K, y J – 1 ) (z K, y J ) Элементы из G (x i, z s ): b 11 b b K(J – 1) b KJ При этом b kj = 1, где b kj – вероятности перехода автомата в состояние z k и появления на выходе сигнала y j, если он был в состоянии z s и на его вход в этот момент времени поступил сигнал x i. Дискретно-стохастические модели (Р-схемы)

35 Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда вероятностный автоматом (Р-схема) формализуется в виде P = Дискретно-стохастические модели (Р-схемы)

36 Для вероятностного автомата Мили соотношение b kj = q j z k, где для всех k и j элементы множества G (x i, z s ) индуцируют некоторые законы распределения на подмножествах Y и Z: Элементы из Yy 1 y 2...y J-1 y J (x i, z s )q 1 q 2...q J-1 q J Элементы из Zz 1 z 2...z K-1 z K (x i, z s )z 1 z 2 z K-1 z K z k = 1 и q j = 1, где z k и q j – вероятности перехода Р-автомата в состояние z k и появления выходного сигнала y k при условии, что Р-автомат находился в состоянии z s и на его вход поступил входной сигнал x i. При этом выполняется условие независимости распределений для нового состояния Р-автомата и его выходного сигнала. Дискретно-стохастические модели (Р-схемы) Возможные приложения P-схемы

37 Для вероятностного автомат Мура соотношение b ki = z k s i, где для всех k и i каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов: Элементы из Yy 1 y 2...y K-1 y K z k s 1 s 2...s I-1 s I s i = 1, где s i – вероятность появления выходного сигнала y i при условии, что Р-автомат находился в состоянии z k. Тогда определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы. Дискретно-стохастические модели (Р-схемы)

38 Частный случай Р-автомата – автомат, у которого переход в новое состояние или выходной сигнал определяются детерминировано. Если выходной сигнал Р-автомата определяется детерминировано, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным. Р-автоматы могут использоваться как генераторы марковских последовательностей. Дискретно-стохастические модели (Р-схемы)

39 Пример. Пусть задан Y-детерминированный P-автомат 00,5000,5 0001,00 Р р = 000,7500,25 000,400,6 01,0000 Zz 0 z 1 z 2 z 3 z 4 Y00110 Дискретно-стохастические модели (Р-схемы)

40 На рис. 2.5 показан ориентированный граф переходов этого автомата. Вершины графа сопоставляются состояниям автомата, а дуги – возможными переходами из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода p ij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями. Требуется оценить суммарные финальные вероятности пребывания этого P-автомата в состояниях z 2 и z 3. Дискретно-стохастические модели (Р-схемы)

41 Рис Граф вероятностного автомата Дискретно-стохастические модели (Р-схемы) 0 0,5 1,0 0,4 1, ,6 0,25 0, z0z0 z4z4 z3z3 z2z2 z1z1

42 При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние z 0 можно не учитывать, так как начальное распределение не оказывает влияние на значения финальных вероятностей. Тогда имеем 001,00 C= 00,7500,25 00,400,6 1,0000 C = c k = (c 1, c 2, c 3, c 4 ), где с k – финальная вероятность пребывания Р-автомата в состоянии z k. Дискретно-стохастические модели (Р-схемы)

43 Получаем систему уравнений с 1 = с 4 ; с 2 =0,75 с 2 +0,4 с 3 ; с 3 = с 1 ; с 4 = 0,25 с 2 +0,6 с 3 Добавим к этим уравнениям условие нормировки с 1 + с 2 + с 3 + с 4 = 1. Тогда, решая систему уравнений, получим с 1 = 5/23, с 2 = 8/23, с 3 = 5/23, с 4 = 5/23. Таким образом, с 2 + с 3 = 13/23 = 0,5652. Т.е. при бесконечной работе заданного Y-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652. Дискретно-стохастические модели (Р-схемы)

44 изучили особенности дискретно-детерминированного подхода при построении математических моделей на основе теории автоматов; научились строить формальную модель объекта, используя типовую математическую F-схему; изучили особенности дискретно-стохастического подхода при построении математических моделей на основе теории автоматов; научились строить формальную модель объекта, используя типовую математическую Р -схему. Выводы и заключение по лекции:

45 1. Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб. для вузов. 5-е изд., перераб. и доп. М.: Высш. шк., с.: ил. 2. Тарасик В.П. Математическое моделирование технических систем: Учебник для вузов. М.: Наука, с. 3. Список дополнительной литературы по теме: Дружинина О.Г. Преподавание дисциплины «Моделирование систем»: методическая разработка по дисциплине «Моделирование систем»/ О.Г. Дружинина. Екатеринбург: ГОУ ВПО УГТУ-УПИ, с. Перечень источников: