5. ДИСКРЕТНО-ДЕТЕРМИНИРОВАННЫЕ МОДЕЛИ (F-СХЕМЫ). ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (P-СХЕМЫ). ОСНОВНЫЕ СООТНОШЕНИЯ И ВОЗМОЖНЫЕ ПРИЛОЖЕНИЯ

Привет, Вы узнаете о том , что такое дискретно-детерминированные модели, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое дискретно-детерминированные модели, f-схемы , настоятельно рекомендую прочитать все из категории Моделирование информационных систем.

Особенности дискретно-детерминированного подхода на этапе формализации процесса функционирования систем рассмотрим на примере использования в качестве математического аппарата теории автоматов. Теория автоматов — это раздел теоретической кибернетики, в котором изучаются математические модели — автоматы. На основе этой теории система представляется в
виде автомата, перерабатывающего дискретную информацию и меняющего
свои внутренние состояния лишь в допустимые моменты времени, Понятие
«автомат» варьируется в зависимости от характера конкретно изучаемых систем, от принятого уровня абстракции и целесообразной степени общности.
Автомат можно представить как некоторое устройство (черный ящик),
на которое подаются входные сигналы и снимаются выходные и которое может
иметь некоторые внутренние состояния. Конечным автоматом называется автомат, у которого множество внутренних состояний и входных сигналов (а,
следовательно, и множество выходных сигналов) являются конечными множествами.
Абстрактно конечный автомат (англ. finite automata) можно представить
как математическую схему (F-схему), характеризующуюся шестью элементами:
конечным множеством X входных сигналов (входным алфавитом); конечным
множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием
z0  Z
; функцией переходов
z, x
; функцией выходов
z, x. Автомат, задаваемый F-схемой

– функционирует в дискретном автоматном времени, моментами которого являются такты, т.е., примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и вы-
ходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-му такту при t=0, 1, 2, ..., через
zt, xt, yt. При этом
  0 0
z  z , zt Z , xt X , ytY .
Абстрактный конечный автомат имеет один входной и один выходной
каналы. В каждый момент t = 0, 1, 2, ... дискретного времени F-автомат находится в определенном состоянии
zt
, в начальный момент времени t=0 он всегда находится в начальном состоянии
  0 0
z  z
. В момент 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 .
Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного алфавита Y.
Другими словами, если на вход конечного автомата, установленного в начальное состояние
0
z
, подавать в некоторой последовательности буквы входного
алфавита
x0, x1, x2,..., т. е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита
y0, y1, y2,..., образуя
выходное слово.
Таким образом, работа конечного автомата происходит по следующей
схеме: в каждом t-м такте на вход автомата, находящегося в состоянии
zt
, подается некоторый сигнал
xt, на который он реагирует переходом в (t+1)-м такте в новое состояние
zt 1
и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для F-автомата 1-ого
рода, называемого также автоматом Мили,

(10)

(11)
для автомата 2-ого рода

Автомат 2-ого рода, для которого
yt zt, t  0,1, 2, ...
(14)
т. е. функция выходов не зависит от входной переменной
xt, называется автоматом Мура.
Таким образом, уравнения (10) — (14), полностью задающие F-автомат,
являются частным случаем уравнений (3) – (4), когда система S детерминированная и на ее единственный вход поступает дискретный сигнал X.
По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без –
обладают лишь одним состоянием.
По характеру отсчета дискретного времени конечные автоматы делятся
на синхронные и асинхронные. В синхронных F-aвmоматах моменты времени,
в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего
сигнала с учетом «считанного» и в соответствии с уравнениями (10) — (14)
происходит переход в новое состояние и выдача сигнала на выходе, после чего
автомат может воспринимать следующее значение входного сигнала. Об этом говорит сайт https://intellect.icu . Таким
образом, реакция автомата на каждое значение входного сигнала заканчивается
за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами. Асинхронный F-автомат считывает
входной сигнал непрерывно, и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины х, он может несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в
устойчивое, которое уже не может быть изменено данным входным сигналом.
Чтобы задать конечный F-автомат, необходимо описать все элементы
множества
0 F  Z, X,Y,,,z , т. е. входной, внутренний и выходной алфавиты, а
также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние
0
z , в котором автомат находился в момент времени
t=0. Существует несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный.
Простейший табличный способ задания конечного автомата основан на
использовании таблиц переходов и выходов, строки которых соответствуют
входным сигналам автомата, а столбцы — его состояниям. При этом обычно
первый слева столбец соответствует начальному состоянию
0
z . На пересечений
i- й строги и k-го столбца таблицы переходов помещается соответствующее
значение
  k i  z , x
функции переходов, а в таблице выходов — соответствующее
значение
  k i  z , x
функции выходов. Для F-автомата Мура обе таблицы можно
совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием
k
z
автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию, согласно (14), выходной сигнал
  k  z .
Описание работы F-автомата Мили таблицами переходов φ и выходов
ψ иллюстрируется табл. 1, а описание F-автомата Мура — таблицей переходов (табл. 2).

Табл. 1. Описание работы F-автомата Мили

Табл. 2. Описание работы F-автомата Мура

Пример. F-автомат Мили F1 с тремя состояниями, двумя входными и
двумя выходными сигналами приведен в табл. 3, а F-автомат Мура F2 — в табл. 4.
Табл. 3. F-автомат Мили F1

Табл. 4. F-автомат Мура F2

