Математические схемы вероятностных автоматов

Содержание

 

Введение 3

1 Основные подходы к построению математических моделей систем 3

2 Дискретно-стохастические модели 5

Библиографический список 17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Наибольшие затруднения  и наибольшие серьёзные ошибки при  моделировании возникают при переходе от содержательного к формальному описанию объектов исследования, что объясняется участием в этом творческом процессе коллективов разных специальностей: специалистов в области систем, которые требуется моделировать (заказчиков), и специалистов в области машинного моделирования (исполнителей). Эффективным средством для нахождения взаимопонимания между этими группами специалистов является язык математических схем, позволяющий во главу угла поставить вопрос об адекватности перехода от содержательного описания системы к ее математической схеме.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Основные  подходы к построению математических  моделей систем

 

 

 Введение понятия «математическая схема» позволяет рассматривать математику не как метод расчёта, а как метод мышления, как средство формулирования понятий, что является наиболее важным при переходе от словесного описания системы к формальному представлению процесса её функционирования в виде некоторой математической модели (аналитической или имитационной). При пользовании математической схемой исследователя системы  S в первую очередь должен интересовать вопрос об адекватности отображения в виде конкретных схем реальных процессов в исследуемой системе, а не возможность получения ответа (результата решения) на конкретный вопрос исследования.

Математическую  схему можно определить как звено  при переходе от содержательного  к формальному описанию процесса функционирования системы с учётом воздействия внешней среды, т. е. имеет место цепочка «описательная модель – математическая схема – математическая (аналитическая или имитационная) модель».

Каждая  конкретная система S характеризуется набором свойств, под которыми понимаются величины, отражающие поведение моделируемого объекта (реальной системы) и учитывающие условия её функционирования во взаимодействии с внешней средой (системой Е). При построении математической модели системы необходимо решить вопрос об её полноте. Полнота модели регулируется в основном выбором границы «система S – среда Е».

Модель  объекта моделирования, т. е. системы  S, можно представить в виде множества величин, описывающих процесс функционирования реальной системы и образующих в общем случае следующие подмножества:

а) совокупность входных воздействий на систему  x_i є X, i=1, n_x;

б) совокупность воздействий внешней среды v_l є V, l=1, n_v;

в) совокупность внутренних параметров системы h_k є H, k=1, n_H;

г) совокупность выходных характеристик системы  y_i є Y, j=1, n_y.

При этом в перечисленных подмножествах  можно выделить управляемые и неуправляемые переменные. В общем случае x_i , v_l, h_k, y_i являются элементами непересекающихся подмножеств и содержат как детерминированные, так и стохастические составляющие.

При моделировании  системы S входные воздействия, воздействия внешней среды Е и внутренние параметры системы являются независимыми (экзогенными) переменными, которые в векторной форме имеют соответственно вид (t)=(x₁(t), x₂(t), …, x_nX(t)); (t)=(₁(t), ₂(t),…, _nV(t)); (t)=h₁(t), h₂(t), …, h_nH(t)), а выходные характеристики системы являются зависимыми (эндогенными) переменными и в векторной форме имеют вид (t)=(y₁(t), y₂(t), …, y_nY(t)).

Процесс функционирования системы S описывается во времени оператором F_S, который в общем случае преобразует экзогенные переменные в эндогенные в соответствии с соотношениями вида

(t) = F_S(, , , t).                                      (1.1)

Совокупность  зависимостей выходных характеристик  системы от времени  y_i (t) для всех видов j= называется выходной траекторией (t). Зависимость (1.1) называется законом функционирования системы S и обозначается F_S. В общем виде закон функционирования системы F_S может быть задан в виде функции, функционала, логических условий, в алгоритмической и табличной формах или в виде словесного правила соответствия.

Весьма  важным для описания и исследования системы S является понятие алгоритма функционирования A_S, под которым понимается метод получения выходных характеристик с учётом входных воздействий (t), воздействий внешней среды  (t) и собственных параметров системы (t). Очевидно, что один и тот же закон функционирования F_S системы S может быть реализован различными способами, т. е. с помощью множества различных алгоритмов функционирования A_S.

Соотношения (1.1) являются математическим описанием  поведения объекта (системы) моделирования во времени t, т. е. отражают его динамические свойства. Поэтому математические модели такого вида принято называть динамическими моделями (системами).

