Моделирование динамики систем на основе цепей Маркова с дискретным временем

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОСТОЧНО–СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ ТЕХНОЛОГИИ И УПРАВЛЕНИЯ»

 

ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра систем информатики

 

 

 

Курсовая работа

(Д.660.2.1.12.013.012.11.ПЗ)

по дисциплине «Теория вычислительных процессов»

Тема: «Моделирование динамики систем на основе цепей Маркова с дискретным временем»

Вариант №16.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Улан-Удэ

2012 

ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ

___________________________________________________________________________

 

ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра систем информатики

 

ЗАДАНИЕ

на курсовую работу

 

Руководитель  работы  Дамбаева С.В.

Исполнитель                 Сундарон Д.Б.

Дата выдачи                " "

Содержание

 

Введение                        4

1. Теоретический раздел         5

       1.1 Определение цепи Маркова,  их классификация   5

       1.2 Невозвратные состояния      10

       1.3 Исследование динамики цепей  Маркова    15

2. Практический раздел        18

      2.1 Граф состояний и матрица вероятностей переходов  18

       2.2 Таблица векторов X(t)       19

       2.3 Программный алгоритм       27

       2.4 Выделение невозвратного и  эргодического множества  28

       2.5 Оценка вероятности пребывания  процесса в состоянии 31

3. Заключение         34

Список использованных источников      35

Приложение А – листинг программы      36

Приложение Б – результат выполнения программ    42

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Данная курсовая работа посвящена изучению цепей  Маркова. Работу можно разделить  на несколько подзадач:

1. Освоить основные положения теории конечных цепей Маркова с дискретным временем.

2. Научится составлять ЦМ для моделирования вычислительных систем и анализа динамики их функционирования.

3. Провести имитационное моделирование динамики ЦМ.

4. Провести расчет  характеристик производительности  вычислительных систем.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретический раздел
1. Определение цепи Маркова

 

Це́пь Ма́ркова — последовательность случайных событий, с конечным или счетным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого.

 

Формальное определение: конечная цепь Маркова - это набор элементов:

КЦМ = {Θ, S, P, X, X₀},   (1)

где

1. Θ - множество моментов времени. Мы будем рассматривать как множество дискретных моментов времени Θ={t_o,t₁,...,t_k,...}, так и непрерывное время,Θ=R, где R -  множество рациональных чисел. 
2. S= {S1,...,S_n}– конечное множество состояний. В каждый момент времени t_k система может находиться только в одном из состояний S_i. Этот факт мы будем обозначать как  S(t_k)=S_i, t_k принадлежит Θ, S_i принадлежит S.
3. P(t_k) = || p_ij(t_k) || - матрица переходных вероятностей. Состояния в системе изменяются со временем случайным образом. Каждый элемент матрицы p_ij(t_k) показывает вероятность того, что если КЦМ в момент t_k находилось в состоянии S_i, то в момент t_k+1 она окажется в состоянии S_j:

p_ij(t_k) = Pr{S(t_k+1)=S_j  |  S(t_k)=S_i}.   (2)

 

Основное свойство Марковских процессов: вероятности перехода из S_i в S_j не зависят от предыдущих состояний системы.

 

Понятно, что переходы во все возможные состояния (в том числе в себя) образуют полную группу событий, поэтому

∑p_ij(t_k) =l для всех i=1,..,n,  t_k ϵ Θ.

^j=1

4. X = X(t_k) = [х₁(t_k),…,x_N(t_k)] - вектор-строка распределения вероятностей нахождения КЦМ в соответствующих состояниях в момент t_k, то естьx_l (t_k) - это вероятность того, что в момент t_k система находится в состоянииS_i. При этом

∑x_i(t_k) =l,  t_k ϵ Θ.

ⁱ⁼¹

По теореме об умножении вероятностей и с учетом основного свойства Марковского процесса получим:

x_j(t_k+1) = ∑p_ij(t_k)x_i(t_k) ,  i=1,..,n.     (3)

ⁱ⁼¹

где p_ij(t_k) выступают в роли условных вероятностей перехода в состояние S_j при условии, что система находится в состоянии S_i.

Нетрудно видеть, что правая часть  формулы определяет произведение вектора-строки X(t_k) на матрицу P(t_k) и в векторной форме эквивалентна следующей записи динамического процесса:

X(t_k+1)=X(t_k)P(t_k).   (4)

5. Х₀= X(t_k) = [x₁(t₀),x₂(t₀),...x_n(t₀)] - распределение вероятностей нахождения КЦМ в начальный момент времени t=t_0. Задание вектора X{t₀) позволяет последовательно вычислять векторы X(t_k) (k=1,2,..).

 

Последовательность состояний S(t₀),S(t₁),...,S(t_k) называется конечной цепью Маркова.

Цепь называется однородной, если p_ij не зависит от времени. В этом случае Р - числовая матрица. Если вектор X(t₀) задан, то для однородной цепи Маркова из рекуррентной формулы (4) следует цепочка выражений:

X(t₁)=X(t₀)P.

X(t₂)=X(t₁)P=X(t₀)P².

…

X(t_k)=X(t₀)P^k.   (5)

где P^k – k-я степень матрицы Р.

Классификация состояний  цепей Маркова

