ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ

Лекция 10

(Р-СХЕМЫ)

Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогич­ной рассмотренным в разделе 3 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастическиих) автома­тах.

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

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

Введем математическое понятие Р-автомата, используя поня­тия, введенные для F-автомата. Рассмотрим множество G, элемен­тами которого являются всевозможные пары (x_i, z_s), где x_i и z_s — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции φ и ψ, то с их помощью осуществляются отображения G→Z и G→Y, то говорят, что F= <Z, X, Y, φ, ψ) определяет автомат детерминиро­ванного типа.

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

При этом где b_kj вероятности перехода автомата в состояние z_k и появления на выходе сигнала y_j, если он был в состоянии z_s и на его вход в этот момент времени поступил сигнал х . Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P=<Z, X, Y, В> называется вероятностным автоматом (Р- автоматом).

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

При этом и , где z_k и q_k - вероятности перехода Р- автомата в состояние z_k и появления выходного сигнала у_к при условии, что Р- автомат находился в состоянии z_s, и на его вход поступил входной сигнал х_i.

Если для всех к и j имеет место соотношение q_kz_i=b_kj, то такой Р-автомат называется вероятностным автоматом Мили. Это тре­бование означает выполнение условия независимости распределе­ний для нового состояния Р-автомата и его выходного сигнала.

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

Здесь , где S_i — вероятность появления выходного сигнала y_i при условии, что Р- автомат находился в состоянии z_k.

Возможные приложения. Если для всех k и i имеет место соот­ношение z_ks_i=b_ki то такой Р- автомат называется вероятностным автоматом Мура. Понятие Р- автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом, задаваемым F=<Z, X, Y, φ, ψ>. Частным случаем Р- автомата, задаваемого как Р= <Z, X, Y, В), являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал Р- автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятност­ным автоматом. Аналогично, Z-детерминированным вероятност­ным автоматом называется Р- автомат, у которого выбор нового состояния является детерминированным.

Подобные Р- автоматы могут испо­льзоваться как генераторы марковских последовательностей, которые необхо­димы при построении и реализации про­цессов функционирования систем S или воздействий внешней среды Е.

Для оценки различных характери­стик исследуемых систем, представляе­мых в виде Р- схем, кроме рассмотрен­ного случая аналитических моделей мо­жно применять и имитационные модели, реализуемые, например, методом статического моделирования.