|
ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ(Р -СХЕМЫ) Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным в § 2.3 конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах. Основные соотношения. В общем виде вероятностный автомат (англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически. Применение схем вероятностных автоматов (P-схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям. Введем математическое понятие P-автомата,используя понятия, введенные для F-автомата. Рассмотрим множество G,элементами которого являются всевозможные пары , где и — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции φ и ψ,то с их помощью осуществляются отображения G→Z и G→Y,то говорят, что F= <Z, X, Y, φ, ψ> определяет автомат детерминированного типа. Введем в рассмотрение более общую математическую схему. Пусть Ф — множество всевозможных пар вида , где — элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида: Элементы из Ф … ... ... … … … При этом , где — вероятности перехода автомата в состояние и появления на выходе сигнала ,если он был в состоянии , и на его вход в этот момент времени поступил сигнал .Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P = <Z, X, Y, В> называется вероятностным автоматом (P-автоматом). Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z,что можно представить соответственно в виде: Элементы из Y … … … … Элементы из Z … … … … При этом и , где и — вероятности перехода P-автомата в состояние и появления выходного сигнала при условии, что P-автомат находился в состоянии и на его вход поступил входной сигнал . Если для всех и имеет место соотношение , то такой P-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния P-автомата и его выходного сигнала. Пусть теперь определение выходного сигнала P-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы. Другими словами, пусть каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующие вид: Элементы из Y … … … … Здесь , где — вероятность появления выходного сигнала при условии, что P-автомат находился в состоянии . Возможные приложения. Если для всех и имеет место соотношение ,то такой P-автомат называется вероятностным автоматом Мура. Понятие P-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом,задаваемым F=<Z, X, Y, φ, ψ>. Частным случаем P-автомата,задаваемого как Р=<Z, X, Y, В>,являются автоматы, у которых либо переход вновое состояние, либо выходной сигнал определяются детерминировано. Если выходной сигнал P-автомата определяется детерминировано, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется P-автомат, у которого выбор нового состояния является детерминированным.
Пример 2.4. Рассмотрим Y-детерминированный P-автомат, который задан таблицей переходов (табл. 2.6) и таблицей выходов:
В этихтаблицах — вероятность перехода P-автомата из состояния в состояние . При этом, как и ранее, . Первую из этих таблиц можно представать в виде квадратной матрицы размерности К x К,которую будем называть матрицей переходных вероятностей или просто матрицей переходов P-автомата. В общем случае такая матрица переходов имеет вид
Таблица 2.6
Для описания Y -детерминированного P-автомата необходимо задать начальное распределение вероятностей вида
Здесь - вероятность, того, что в начале работы P-автомат находится в состояния . При этом . Будем считать, что до начала работы (до нулевого такта времени) f всегда находится а состоянии z,n нулевой такт времени меняет состояние в соответствии с распределением D. Дальнейшая смена состояний P-автомата определяется матрицей переходов .Информацию о начальном состояния P-автомата удобно мести в матрицу , увеличив ее размерность до .При этом первая строка такой матрицы, сопоставляемая состоянию , будет иметь вид (0, d1, d2,..., …, dk), а первый столбец будет нулевым. Описанный Y -детерминированный P-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги — возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода ,а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями. Пример 2.5. Пусть задан Y -детерминированный P-автомат На рис. 2.5 показан граф переходов этого автомата. Требуется оценить суммарные финальные вероятности пребывания этого P-автомата в состояниях и . При использовании аналитического подхода можно записать известнее соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. При этом начальное состояние можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеем
где — финальная вероятность пребывания P-автомата в состоянии . Получаем систему уравнений Добавим к этим уравнениям условие нормировки . Тогда, решая систему уравнений, получим , , , . Таким образом, . Другим словами, при бесконечной работе заданного в этом примере Y -детерминированного P-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы равной 0,5652. Подобные P-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е. Для оценки различных характеристик исследуемых систем, представляемых в виде P-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.
Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|