Дискретно-стохастические модели (P-схемы)
Изучение вероятностного автомата или дискретного потактного преобразователя информации с памятью. Математическое понятие Р-автомата. Вероятностный автомат Мили и Мура. Оценка суммарных финальных вероятностей пребывания Р-автомата в разных состояниях.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 48,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (P-схемы)
Вероятностный автомат [англ, probabilistic automat) (ВА) - это дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти нем и может быть описано статистически.
Схемы вероятностных автоматов (Р-схем) применяются:
- в проектировании дискретных систем, проявляющих статистически закономерное случайное поведение;
- в определении алгоритмических возможностей систем;
- в обосновании границ целесообразности их использования;
- в решении задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям.
Математическое понятие Р-автомата формируется на понятиях, введенных для F-автомата.
Пусть множество G, элементами которого являются всевозможные пары где xi и zs -- элементы входного подмножества X и подмножества состояний Z соответственно . Если существуют две такие функции и , то с их помощью осуществляются отображения и , то говорят, что (1) определяет конечный автомат детерминированного типа.
Введем более общую математическую схему. Пусть Ф -- множество всевозможных пар вида (zk, yj), где yj -- элемент выходного подмножества Y, т.е. . Пусть в любой элемент множества G индуцирует на множестве Ф некоторый закон распределения следующего вида:
Таблица 1
|
Элементы из Ф |
*** |
(z1, y1) |
*** |
(z1, y2) |
*** |
(zK, yJ-1) |
(zK, yJ) |
|
|
(zk, yj) |
*** |
b11 |
b12 |
bk(j-1) |
bkj |
При этом , (2) где bkj -- вероятности перехода автомат в состояние zk и выдаче на выходе сигнала yj, если автомат был в состоянии z.S, и на его вход в момент времени поступил сигнал хi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G.
Обозначим множество этих таблиц через В. Тогда четверка элементов (3) называется вероятностным автоматом (Р-автоматом).
Вероятностный автомат Мили
Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, которые можно представить соответственно в виде:
Таблица 2
|
Элементы из Y |
*** |
y1 |
y2 |
*** |
YJ-1 |
y J |
|
|
*** |
q1 |
q2 |
*** |
q J-1 |
q J |
||
|
Элементы из Z |
*** |
z1 |
z2 |
*** |
zK-1 |
zK |
|
|
*** |
1 |
2 |
*** |
K-1 |
K |
При этом и (4)-- вероятности перехода Р-автомата в состояние zk и выдачи выходного сигнала yk при условии, что Р-автомат находился в состоянии zS и на его вход поступил входной сигнал xt.
Если для всех k и j имеет место соотношение (5), то такой автомат называется вероятностным автоматом Мили. Представленное требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.
Вероятностный автомат Мура
Пусть выходной сигнал Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы, каждый элемент выходного подмножества Y индуцирует распределение вероятностей выходов, имеющее следующий вид:
Таблица 3
|
Элементы из Ф |
*** |
yl |
у2 |
*** |
yk-1 |
yk |
|
|
(zk, yj) |
*** |
s1 |
S2 |
*** |
SI-1 |
SI |
Здесь ,(6) где Si, -- вероятность появления сигнала на выходе yi при условии, что Р-автомат находился в состоянии zk.
Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Такой автомат называется Y-детерминированным вероятностным автоматом.
Если состояние Р-автомата определяется детерменированно, то такой автомат называется Z-детерминированным вероятностным автоматом.
Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.
Рассмотрим пример У-детерминированного Р-автомата
Пусть У-детерминированный Р-автомат, задан таблицей переходов.
Таблица 4
|
zk |
zk |
|||||
|
z1 |
z2 |
zK-1 |
zk |
|||
|
z1 |
p11 |
p12 |
p1(K-1) |
p1K |
||
|
z2 |
p21 |
P22 |
p2(K-1) |
p2K |
||
|
p3(K-1) |
p3K |
|||||
|
zk |
pK1 |
pK1 |
pK(K-1) |
pK |
где pij - вероятность перехода автомата из состояния zi в состояние zj
Можем записать
(7)
Таблица выходов представлена следующим образом:
Таблица 5
|
Z.... z1 |
z2.... zk- |
zk |
|
|
Y.... уi1 |
уi2... yik-1 |
yik |
Первую из этих таблиц можно представить в виде квадратной матрицы размерности К x К, которая называется матрицей переходных вероятностей или просто матрицей переходов Р-автомата. В общем случае матрица переходов имеет вид
(8)
Для полного описания У-детерминированного Р-автомата необходимо задать начальное распределение вероятностей вида
Таблица 6
|
Z.... z1 |
z2.... zk- |
zk |
|
|
D.... d1 |
d2.... dK-1 |
dK |
где dK -- вероятность того, что в начале работы автомат находится в состоянии zk
При этом . (9)
Будем предполагать, что до начала работы (до нулевого такта времени) Р-автомат всегда находится в состоянии z0, в нулевом такте времени меняет свое состояние в соответствии с распределением D. Дальнейшая смена состояний Р-автомата определяется матрицей переходов РР. Информацию о начальном состоянии Р-автомата удобно внести в матрицу РР/, увеличив ее размерность до (10). При этом первая строка такой матрицы, сопоставляемая состоянию z0, будет иметь вид (0, dt, d2,......, dK), а первый столбец будет нулевым.
- сопоставляется со состоянием z0 (11)
Описанный У-детерминированный Р-автомат можно задать в виде ориентированного графа, вершины которого сопоставляются состояниям автомата, а дуги -- возможным переходам из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода рij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями.
Рассмотрим следующий пример. У-детерминированный Р-автомат задан матрицей
(12)
Таблица 7
|
Z |
z0 |
z1 |
z2 |
z3 |
z4 |
|
|
Y |
0 |
0 |
1 |
1 |
0 |
Граф переходов имеет вид (Рис.1).
Рис. 1
вероятностный автомат дискретный преобразователь
Требуется оценить суммарные финальные вероятности пребывания этого Р-автомата в состояниях z2 и z3.
При использовании аналитического подхода можно записать известные соотношения из теории марковских цепей и получить систему уравнений для определения финальных вероятностей. Начальное состояние za можно не учитывать, так как начальное распределение не оказывает влияния на значения финальных вероятностей. Тогда имеем
- матрица финальных состояний (13)
(14), где ck - финальная вероятность пребывания Р-автомата в состоянии zk.
Получаем систему уравнений
(15)
Добавим к этим уравнениям условие нормировки с1+с2 + с3 + с4 = 1 (16). Тогда, решая систему уравнений, получим с1 = 5/23, с2=8/23, c3 = 5/23, с4 = 5/23 (17). Таким образом, с2+с3= 13/23 =0,5652 (18). Другими словами, при бесконечной работе заданного в этом примере У-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652.
Подобные Р-автоматы могут использоваться как генераторы марковских последовательностей, которые необходимы при построении и реализации процессов функционирования систем S или воздействий внешней среды Е.
Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, кроме рассмотренного случая аналитических моделей можно применять и имитационные модели, реализуемые, например, методом статистического моделирования.
Размещено на Allbest.ru
...Подобные документы
Имитационное моделирование на цифровых вычислительных машинах. Разработка модели процесса инвестирования по заданному его математическому описанию и структуре гибридного автомата, реализующего данную модель. Запуск пакета MVS и создание нового проекта.
курсовая работа [1,3 M], добавлен 27.02.2015Нахождение вероятности за определенный промежуток времени. Плотность распределения вероятностей. Математическое ожидание и среднеквадратическое отклонение. Интегральная теорема Лапласа, распределение Стьюдента. Исправленная выборочная дисперсия.
контрольная работа [110,5 K], добавлен 28.05.2012Статистические модели принятия решений. Описание моделей с известным распределением вероятностей состояния среды. Рассмотрение простейшей схемы динамического процесса принятия решений. Проведение расчета вероятности произведенной модификации предприятия.
контрольная работа [383,0 K], добавлен 07.11.2011Стохастические игры как разновидность многошаговых игр, в которых переход от одной позиции к другой совершается с определенной вероятностью. Расчетные методы их решения. Разработка и тестирование программного средства для решения игры "Герб-Решетка".
контрольная работа [364,0 K], добавлен 20.02.2013Множественная корреляция и линейная регрессия. Оценка прогнозных качеств модели. Простейшие методы линеаризации. Вероятностный эксперимент, событие или вероятность. Фиктивные переменные в регрессионных моделях. Системы эконометрических уравнений.
курс лекций [2,0 M], добавлен 13.02.2014Построение и изучение математической модели случайного стационарного эргодического процесса с вероятностными характеристиками: ожидание и дисперсия. Построение графиков динамики изменения эмпирических данных и гистограмм распределения для всех выборок.
курсовая работа [217,2 K], добавлен 18.03.2012Модели движения людских потоков на основе уравнений динамики жидкости и газов, основанные на социальных силах и теории клеточных автоматов. Численное исследование полевой стохастической дискретно-непрерывной модели движения людей на примере "коридор".
дипломная работа [1,1 M], добавлен 18.12.2013Динамические, стохастические, дискретные модели имитационного моделирования. Предпосылки, технологические этапы машинного моделирования сложной системы. Разработка имитационной модели автоматизированного участка обработки деталей, ее верификация.
дипломная работа [224,3 K], добавлен 05.09.2009Составление математической модели транспортной задачи закрытого типа, представленной в матричной форме, с ограничениями пропускной способности. Поиск оптимального плана, при котором выполняется условие наименьшего суммарного пробега порожних вагонов.
контрольная работа [60,5 K], добавлен 20.03.2014Сущность и содержание метода моделирования, понятие модели. Применение математических методов для прогноза и анализа экономических явлений, создания теоретических моделей. Принципиальные черты, характерные для построения экономико-математической модели.
контрольная работа [141,5 K], добавлен 02.02.2013Понятие имитационного моделирования, применение его в экономике. Этапы процесса построения математической модели сложной системы, критерии ее адекватности. Дискретно-событийное моделирование. Метод Монте-Карло - разновидность имитационного моделирования.
контрольная работа [26,7 K], добавлен 23.12.2013Статистический анализ в Excel. Очистка информации от засорения, проверка закона распределения, корреляционный и регрессионный анализ двумерной и трехмерной модели. Математическая модель и решение задачи оптимального управления экономическим процессом.
контрольная работа [447,2 K], добавлен 04.11.2009Теоретические основы первичной обработки статистической информации. Особенности определения минимального числа объектов наблюдения при оценке показателей надежности. Анализ вероятностной бумаги законов нормального распределения и распределения Вейбулла.
курсовая работа [163,5 K], добавлен 22.03.2010Создание математической модели для оперативного мониторинга продажи услуг в Региональном филиале ОАО "Сибирьтелеком"-"Томсктелеком". Преимущества, стоимость и основные перспективы развития услуг ISDN. Математическое моделирование dial-up подключений.
дипломная работа [2,8 M], добавлен 20.09.2010Изучение экономических показателей и особенностей повышения эффективности химического производства, которое достигается различными методами, одним из которых является метод математического моделирования. Анализ путей снижения затрат на производство.
курсовая работа [41,2 K], добавлен 07.09.2010Моделирование приращений цены, процентной ставки, кредитного риска. Хеджирование и динамическое управление капиталом. Определение величины скачков цен. Модели с использованием байесовского подхода (формула пересчета вероятностей). Алгоритм Монте-Карло.
презентация [263,4 K], добавлен 23.06.2015Разработка оптимального режима процесса получения максимального выхода химического вещества. Обоснование выбора методов получения математической модели и оптимизации технологического процесса. Входная и выходная информация, интерпретация результатов.
курсовая работа [114,9 K], добавлен 08.07.2013Сущность математического моделирования и формализации. Выявление управляемых и неуправляемых параметров. Математическое описание посредством уравнений, неравенств, функций и иных отношений взаимосвязей между элементами модели (параметрами, переменными).
курсовая работа [116,8 K], добавлен 17.12.2009Цель математического моделирования экономических систем: использование методов математики для эффективного решения задач в сфере экономики. Разработка или выбор программного обеспечения. Расчет экономико-математической модели межотраслевого баланса.
курсовая работа [1,3 M], добавлен 02.10.2009Построение имитационной схемы для модели Солоу и прослеживание ее динамики на протяжении 30 лет. Вычисление стационарного значения фондовооруженности. Проверка "золотого правила накопления". Изучение поведения модели при смене некоторых параметров.
лабораторная работа [722,3 K], добавлен 11.12.2012
