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

 
 

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

                                                        по дисциплине

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

                                    На тему

       «Моделирование динамики систем на основе

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

                    Вариант - 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

          Содержание 

1. Введение            2

 

2. Цели работы            3

 

3. Постановка  задачи           3
1.    Исходные данные          3
2.    Алгоритм имитационного моделирования динамики ЦМ     3
3.    Содержание работы          4

 

4. Теоретическая часть           5
1. Определение цепи Маркова         5
2. Модель вычислительной системы как цепь Маркова     6
3. Классификация состояний цепей Маркова       8
4. Оценка длительности пребывания системы во множестве Т             10
5. Исследование динамики цепей Маркова при большом числе шагов            12

 
 

5. Практическая  часть                    15
1. Матрица переходных вероятностей Р                    15
2. Векторы вероятностей X(t)                  15
3. Оценка результатов тестирования программы 1               20
4. Структурирование Р                   22
5. Матрица N и средняя трудоёмкость процесса               23
6. Оценка результатов тестирования программы 2               24
7. Среднеквадратичные отклонения от среднего пребывания процесса во

   множестве Т и трудоёмкости                  24

8. Оценка предельных вероятностей пребывания процесса во множестве Ť           25

 

6. Используемая  литература                   27

 

7. Приложение                     27

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Введение   

    Цепи  Маркова названы так в честь выдающегося русского математика, Андрея Андреевича Маркова, который много занимался случайными процессами и внес большой вклад в развитие этой области. В последнее время можно услышать о применении цепей Маркова в самых разных областях: в современных веб-технологиях, при анализе литературных текстов или даже при разработке тактики игры футбольной команды. У тех, кто не знает что такое цепи Маркова, может возникнуть ощущение, что это что-то очень сложное и почти недоступное для понимания.

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

    Такая технология сейчас очень широко применяется  в Интернете для создания псевдоконтента веб-страничек. Люди желающие увеличить  трафик на свой сайт и повысить его  рейтинг в поисковых системах, стремятся натолкать туда как можно больше популярных ключевых слов для поиска. Но на поисковиках ставят умные алгоритмы, которые умеют отличать реальный текст от бессвязного нагромождения слов. Тогда, чтобы обмануть поисковики используют горы текста созданного генератором на основе Марковской цепи. Есть, конечно, и положительные примеры использования цепей Маркова для работы с текстом, их применят при анализе подлинности текстов, определении авторства, в алгоритмах для синтеза речи и т.п.  
 
 
 
 
 
 
 
 
 
 
 

                               Цели работы 

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

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

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

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

                          Постановка задачи 

                           Исходные данные 

 

Стартовая вершина  – 1. 

Трудоемкости  каждого состояния:

С1=1 С2=3 С3=5 С4=7 С5=9 С6=6  

          Алгоритм  имитационного моделирования  динамики ЦМ

    Задано:

А) матрица переходных вероятностей Р

Б) номер стартового состояния j0

В) число временных шагов исследования процесса tk

Г) число статических  экспериментов N 

Требуется:

    Вычислить оценки вероятностей нахождения процесса в различных состояниях 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]/N, j=1..n, которые являются оценками среднего числа пребываний процесса в j-м состоянии.

8) Вычисляем  сумму S=X[1]+X[2]+..+X[n] и величины X[j]/S, которые представляют собой оценки вероятностей пребывания процесса в каждом состоянии. Выводим tk и вектор X на печать и график.

9) повторяем  шаги 1-8 для всех tk, k=1..15. 

                           Содержание работы 

    1. Изучить теоретический материал  по ЦМ.

    2. Для заданного варианта модели  ВС составить матрицу переходных  вероятностей.

    3. Вычислить векторы вероятностей X(t) пребывания системы в каждом из 15 шагов при старте из заданного исходного состояния и построить соответствующие графики.

    4. Написать и отладить программу  имитационного моделирования динамики  ЦМ на языке высокого уровня.

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

    6. Структурировать матрицу Р, выделить  множества невозвратных и эргодических  состояний. Выписать матрицы Q, R, W.

    7. Вычислить среднее число тактов пребывания системы в каждом из невозвратных состояний путём вычисления матрицы N.

    8. На основе N вычислить среднюю трудоёмкость вычислительного процесса.

    9. Получить оценку строки матрицы  N, соответствующей заданному стартовому состоянию с помощью модификации разработанной программы: выполнение шага 3 прекращается, если очередное состояние относится к эргодическому множеству; исключается шаг 8, на печать выводится результат шага 7; расчет ведется только для максимального значения tk.

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

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

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

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

    Формальное  определение. Конечная цепь Мария (Finite Markov Chain - FMC) - это набор элементов:

    FMC = {Θ, S, P, X, X₀}.  (1)

    Рассмотрим элементы определения (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) показывает вероятность того, что если FMC в момент 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 не зависят от предыдущих состояний системы.

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

    _n

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