ФЭНДОМ


Дискретно- детерминированные модели ( F - схемы )Править

Основным видом дискретно- детерминированных моделей является конечный автомат.

Конечным автоматом  называют дискретный преобразователь информации, способный под воздействием входных сигналов переходить из одного состояния в другое и формировать сигналы на выходе. Это автомат с памятью. Для организации памяти в описание автомата вводят автоматное время и понятие состояние автомата.

Понятие «состояние» автомата означает, что выходной сигнал автомата зависит не только от входных сигналов в данный момент времени, но и учитывает входные сигналы, поступающие ранее. Это позволяет устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входных сигналов.

Всякий переход автомата из одного состояния в другое возможен не ранее, чем через дискретный интервал времени. Причем сам переход считается, происходит мгновенно, то есть не учитывают переходные процессы в реальных схемах.

Существует два способа введения автоматного времени по которому автоматы делятся на синхронные и асинхронные.

В синхронных автоматах моменты времени, в которых фиксируются изменения состояний автомата, задаются специальным устройством - генератором синхросигналов. Причем сигналы поступают через равные интервалы времени - $ \Delta t $ . Частота тактового генератора выбирается такой, чтобы любой элемент автомата успел закончить свою работу до появления очередного импульса.

В асинхронном автомате моменты перехода автомата из одного состояния в другое заранее не определены и зависят от конкретных событий. В таких автоматах интервал дискретности является переменным.

Также существуют детерминированные и вероятностные автоматы.

В детерминированных автоматах поведение и структура автомата в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата.

В вероятностных автоматах они зависят от случайного выбора.

Абстрактно конечный автомат можно представить как математическую схему (F - схему), которая характеризуется шестью видами переменных и функций:

  1. конечное множество x(t) входных сигналов (входной алфавит);
  2. конечное множество y(t) выходных сигналов (выходной алфавит);
  3. конечное множество z(t) внутренних состояний (алфавит состояний);
  4. начальное состояние автомата z0 , ;
  5. функция переходов $ \varphi(z,x) $ автомата из одного состояния в другое;
  6. функция выходов $ \psi(z,x) $ автомата.

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

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

Следовательно, работа конечного автомата происходит по следующей схеме: на каждом t - ом такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который автомат реагирует переходом на (t+1)-ом такте в новое состояние z(t+1) и выдачей некоторого выходного сигнала.

В зависимости от способа определения выходного сигнала абстрактные конечные автоматы (синхронные) подразделяются на два типа:

1) F - автомат первого рода, также называется автомат Мили:

$ \left\{\begin{matrix}z(t+1)=\varphi[z(t),x(t)],t=0,1,2,...;\\ y(t)=\psi [z(t),x(t)],t=0,1,2,...;\end{matrix}\right. $

File5 html 26087099

Рис.1 Граф автомата Мили

2) F - автомат второго рода:

$ \left\{\begin{matrix}z(t+1)=\varphi[z(t),x(t)],t=0,1,2,...;\\ y(t)=\psi [z(t-1),x(t)],t=1,2,3,...;\end{matrix}\right. $

Для которого: $ y(t)=\psi[z(t)],t=0,1,2,...; $

File5 html 618e381b

Рис.2 Граф автомата Мура

называется автомат Мура - функция выходов не зависит от входной переменной x(t).

Чтобы задать конечный F - автомат, необходимо описать все элементы множества $ F=<z,x,y,\psi,z_0> $ .

Существует несколько способов задания работы F - автоматов среди которых наибольшее применение нашли табличный, графический и матричный.

Дискретно-стохастические модели (P- схемы)Править

Р-схемы принято называть вероятностными автоматами, с помощью которых можно определить дискретные преобразования информации с памятью.

Вероятностный автомат (англ, probabilistic automata) (ВА) - это дискретный потактный преобразователь информации с памятью, функционирова­ние которого в каждом такте зависит только от состояния памяти нем и может быть описано статистически.

Схемы вероятностных автоматов (Р-схем) применяются:

  • в проектировании дискретных систем, проявляющих статистически закономерное случайное пове­дение;
  • в определении алгоритмических возможностей систем;
  • в обосновании границ целесообразности их использования;
  • в решении задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.

Математическое понятие Р-автомата формируется на понятиях, введенных для F'-автомата.

Пусть множество G'элемен­тами которого являются всевозможные пары где xi' и zs — элементы входного подмножестваX' и подмножества состояний Z соответственно . Если существуют две такие функции  и то с их помощью осуществляются отображения  и , то говорят, что  (1) определяет конечный автомат детерминиро­ванного типа.

Введем более общую математическую схему. Пусть Ф — множество всевозможных пар вида ('zk', 'yj'), где yj' — элемент выходного подмножества Y'т.е. . Пусть в любой элемент множества G' индуцирует на множестве Ф некоторый закон распределения следующего вида:

Таблица 1

Элементы из Ф

•••

('z'1', 'y'1')

•••

('z'1', 'y'2')

•••

('zK', 'yJ-1')

('zK', 'yJ')

('zk', 'yj')

•••

b11

b12

bk(j-1)

bkj

При этом , (2) где bkj' — вероятности перехода автомат в состояние zk' и выдаче на выходе сигнала yj, если автомат был в состоянии z.S, и на его вход в момент времени поступил сигнал хi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G'.

 Обозначим множество этих таблиц через В. Тогда четверка элементов  (3) называ­ется вероятностным автоматом (Р-автоматом).

Вероятностный автомат Мили

Пусть элементы множества G' индуцируют некоторые законы распределения на подмножествах Y' и Z, которые можно представить соответственно в виде:

Таблица 2

Элементы из Y

•••

y'1

y2

•••

YJ-1

y J

•••

q1

q2

•••

q J-1

q J

Элементы из Z

•••

z1

z2

•••

zK-1

zK

•••

n1

n2

•••

n K-1

n K

При этом  и (4)— вероятности перехода Р-автомата в состояние zk и выдачи выходного сигнала yk' при условии, что Р-автомат находился в состоянии zS' и на его вход поступил входной сигнал xt'.

Если для всех k' и j имеет место соотношение (5)то такой автомат называется вероятностным автоматом Мили.Представленное тре­бование означает выполнение условия независимости распределе­ний для нового состояния Р-автомата и его выходного сигнала.

Вероятностный автомат Мура

Пусть выходной сигнал Р-автомата зави­сит лишь от того состояния, в котором находится автомат в данном такте работы, каждый элемент выходного подмножества Y' индуцирует распределение вероятностей выходов, имеющее следующий вид:

Таблица 3

Элементы из Ф

•••

yl

у2

•••

yk-1

yk

('zk', 'yj')

•••

s'1

S'2

•••

SI-1

SI

Здесь ,(6) где Si, — вероятность появления сигнала на выходе yi' при условии, что Р-автомат находился в состоянии zk'.

Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Такой автомат называется Y-детерминированным вероятност­ным автоматом.

Если состояние Р-автомата определяется детерменированно, то такой автомат называется Z-детерминированным вероятност­ным автоматом.

Аналогично, Z-детерминированным вероятност­ным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.