11) Математические схемы дискретно-детерминированных систем (f-схемы)[finite automate]

Если x,y,z – конечны, то автомат называется конечным

Абстрактно: F=<X,Y,Z,φ,ψ>, где X – входной алфавит, Y – выходной алфавит, Z – алфавит состояний, φ(x,z) – функция переходов, ψ(x,z) – функция выходов

Автомат функционирует в дискретном автоматическом времени, задаваемом тактами. Каждому такту соответствует значения x(t), y(t), z(t), x€X, y€Y, z€Z

В момент t будучи в состоянии z(t) автомат способен воспринимать x(t), выдавать y(t) = ψ(x(t),z(t)); z(t+1) = φ(x(t),z(t))

Автоматы бывают:

1. Первого рода(автомат Мили)

y(t) = ψ(x(t),z(t))

z(t+1) = φ(x(t),z(t)) t=0,1,2…

2. Автомат второго рода

y(t) = ψ(x(t-1),z(t))

z(t+1) = φ(x(t),z(t)) t=1,2…

3. Автомат Мура

y(t) = ψ(z(t)) t=0,1,2…

Разделяют автоматы с памятью и без памяти. Автоматы с памятью имеют более 1 состояния. Без памяти – 1 состояние – комбинационные/логические схемы(y(t) = ψ[x(t)])

По характеру отсчета времени – делят на синхронные и асинхронные

К синхронным моментам времени в которые автомат считывает/воспринимает входные сигналы определяются синхронизирующими сигналами. Асинхронный автомат считывает входной сигнал непрерывно, и может за время его действия несколько раз менять состояние, пока не перейдет в устойчивое состояние.

Способы задания F-автомата: табличный, графический (граф), матричный

12) Математические схемы дискретно-стохастических систем (p-схемы)[probabilistic]

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

Пусть элементы из множества G, состоящий из пар (x_i,z_s) индуцируют на множестве Ф, состоящем из пар (z_k,y_j) некоторый закон распределения.

,

где , b_jk – вероятность перехода автомата в состояние z_k и появление сигнала y_j, если на входе x_i и автомат был в z_s.

Число таких распределений, представлено в виде таблиц, равно числу элементов множества G. B – множество таблиц (отображение), тогда: P=<X,Y,Z,B>

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

Элементы Y на вероятности их появления ( ), где q_i – вероятность появления на выходе сигнала y_i.

Элементы Z на вероятности их перехода ( ), где с_k – вероятность перехода автомата в состояние z_k.

Рассмотрим частные случаи P-автомата:

Y-детерминированный P-автомат (выходной сигнал детерминирован)

Z-детерминированный P-автомат (переход в новое состояние детерминирован)

13) Марковские случайные процессы. Эргодические цепи Маркова

Марковские процессы (процессы без последействия) – разновидность случайных процессов, описывающих систему с дискретными состояниями: если система в момент n находится в состоянии j, то вероятность её перехода в момент n+1 в состояние k зависит только лишь от значений n,j,k и не зависит от того, в каких состояниях система была в более раннее, чем n моменты времени.

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

Дискретный Марковский процесс с дискретным временем называется дискретной цепью Маркова. Он характеризуется тем, что переходы возможны лишь в дискретные моменты времени t₀,t₁,t₂.

В Марковском процессе с непрерывным временем, переход возможен в любой, наперед неизвестный момент времени.

Цель Марковских процессов описывается матрицей переходов за 1 шаг:

где P_ij – вероятность перехода за один шаг из состояния z_i в z_j. Марковская цепь однородна, если P_ij не зависит от шага.

Равенство Маркова (реккурентная формула для определения вероятностей состояния системы после k-ого шага, через вероятность после k-1):

Свойства эргодической цепи Маркова:

Эргодическое состояние – если возвратное состояние не является ни нулевым, ни периодическим. Вероятность того что система когда-нибудь вернется в состояние j:

Если f_j=1, то j – возвратное состояние, а если f_j<1, то j – невозвратное состояние.

Также различают при fj=1: если среднее время между пребываниями системы в состоянии стремится в бесконечность, то состояние j – возвратное ненулевое, если это время конечная величина, то j – возвратное нулевое

Если ||P_ij|| - не содержит нулевых элементов, для такой цели характерно то, что при большом числе шагов n->бесконечности, наступает стационарный режим.

Предельная вероятность нахождения в состоянии j: