Автор: Пользователь скрыл имя, 10 Декабря 2012 в 13:18, курсовая работа
Данная курсовая работа посвящена изучению цепей Маркова. Работу можно разделить на несколько подзадач:
1. Освоить основные положения теории конечных цепей Маркова с дискретным временем.
2. Научится составлять ЦМ для моделирования вычислительных систем и анализа динамики их функционирования.
3. Провести имитационное моделирование динамики ЦМ.
4. Провести расчет характеристик производительности вычислительных систем.
Введение 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
Входные данные:
- матрица переходных
- номер стартового состояния j0
- число временных шагов
- число статических
Выходные данные:
Оценки вероятностей нахождения процесса в различных состояниях X[j] в момент времени t=tk.
Словесный алгоритм:
1) Создаём 2 массива X и Y длиной n. Заполняем их нулями, полагаем tk=1.
2) Полагаем t=0, помещаем 1 в позицию j0 массива Y.
3) Выполняем основной шаг алгоритма – определяется номер очередного состояния j в соответствии с матрицей Р случайным образом. Прибавляем 1 к элементу Y[j]. Увеличиваем t на 1.
4) Повторяем шаг 3 до тех пор, пока t<=tk.
5) Пересчитываем X=X+Y.
6) Повторяем шаги 2-5 N раз.
7) Вычисляем значения X[j]=X[j]/
8) Вычисляем сумму S=X[1]+X[2]+..
9) повторяем шаги 1-8 для всех tk, k=1..15.
Основной шаг алгоритма:
Пусть в момент времени t система находилась в состоянии Sk. Определим номер состояния, в которое система перейдет в момент t+1. Выделим k-ую строку матрицы P:
=[, , … ], =1
С помощью датчика случайных чисел генерируем случайное число r(t), 0<=r(t)<=1 с равномерным законом распределения. Тогда номер состояния j определится условием:
min{l:=>r(t)}
Иными словами, j – это номер элемента строки , для которого сумма при возрастании j от 1 до n впервые не меньше r(t).
2.4 Выделение невозвратного и эргодического множества из матрицы вероятностей переходов.
Невозвратное множество
Эргодическое множество
Структурируем матрицу P. Выписываем матрицы Q, W, R:
Любая матрица Р выглядит следующим образом (канонический вид):
Таблица 2.18
P |
s |
s-n |
s |
Q |
R |
s-n |
0 |
W |
Где s – количество состояний невозвратного множества, n-s – количество состояний эргодического множества, 0 – матрица, содержащая нули (нулевая).
Таблица 2.19 - Матрица вероятностей переходов
Матрица Q размерности s×s определяет поведение процесса до выхода из множества невозвратных состояний (таблица 2.21).
Таблица 2.21
Матрица W размерности (n-s)×(n-s) определяет динамику эргодических состояний. Поскольку из множества невозможно выйти, то матрица 0 размерности состоит из нулей.
Таблица 2.21 – Матрица эргодических состояний
Таблица 2.22 – Нулевая матрица
Матрица R размерности (таблица 2.23) определяет вероятности перехода из множества невозвратных состояний в эргодическое множество.
Таблица 2.23
Найдем обратную матрицу (таблица 2.23) по следующей формуле:
Таблица 2.24
Средняя трудоемкость вычислительного процесса:
Оценим теперь дисперсию числа пребываний процесса в множестве невозвратных состояний по следующей формуле:
Этот показатель характеризует степень разброса величин относительно среднего. Для начала, вычислим матрицу дисперсии D, по формуле D=N*(2*Ndg – E)-Nsq, для этого нам понадобятся матрицы:
Таблица 2.25 - Ndg, где все элементы кроме диагонали =0
Таблица 2.26 - Nsq, где каждый элемент возведен в квадрат:
E – единичная матрица.
Таблица 2.27
С помощью матрицы D, нужно найти среднеквадратичное отклонение числа пребывания процесса от среднего G, для этого нам нужно вычислить элементы, которые равны корню квадратному из соответствующих элементов матрицы D:
Таблица 2.28
Вычислим среднеквадратичное отклонение трудоемкости вычислительного процесса от среднего по формуле
2.5 Оценка предельных
вероятностей пребывания
Для оценки предельных вероятностей пребывания процесса в множестве T~, воспользуемся 2-мя методами:
Возведем матрицу P в предельно большую степень. limPk при k-> к бесконечности, и получим:
Таблица 2.29
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 | |
1 |
0 |
0 |
0 |
0 |
0,22 |
0,19 |
0,11 |
0 |
2 |
0 |
0 |
0 |
0 |
0,25 |
0,22 |
0,12 |
0 |
3 |
0 |
0 |
0 |
0 |
0,3 |
0,26 |
0,15 |
0 |
4 |
0 |
0 |
0 |
0 |
0,17 |
0,14 |
0,08 |
0 |
5 |
0 |
0 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
6 |
0 |
0 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
7 |
0 |
0 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Как видно, матрица Q стремится к нулевой матрице.
Для проверки правильности результата, воспользуемся спектральным разложением матрицы P. Когда матрица P возводится в k степень, она имеет вид
Qk |
R(k) |
0 |
Wk |
При предельном возведении, матрица Q->0, а матрицы R(k) и Wk, принимают вид:
Таблица 2.30 - R(k)
0 |
0,22 |
0,19 |
0,11 |
0 |
0 |
0,25 |
0,22 |
0,12 |
0 |
0 |
0,3 |
0,26 |
0,15 |
0 |
Таблица 2.31 - Wk
|
0 |
0,17 |
0,14 |
0,08 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
0 |
0,42 |
0,37 |
0,21 |
0 |
0 |
0 |
0 |
0 |
0 |
Можно заметить что результат совпадает с первым методом, и делая вывод можно сказать что с вероятностью 100% процесс перейдет во множество эргодических состояний. Предельный вектор вероятностей переходов имеет вид:
Таблица 2.32
0 |
0 |
0 |
0 |
0,22 |
0,19 |
0,11 |
0 |
Алгоритм программы №2:
1. Выполнение шага 3 прекращается, если очередное состояние Sj относящегося к эргодическому множеству Sjϵ Ť
2. Исключается шаг 8, на печать выводится результат шага 7.
3. Расчет ведется только для максимального значения tkk=20.
Заключение
В ходе проделанной работы были выполнены все цели данной лабораторной работы. А также было выяснено, что с увеличением числа испытаний N, относительные частоты пребывания системы в состояниях приближаются к теоретическим вероятностям этих состояний.
Список использованных источников
1. Цепь Маркова [Электронный ресурс] // - режим доступа:
http://ru.wikipedia.org/wiki/
2. Доррер Г.А. «Методы моделирования дискретных систем»: Красноярск, 2004, СибГТУ, С.89-116.
3. Шилдт Г. «Самоучитель С++» - СПб.: БХВ-Петербург, 2003.
Приложение А - листинг программы
Программа №1:
#include <vcl.h>
#include <time.h>
#pragma hdrstop
#include "Unit1.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int const K=8;
int P[K][K]={NULL},X[100][K]={
//----------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//----------------------------
int Co;
int x=0,y=200;
void __fastcall TForm1::FormActivate(TObject *Sender)
{
srand(time(NULL));
SG->Cells[0][0]="P";
for(int i=1; i<K+1; i++)
{
SG->Cells[0][i]=i;
SG->Cells[i][0]=i;
}
for(int i=1; i<K+1; i++)
for(int j=1; j<K+1; j++)
SG->Cells[i][j]=0;
SG->Cells[1][1]=1;SG->Cells[2]
SG->Cells[5][1]=0;SG->Cells[6]
SG->Cells[1][2]=0;SG->Cells[2]
SG->Cells[5][2]=0;SG->Cells[6]
SG->Cells[1][3]=6;SG->Cells[2]
SG->Cells[5][3]=4;SG->Cells[6]
SG->Cells[1][4]=0;SG->Cells[2]
SG->Cells[5][4]=0;SG->Cells[6]
SG->Cells[1][5]=0;SG->Cells[2]
SG->Cells[5][5]=3;SG->Cells[6]
SG->Cells[1][6]=0;SG->Cells[2]
SG->Cells[5][6]=8;SG->Cells[6]
SG->Cells[1][7]=0;SG->Cells[2]
SG->Cells[5][7]=0;SG->Cells[6]
SG->Cells[1][8]=0;SG->Cells[2]
SG->Cells[5][8]=0;SG->Cells[6]
}
//----------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Co=1;
for(int i=0; i<K; i++)
for(int j=0; j<100; j++)
X[j][i]=0;
int Jo=StrToInt(Edit1->Text);
int Tk=StrToInt(Edit2->Text);
int No=StrToInt(Edit3->Text);
for(int i=0; i<K; i++)
for(int j=0; j<K; j++)
P[i][j]=StrToInt(SG->Cells[j+
int st,Sluh;
for(int N=0; N<No; N++)
{
st=Jo-1;
Y[0][Jo-1]=1;
for(int T=0; T<Tk; T++)
{
int Sum=0;
Sluh=1+rand()%10;
for(int j=0; j<K; j++)
{
}
if(st==8) break;
}
for(int i=0; i<K; i++)
for(int j=0; j<Tk+1; j++)
}
int Z[K]={NULL};
for(int i=0; i<K; i++)
for(int j=0; j<Tk+1; j++)
Z[i]+=X[j][i];
for(int i=0; i<K; i++)
S->Cells[i+1][0]=FloatToStr((
for(int i=0;i<K;i++)Z[i]=0;
for(int j=0; j<Tk+1; j++)
{
int S=0;
for(int i=0; i<K; i++)
S+=X[j][i];
for(int i=0; i<K; i++)
S1->Cells[i+1][j+1]=
}
for(int i=0;i<K;i++) S1->Cells[i+1][0]=i+1;
for(int i=0;i<Tk+1;i++) S1->Cells[0][i+1]=i;
}
Программа №2:
#include <vcl.h>
#include <time.h>
#pragma hdrstop
#include "Unit1.h"
//----------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int const K=9;
int P[K][K]={NULL},X[100][K]={
//----------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//----------------------------
int Co;
int x=0,y=200;
void __fastcall TForm1::FormActivate(TObject *Sender)
{
//Button4->Visible=false;
//Button2->Enabled=false;
//Button3->Enabled=false;
srand(time(NULL));
SG->Cells[0][0]="P";
for(int i=1; i<K+1; i++)
{
SG->Cells[0][i]=i;
SG->Cells[i][0]=i;
}
for(int i=1; i<K+1; i++)
for(int j=1; j<K+1; j++)
SG->Cells[i][j]=0;
Информация о работе Моделирование динамики систем на основе цепей Маркова с дискретным временем