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

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования

«Восточно-Сибирский Государственный Технологический Университет»

(ГОУ ВПО ВСГТУ)

 

 

 

 

Электротехнический факультет

Кафедра «Системы информатики»

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

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

Вариант №15

 

 

 

 

 

 

Выполнил: студент гр.639 Кикоть И.М.

Проверил: Дамбаева С.В

 

 

 

 

г. Улан-Удэ   2012 год

Содержание:

1. Введение.
2. Теоретическая часть.
3. Постановка задачи и исходные данные.
4. Практическая часть.

• Переходные вектора и график полученные теоретически и практически.
• Структурирование матрицы P, и выделение подмножеств T и T~.
• Сравнение теоретически полученной матрицы N с результатом работы программы. Вычисление средней трудоемкости Cср.
• Оценка среднеквадратичного отклонения от числа пребываний в множестве невозвратных состояний, а так же соответствующие отклонение трудоемкостей от среднего.
• Оценка предельных вероятностей пребывания процесса во множестве невозвратных состояний от среднего.

5. Описание структур данных программы.

6. Список литературы.
7. Приложения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение:

     Цели и задачи дисциплины.

Цели дисциплины:

• изучение основных принципов и методов моделирования вычислительных процессов и управления процессами;
• привитие навыков применения математического аппарата для описания, анализа и синтеза формальных моделей вычислительных процессов с направленностью на использование этих моделей в практике проектирования типовых компонентов программного и программно-аппаратного обеспечения вычислительной техники и автоматизированных систем.

Задачи дисциплины:

• изучение методов и формальных языков моделирования вычислительных процессов и систем;
• ознакомление с принципами и стратегиями управления вычислительными процессами и методами борьбы с возможными аномалиями;
• изучение принципов и методов  формальной спецификации и верификации программного обеспечения;
• приобретение опыта использования сетей Петри как инструмента для моделирования аппаратного и программного обеспечения ЭВМ.

        Место дисциплины в структуре ООП.

Дисциплина ”Теория вычислительных процессов” (код Б.3.18) относится к вариативной части профессионального цикла дисциплин (код Б.3). Дисциплина базируется на знаниях и умениях, приобретённых при изучении курсов  “Дискретная математика” (Б.2.7), “Математическая логика и теория алгоритмов” (Б.2.8), “Программирование” (Б.3.5).

Знания и умения, полученные при изучении дисциплины ”Теория вычислительных процессов”, используются в последующих дисциплинах: “Операционные системы” (Б.3.7), “Web-программирование” (Б.3.14).

         Требования к уровню освоения дисциплины.

       В результате освоения дисциплины ”Теория вычислительных процессов” у студента

формируются следующие компетенции ООП подготовки бакалавра по направлению 2301000062 ”Информатика и вычислительная техника”:

• использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы  математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);
• способен разрабатывать модели компонентов информационных систем, включая модели баз данных (ПК-11);
• имеет навыки работы с компьютером как средством управления информацией

      (ОК-12);

 

Освоив дисциплину ”Теория вычислительных процессов”, студент должен:

 

• иметь представление

• –о проблемах и направлениях развития теории вычислительных   процессов,

   новых  способах их формального описания и верификации;

• –об основных тенденциях развития способов задания семантики программ,

   их  формальной спецификации и верификации;

• знать
• –формальные модели основных вычислительных процессов,
• –методы управления процессами и их синхронизации,
• –протоколы взаимодействия объектов,
• –методы анализа вычислительных  процессов;
• –возможные аномалии при кооперировании процессов и конкуренции за обладание

  общими ресурсами;

• –основные классы схем программ, используемых при конструировании

  языков  программирования;

• - методы моделирования систем на основе сетей Петри,

• уметь

• –разрабатывать автоматные модели процессов распознавания языков;
• –моделировать работу алгоритмов взаимодействия процессов и  ресурсов

в работе вычислительной системы,

• иметь опыт

• использования инструментальных средств моделирования вычислительных

            процессов.

2. Теоретическая часть:

 

1. Определение цепи Маркова:

Цепь Маркова – это модель системы, которая переходит случайным образом из одного состояния в другое.