При другом способе задания конечного автомата используется понятие
направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг
графа, соответствующих тем или иным переходам автомата. Если входной сигнал
k
x
вызывает переход из состояния
i
z
, в состояние
j
z , то на графе автомата
дуга, соединяющая вершину
i
z
с вершиной
j
z
обозначается
k
x . Для того, чтобы
задать функцию выходов, дуги графа необходимо отметить соответствующими
выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал
k
x
действует на состояние
i
z , то, согласно сказанному, получается дуга, исходящая из
i
z
и помеченная
k
x
; эту дугу дополнительно отмечают выходной сигналом
  i k
y  z , x . Для автомата Мура аналогичная разметка
графа такова: если входной сигнал
k
x , действуя на некоторое состояние автомата, вызывает переход в состояние
j
z , то дугу, направленную в
j
z
и помеченную
k
x , дополнительно отмечают выходным сигналом
  j k
y  z , x .
На рис. 4 приведены заданные ранее таблицами Fавтоматы Мили F1 (а) и Мура
F2 (б) соответственно.
При решении задач моделирования систем часто более удобной формой является
матричное задание конечного
автомата. При этом матрица соединений автомата есть квадратная матрица
ij C  c , строки которой соответствуют исходным состояниям, а столбцы – состояниям перехода. Элемент
s
k
ij
y
x
c  , стоящий на пересечении i-й строки и j-го
столбца, в случае автомата Мили соответствует входному сигналу
k
x , вызывающему переход из состояния
i
z
в состояние
j
z , и выходному сигналу
s
y , выдаваемому при этом переходе. Если переход из состояния
i
z
в состояние
j
z
происходит под действием нескольких сигналов, элемент матрицы
ij c
представляет собой множество пар «вход-выход» для этого перехода, соединенных знаком дизъюнкции.
Для F-автомата Мура элемент
ij c
равен множеству входных сигналов
на переходе
i
z
и
j
z , а выход описывается вектором выходов
      K
y  z , z , ..., z  0 1
.
Необходимо отметить, что вообще на практике автоматы всегда являются асинхронными, а устойчивость их состояний обеспечивается, например, введением сигналов синхронизации. Однако на уровне абстрактной теории, когда
конечный автомат выступает в виде математической схемы для формализации
конкретных объектов без учета ряда второстепенных особенностей, удобным
оказывается оперировать с синхронными конечными автоматами.
Таким образом, понятие F-автомата в дискретно-детерминированном
подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов в автоматизированных системах обработки информации и управления.

Рис. 4. F-автоматы Мили и Мура соответственно

В качестве таких объектов в первую очередь следует назвать
элементы и узлы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией и т. д. Для всех перечисленных объектов характерно наличие дискретных
состояний и дискретный характер работы во времени, т. е. их описание с помощью F-схем является эффективным. Но широта их применения не означает
универсальности этих математических схем. Например, этот подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов.
Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования
исследуемой системы S. Так как сущность дискретизации времени при этом
подходе остается аналогичной конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.
В общем виде вероятностный автомат (англ. probabilistic automat)
можно определить как дискретный потактный преобразователь информации с
памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически.
Применение схем вероятностных автоматов (Р-схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.
Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары
  i s
x ,z . Если существуют две такие функции φ и ψ,
то с их помощью осуществляются отображения G→Z и G→Y, то говорят, что
F  Z, X,Y,,
определяет автомат детерминированного типа.
Введем в рассмотрение более общую математическую схему. Пусть Ф
— множество всевозможных пар вида
  k j
z , y . Потребуем, чтобы любой элемент
множества G индуцировал на множестве Ф некоторый закон распределения с
вероятностями
kj b
перехода автомата в состояние
k
z
и появления на выходе
j
y ,
если он находился в состоянии
s
z
и на его вход поступил сигнал
i
x
. При этом
справедливо
 

K
k
J
j
bkj
1 1
1.
Число таких распределений равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов
F  Z, X,Y,B
называется вероятностным автоматом (Р-автоматом).
Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, для которых


K
k
k
z
1
1
и


J
k
qk
1
1,
где
k
z , qk – вероятности перехода Р-автомата в состояние
k
z
и появления выходного сигнала
k
y
при условии, что P-автомат находился в состоянии
s
z
и на его вход поступил входной сигнал
i
x .
Если для всех k и j имеет место соотношение
k j bkj q z  , то такой Равтомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Равтомата и его выходного сигнала.
Пусть теперь определение выходного сигнала Р-автомата зависит
лишь от того состояния, в котором находится автомат в данном такте работы.
Другими словами, пусть каждый элемент выходного подмножества Y индуци-
рует распределение вероятностей выходов, для которых
1
1
 

I
i
i
s ,
i
s – вероятность появления выходного сигнала
i
y
при условии, что автомат находился в
состоянии
k
z .
Если для всех k и i имеет место соотношение
k i bki z s  , то такой Равтомат называется вероятностным автоматом Мура. Понятие Равтоматов Мили и Мура введено по аналогии с детерминированным Fавтоматом, задаваемым
F  Z, X,Y,, . Частным случаем Р-автомата, задаваемого как
F  Z, X,Y,B , являются автоматы, у которых либо переход в новое
состояние, либо выходной сигнал определяются детерминировано. Если выходной сигнал Р-автомата определяется детерминировано, то такой автомат
называется Y-детерминированным вероятностным автоматом. Аналогично,
Z-детерминированным вероятностным автоматом называется Р-автомат, у
которого выбор нового состояния является детерминированным.

Исследование, описанное в статье про дискретно-детерминированные модели, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое дискретно-детерминированные модели, f-схемы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Моделирование информационных систем