Для статических  моделей математическая модель (1.1) представляет собой отображение  между двумя подмножествами свойств  моделируемого объекта Y и (X, V, H), что в векторной форме может быть записано как

= f (, , , ).                                            (1.2)

Соотношения (1.1) и (1.2) могут быть заданы различными способами: аналитически (с помощью  формул), графически, таблично. Такие  соотношения в ряде случаев могут быть получены через свойства системы S в конкретные моменты времени, называемые состояниями. Состояние системы S характеризуется векторами '= (z₁', z₂', …, z_k') и ''= (z₁'', z₂'', …, z_k''), где z₁'= z₁(t'), z₂'= z₂(t'), …, z_k'= z_k(t') в момент t''є (t₀, T); z₁''= z₁(t''), z₂''= z₂(t''),…, z_k''= z_k(t'') в момент t''є (t₀, T) и т. д.

Если  рассматривать процесс функционирования системы S как последовательную смену состояний z₁(t), z₂(t),…,  z_k(t), то они могут быть интерпретированы как координаты точки в k-мерном фазовом пространстве, причём каждой реализации процесса будет соответствовать некоторая фазовая траектория. Совокупность всех возможных значений состояний {} называется пространством состояний объекта моделирования Z, причём z_k є Z.

Состояния системы S в момент времени t_0t^*T полностью определяются начальными условиями ⁰=(, , …, ), входными воздействиями (t), внутренними параметрами (t) и воздействиями внешней среды (t), которые имели место за промежуток времени t^* - t₀, с помощью двух векторных уравнений

z(t) = Ф(⁰, , , , t);                                            (1.3)

(t) = F(, t).                                                   (1.4)

Первое  уравнение по начальному состоянию ⁰ и экзогенным переменным , , определяет вектор-функцию (t), а второе по полученному значению состояний (t) – эндогенные переменные на выходе системы (t). Таким образом, цепочка уравнений объекта «вход – состояния – выход» позволяет определить характеристики системы

(t) = F[Ф(⁰, , , , t)].                                       (1.5)

В общем  случае время в модели системы  S может рассматриваться на интервале моделирования (0, Т) как непрерывное, так и дискретное, т. е. квантованное на отрезки длиной t временных единиц каждый, когда T = mt, где m= – число интервалов дискретизации.

Таким образом, под математической моделью объекта (реальной системы) понимают конечное подмножество переменных {, , } вместе с математическими связями между ними и характеристиками (t).

Если  математическое описание объекта моделирования  не содержит элементов случайности  или они не учитываются, т.е. если можно считать, что в этом случае стохастическое воздействие внешней  среды (t) и стохастические внутренние параметры (t) отсутствуют, то модель называется детерминированной в том смысле, что характеристики однозначно определяются детерминированными входными воздействиями

  = f (, t).                                                      (1.6)

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

Приведённые математические соотношения представляют собой математические схемы общего вида и позволяют описать широкий класс систем. Однако в практике моделирования объектов в области системотехники и системного анализа на первоначальных этапах исследования системы рациональнее использовать типовые математические схемы: дифференциальные уравнения, конечные и вероятностные автоматы, системы массового обслуживания, сети Петри.

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

Таким образом, при построении математических моделей  процессов функционирования систем можно выделить следующие основные подходы: непрерывно-детерминированный; дискретно-детерминированный (конечные автоматы); дискретно стохастический (вероятностные автоматы); непрерывно-стохастический (системы массового обслуживания); обобщённый или универсальный (агрегативные системы).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Дискретно-детерминированные  модели

 

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

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

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

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

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

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

Элементы  из Ф   … (z₁, y₁)…  (z₁, y₂)…   …   (z_k, y_J-1)       (z_k, y_J)

      (x_i, z_k)            …      b₁₁           b₁₂               ...     b_K(J-1)             b_KJ

 

При этом   b_kj=1, где b_kj – вероятности перехода автомата в состояние z_k и появления на выходе сигнала y_J, если он был в состоянии z и на его вход в этот момент времени поступил сигнал x_i. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четвёрка элементов  F= называется вероятностным автоматом (Р-автоматом).

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

Элементы  из Y   …    y₁      y₂  …       y_J-1         y_J

  (x_i, z_J)                …    q₁          q₂  …       q_J-1         q_J