Формальное определение. Конечная цепь Маркова (Finite Markov Chain - FMC) - это набор элементов: FMC = {Θ, S, P, X, X0}.  (1)

Рассмотрим эти элементы:

• Θ - множество моментов времени. Мы будем рассматривать как множество дискретных моментов времени Θ={to,t1,...,tk,...}, так и непрерывное время, Θ=R, где R -  множество рациональных чисел. 
• S = {S1,...,Sn} – конечное множество состояний. В каждый момент времени tk система может находиться только в одном из состояний Si. Этот факт мы будем обозначать так:

S(tk)=Si, tkпринадлежит Θ, Si принадлежит S

• P(tk) = || pij(tk) || - матрица переходных вероятностей.

Состояния в системе изменяются со временем случайным образом. Каждый элемент матрицы pij(tk) показывает вероятность того, что если FMC в момент tk находилось в состоянии Si, то в момент tk+1 она окажется в состоянии Sj:

pij(tk) = Pr{S(tk+1)=Sj  |  S(tk)=Si}.  (2)

При этом основное свойство Марковских процессов состоит в том, что вероятности перехода из Si в Sj не зависят от предыдущих состояний системы.

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

n

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

j=1

• X = X(tk) = [х1(tk),…,xN(tk)] - вектор-строка распределения вероятностей нахождения FMС в соответствующих состояниях в момент tk, то есть xl(tk) - это вероятность того, что в момент tk система находится в состоянии Si. При этом

n

∑ xi(tk) =l,  tk ϵ Θ.

i=1

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

       n

xj(tk+1) = ∑ pij(tk)xi(tk) ,  i=1,..,n.   (3)

      i=1

где pij(tk) выступают в роли условных вероятностей перехода в состояние Sj при условии, что система находится в состоянии Si.

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

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

• Х0 = X(tk) = [x1(t0), x2(t0),...xn(t0)] - распределение вероятностей нахождения FMC в начальный момент времени t=t0. Задание вектора X{t0) позволяет последовательно вычислять векторы X(tk) (k=1,2,..).

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

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

X(t1)=X(t0)P.

X(t2)=X(t1)P=X(t0)P2.

…

X(tk)=X(t0)Pk.   (5)

 

Где Pk – k-я степень матрицы Р.

Цепь Маркова можно представить как динамически систему - вероятностный автомат с обратной связью (рис. 1). На рисунке прямоугольник 1 означает задержку сигнала состояния на 1 такт.

 

 

 

 

 

 

 

 

Рис. 1

 

Матрицы Р, порождающие цепи Маркова, т.е. такие, у которых все элементы 0<=pij<=1, а их суммы по столбцам равны единице для всех строк

 n

∑ pij=1,  i=1,..,n, 

i=1

называют стохастическими. Свойства этих матриц хорошо изучены, и мы в дальнейшем будем использовать известные факты без доказательств.

Отметим также, что, помимо аналитических методов исследования поведения FMC, большие возможности дает метод статистического моделирования.

 

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

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

В частности, предполагается наличие следующих периферийных устройств:

F1 - накопитель на жестком магнитном диске;

F2 - накопитель на гибком магнитном диске;

F3 - устройство печати;

F4 - клавиатура.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.

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

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

 

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

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

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

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

X(t0)=[x0 x1 x2 x3 x4] = [1 0 0 0 0],

А матрица вероятностей переходов не зависит от времени:

Из этой матрицы видно, что из состояния S0 процесс с вероятностями р1,р2,р3,р4 переходит, соответственно в состояния S1,S2,...,S4, при этом р1 + р2 + р3 + р4 = 1.

Из состояний S1,S2,S3 процесс с вероятностью 1 возвращается в S0. Достигнув состояния S4, процесс навсегда остается в нем. Такое состояние называется поглощающим.

Помимо порядка смены состояний может оцениваться трудоемкость вычислительного процесса.

Пусть С0- средняя трудоемкость этапа счета (среди число процессорных операций или соответствующее процессорное время);

С1,С2,С3 - средняя трудоемкость операций файлового обмена в байтах (или, если известна скорость обмена каналов, - среднее время обмена).