Введем классификацию состояний  цепи Маркова. Множество всех состояний  может быть разбито на непересекающиеся подмножества, или классы: невозвратные и эргодические. Их свойства определяются следующим образом. Если процесс покинул класс первого типа, он никогда в него не возвращается. Если процесс попал в класс состояний второго типа, то он никогда его не покидает. Невозвратное множества мы будем обозначать Т, а эргодическое - Ť. При этом их объединение = S, а пересечение – пустое множество. Если эргодическое множество содержи только одно состояние, то это состояние называется поглощающим. Для такого состоянияS, элемент переходной матрицыp_ijдолжен быть равен 1, следовательно, все остальные элементы соответствующей строки равны 0. Цепь, всеэргодические состояния которой являются поглощающими, называется поглощающей цепью.

Для цепи Маркова с N состояниями, в которой имеют® как невозвратные, так и эргодические множества, структура матрицы вероятностей переходов имеет канонический вид

P	s	s-n
s	Q	R
s-n	0	W

 

Где s - количество состояний в невозвратном множестве;

n-s - количество состояний в эргодическом множестве.

Матрица W размерности (n-s)x(n-s) определяет динамику эргодических состояний. Поскольку из множества Ť невозможно выйти, то матрица 0 размерности sx(n-s) состоит из нулей.

Матрица Q размерности sxs определяет поведение процесса до выхода из множества невозвратных состояний.

МатрицаR размерности sx(n-s) определяет вероятности перехода из множества невозвратных состоянии в эргодическое множество.

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

P	s	s-n
s	Q	R(k)
s-n	0	W

 

Рассмотрим структуру матрицы R(k). Вычисляя последовательно степени матрицы Р с учетом (9), получим:

R(1)=R;

R(2) = QR(1)+ R(1)W =QR+RW

R(3) = QR(2)+ R(2)W = Q²R + 2QRW + RW²;

….

_k

R{k+l)= ∑C^l_kQ^k-lRW^l

       ⁱ⁼⁰

где C^l_k – биномиальные коэффициенты. В соответствии со сказанным выше, i-я строка матрицы R(k) содержит вероятности перехода системы во все состояния эргодического множества за k шагов при старте из состоянияS_i ϵ Т. Если цепь Маркова поглощающая, то W = I - единичная матрица размерности n-s, и все ее степени - также единичная матрица той же размерности.

Модель вычислительной системы как цепь Маркова

Основные понятия, связанные с  моделированием на основе цепей Маркова, рассмотрим на примере простейшей модели, в которой ВС рассматривается  как конечный автомат, состоящий  из центрального процессора (CPU) F₀ и нескольких внешних устройств F₁,..,F₄. Центральный процессор производит вычисления, а внешние устройства осуществляют файловый обмен.

Система работает по следующим правилам. Вначале запускается процессор, который может либо производить  вычисления, либо управлять только одним устройством. Устройства, F₁, F₂, F₃, окончив работу, возвращают управление процессору. Если же управление переходит к клавиатуре F₄, то цикл автоматической работы заканчивается и система останавливается в ожидании команды с клавиатуры. Модель, которую мы будем рассматривать, не отражает сущности выполняемых операций, а имеет дело с временными интервалами, в течение которых работают устройства, входящие в ВС. Эти временные интервалы называются случайными величинами. Модель должна удовлетворять следующим требованиям:

1. Она должна оценивать порядок порождения алгоритмом запросов на каждый из видов обслуживания - вычисления и файловый обмен.
2. Модель должна определять трудоемкости обслуживания запросов - количество вычислительных операций и объем информации, передаваемой при файловом обмене.
3. Модель должна отображать случайную природу вычислительных процессов, т.е. случайные моменты возникновения запросов и случайную суммарную трудоемкость обслуживания запросов
4. Принимается, что достаточная адекватность модели реальному вычислительному процессу достигается при совпадении первых моментов одноименных характеристик -  математического ожидания и дисперсии.

Будем рассматривать вычислительный процесс как последовательность этапов счета и файлового обмена.

Состояния являются функциями времени: S_i = S_i(t), причем смена состояний происходит в случайные моменты t0, t1, … , tm. В рассматриваемой модели нам не важны значения интервалов времени между моментами смены состояний ВС. Эти моменты будут рассматриваться как последовательные работы ВС и обозначаться целыми числами. Таким образом, в дальнейшем время считается дискретным.

Процессы смены состояний в  этой системе будем рассматривать  как однородную Марковскую цепь.

Введем  вектор X, определяющий распределение вероятностей состояний в момент t. Сделаем дополнительные предположения о ходе процесса. Процесс всегда начинается с состоянияS₀, т.е. с процессорной обработки, и любому этапу обмена должна предшествовать процессорная обработка. Отсюда следует, что вероятности начальных состояний определяются вектором

X(t₀)=[x₀ x₁ x₂ x₃ x₄] = [1 0 0 0 0],

1.2 Невозвратные состояния.

Рассмотрим поведение цепи Маркова  при росте числа шагов к. Из анализа структуры матрицы Р^к следует,  процесс, стартовав из некоторого состояния S_i, принадлежащего невозвратному множеству Т, на каждом шаге с вероятностями, определенными матрицей R, переходит в эргодическое множество. Через определенное число шагов процесс окажется в эргодическом множестве с вероятностью, как угодно близкой к единице.

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