Задачи и упражнения по главе 3

1. Найдите собственные числа и собственные векторы стохастической матрицы

p₁ q₁

Р =, где p_i + q_i = 1, i = 1, 2

q₂ p₂

Преобразуйте их к виду

P = U Λ U^-1,

где Λ - диагональная матрица.

Вычислите Рⁿ при n -> ∞.

2*. Дана стохастическая матрица

Q R

а) представьте Р в блочном виде Р =

Ø W

б) вычислите матрицу N = (I -Q)^-1;

в) сделайте, спектральное разложение матрицы P = U Λ U^-1;

г)вычислите Р^∞ .

3. Процесс описывается неоднородной цепью Маркова, данной на рисунке 4.2.

Вероятности перехода зависят от номера шага к следующим образом:

0.475 + 0.05k 0.025 + 0.95k

Р₁(k) = ————————; Р₂ (k) = ————————;

0.5+k 0.5+k

Р₃=0.1; Р₄ =0.9;

0.135+ 0.04k 0.015+ 0.36k

Р₅ (k) = ————————; Р₆ (k) = ————————.

0.15 + 0.4k 0.15 + 0.4k

Оценить:

а) вероятности пребывания процесса в различных cостояниях при к = 1, 2, 3;

б) вероятность завершения процесса за 4 шага;

в) среднее число пребываний процесса в невозвратных состояниях при больших k.

4*. Вычислительный процесс определяется схемой на рисунке 4.3.

Рассматривая этот процесс как цепь Маркова, определить:

а) вероятность того, что процесс завершится за 3 шагапри следующих значениях переходных вероятностей:

о) предельные вероятности завершения процесса по каждому из выходов при значениях вероятностей перехода заданных в п. а);

в) среднее число пребываний процесса в невозвратных состояниях при значениях вероятностей, заданных в п. а);

г) предельную трудоемкость (время выполнения) узла 2 при котором среднее время его выполнения не превысит 5% от суммарного среднего времени выполнения всего процесса.
Вероятности переходов определены в п. а), а трудоемкости других узлов следующие:

д) узел, имеющий наибольшее среднеквадратичное отклонение трудоемкости. Вероятности переходов определены в п. а), а трудоемкости узлов следующие:

5. Линейный автомат. Частица движется по прямой единичными шагами (рис 4.4). Всего имеется 5 состояний S₁,..., S₅,, при этом состояния S₂, S₃, S₄ - внутренние, S₁, S₅ -граничные. Вероятность перемещения частицы из данного состояния влево равна р, вправо - q = 1 — p.

Построить, цепь Маркова для описанной ситуации при следующих дополнительных условиях:

а) процесс, достигнув S₁ и S₅, остается там навсегда. Оценить математическое ожидание числа пребываний в каждом изсостояний, если процесс стартует из S₃;

б) частица, достигнув S₁ или S₅, «отражается» и возвра­щается в состояние, из которого пришла, а попав в S₃, остается там навсегда. Оценить математическое ожидание числа пре­рываний в каждом из состояний, если процесс стартует из S₂;

в) состояния S₁ и S₅ соединены так, что вероятность перехода от S₅ к S₁, равна q, а от S₁ к S₅ - р. Попав в S₃, частица остается там навсегда. Оценить математическое ожидание числа пребываний в каждом из состояний, если процесс стартует из S₁.

6. Условия те же, что и в задаче 5, но перемещение происходит со следующими вероятностями: перемещение влево - р, перемещение вправо - q, отсутствие перемещения - r, р +q+r = 1. Построить цепь Маркова для описанной ситуации при следующих дополнительных условиях:

а) процесс, достигнув S₁ и S₅, остается там навсегда. Оценить математическое ожидание числа пребываний в каждом из состояний, если процесс стартует из S₃;

б) частица, достигнув S₁ и S₅, «отражается» и возвращается в состояние, из которого пришла, а попав в S₃, остается там навсегда. Оценить математическое ожидание числа пребываний вкаждом из состояний, если процесс стартует из S₄;

в) состояния S, и S; соединены так, что вероятность перехода от S₅ к S₁ равна q, а от S₁ к S₅ - р. Попав в S₃,

Частица остается там навсегда. Оценить математическое ожидание числа пребываний в каждом из состояний, если процесс стартует из S₅.

7. Решить задачу 5 в предположении, что время изменяется непрерывно, а плотности вероятностей перехода частиц влево равны μ. а вправо – μ ₂ ∙ μ ₁+μ ₂ = μ Построить цепь Маркова для непрерывного времени, написать дифференциальные уравнения для вероятностей пребывания каждом из состояний. Оценить предельные вероятности.

Рассмотреть случаи а), б), в) из задачи 5.

8. Решить задачу 6 для непрерывного времени. Плотности вероятностей перехода частиц влево, вправо и отсутствия перемещения равны, соответственно, μ ₁, μ ₂, μ ₃. Построить цепь Маркова для непрерывного времени, написать дифферен­циальные уравнения для вероятностей пребывания в каждом из состояний. Оценить предельные вероятности.

Рассмотреть случаи а), б), в) из задачи 6.

9. С магнитной ленты считывается массив, состоящий из N блоков данных, с проверкой контрольной суммы по блокам. Вероятность правильного прочтения г-го блока равна р_i. При ошибке чтения делается реверс ленты и новая попытка чтения. Количество попыток не ограничено. Составить сеть Петри, моделирующую эту систему, и соответствующую цепь Маркова. Оценить:

а) математическое ожидание времени чтения массива при N = 100, если для всех блоков р = 0.9, время чтения t_ч-1c, время реверса t_p =0.5c;

б) минимально необходимую вероятность правильного прочтения блока p_min для того, чтобы время чтения массива увеличилось не более чем на 10%, по сравнению со временем Nt_ч, отношение времени чтения и реверса t₄/t_p=4;

в) среднеквадратичное отклонение времени чтениямассива от математического ожидания, если для всех блоков р_i=0.95, t_ч=1c, t_p=0.3c, N=200;

г) оценить вероятность правильного прочтения блока р_i, еслипри чтении 1000 блоков было зафиксировано 5 реверсов.

Принять, что все p_i равны.

10. По информационному каналу с помехами осуществ­ится передача блоков данных в дуплексном режиме от источника И к приемнику П. Это означает, что, получив очередной блок от И, П посылает «квитанцию» И для проверки. Если И подтверждает правильность передачи, то данный блок считается переданным, в противном случае передача повторяется. Число попыток не ограничено. Рассматривая канал как цепь Маркова, где p _i - вероятность правильной передачи И —> П, а р₂ то же для передачи П—> И, оценить;

а) математическое ожидание и дисперсию числа попыток передачи одного блока от И к П;

б) математическое ожидание и среднеквадратичное отклонение времени передачи массива из 100 блоков при P₁ =0.95, р₂=-0.99. время передачи блока от И к П - 0.1с, время передачи «квитанции» от П к И - 0.05с;

в) математическое ожидание и среднеквадратичное отклонение числа повторных передач блоков при N=1000 p₁ =0.99, р₂ =0.995;

г) вероятности р₁ и р₂, если известно, что при передаче 1000 блоков было зафиксировано 3 «переспроса». Принять p₁ = p₂.

11. Триггер с тремя входами - R, S, С и двумя выходами y_о и у₁ (рис 4.4) может находиться в двух состояниях:

s₀(y_о = 1, y₁= 0) И s, (y₀ = 0, у₁ = 1).

Переход из одного состояния s_j(t_k) в другое s_j(tk=1)i, j = 0, 1 зависит от входного сигнала U(t_k) в момент t_k иопределяется следующей схемой:

Предположим теперь, что вероятности правильного перехода при входных сигналах R, S, С равны, соответственно, p_r p_s p_с, q_r=1 -p_r q_s =1-p_s, q_с= -1-p_с - вероятности ложного срабатывания. Рассматривая последовательность смены состояний s(t₀), s(t₁), s(t₂) (выходное слово) - при последовательности входных сигналов U(t₁), U{t₂)... (входном слове), оценить:

а) вероятность нахождения триггера в каждом из состояний при входном слове RCRCS, если S( t₀) = S₀

б) то же при входном слове RRCCCSS и S(t₀)=S₁;

в) оценить уровень надежности триггера р_s для того, чтобы при 10⁶ срабатываниях по сигналу С вероятность ошибки была бы не больше 10 ^-5.

12*. Рассматривается очередь длинной N перед обслуживающим устройством.

На вход системы поступают заявки. Число одновременно поступающих заявок не превышает М.

Устройство в каждый момент времени обслуживает только одну заявку (если очередь не пуста). Количество поступающих на вход очереди заявок ξ, представляет собой - случайную величину со следующим распределением:

Величины а_т заданы и представляют вероятность того, что на вход очереди поступит т заявок. Состояние системы S_i определяется как число заявок i, ждущих обслуживания к началу k-го такта. При этом, если S(t_k) = S_i, то S(t_k+])=S_j

причем

Составить модель системы в виде сети Петри и соответствующую цепь Маркова.

Составить матрицу вероятностей перехода для М = 3, N = 4 и произвести следующие вычисления:

а) вычислить вероятности пребывания в каждом из состояний через 3 шага для следующего распределения вероятностей поступления заявок: a₀₌0.2, a₁=0, 3, а₂ =0.3, а₃ = 0.2. В начальный момент времени очередь была пуста;

б) определить предельные вероятности пребывания системы в каждом из состояний при заданных выше вероятностях;

в) определить среднюю длину очереди для указанных выше условий.

13*. Студент некоторого учебного заведения с четырехгодичным обучением каждый год с вероятность p переходит на следующий курс, с вероятностью q остается навторой год и с вероятностью r отчисляется из института (р + q +r= 1). Составить модель процесса в виде сети Петри и рассматривая процесс перехода с курса на курс как цепь Маркова, определить следующие величины:

а) вероятность того, что студент окончит институт за 4 года. Для расчета положить р = 0.8, q = 0.1, r = 0.1;

б) то же, что и в п. а, но при дополнительном условии, что на каждом курсе нельзя находиться более двух лет;

в)математическое ожидание числа лет пребывания на каждом курсе при условии, что студент поступил на первый курс. Взять данные п. а;

г) дисперсию числа лет пребывания на каждом курсе при условии, что студент поступил на первый курс. Взять данные п. а.

14*. Студент изучает курс в интерактивном режиме с помощью компьютерной системы. Изучение одного модуля (фрагмента курса) состоит из чтения теоретического материала и сдачи тестов. При оценке знаний на «4» и «5» модуль считается освоенным; при оценке «3» студенту дается дополнительный материал и снова проводится тестирование; при оценке «2» студент изучает модуль с самого начала.

1.Составить сеть Петри и цепь Маркова для данной задачи.

2.Определить среднее время изучения модуля, если чтение теоретического материала занимает 1 час, чтение дополнительного материала - 0.5 часа, тестирование - 0.2 часа, вероятность получения оценок «4» и «5» равна p₁, оценки «3» p₂, оценки «2» - рз, (р₁+ р₂+ р₃= 1). Для расчетов взять p ₁ =0.5, р₂=0.3, р₃=0.2.

15. При реализации двух моделей аппаратуры фирма придерживалась следующих правил:

1.Одновременно продается только одна модель.

2.Если текущий месяц был успешным, то на следующий месяц реализуется та же модель, при этом вероятность успеха сбавляет р₁, вероятность неудачи q₁ =1- р₁.

3. Если текущий месяц был неудачен, то на следующий месяц реализуется другая модель, при этом вероятность успеха оставляет р₂ вероятность неудачи q₂ = 1- р₂.

Составить событийную модель системы в виде сети Петри и, рассматривая процесс реализации аппаратуры как цепь Маркова с двумя состояниями (S₁ - успех и S₂ - неудача), определить следующие характеристики:

а) вероятность успеха и неудачи через 4 шага при условии, что реализация началась с удачи. Для вычислений взять р₁ = 0.5, р₂ =0.7;

б) вероятность успеха и неудачи через 3 шага при условии, что реализация началась с неудачи. Для вычислений взять р, = 0.45, р, =0.6;

в)предельные вероятность успеха и неудачи при большом числе шагов. Для вычислений взять р₁ =0.5, р₂ =0.6.

16. В условиях задачи 15 известно, что успех после успешного шага приносит доход с₁₁ рублей, неудача после успешного шага - доход с₁₂ рублей, успех после неудачи – с₂₁ рублей, неудача после неудачи - с₂₂ рублей. Определить следующие величины:

а)математическое ожидание полного дохода через 3 шага при условии, что реализация начинается с успеха. Взять Р₁ = O, 5, р₂ = 0.7, с₁₁ = 500, с₁₂ = 150, с₂₁ = 200, с₂₂= 400;

б)математическое ожидание полного дохода через 4 шага при условии, что реализация начинается с неудачи. Взять числовые данные из п. а;

в)составить в общем виде разностные уравнения для вычисления математического ожидания дохода на п + 1 шаге, если известны математические ожидания дохода на п шаге.

5. Лабораторный практикум

Приведенный ниже цикл из восьми лабораторных работ рассчитан на 34 часа работы в компьютерном классе и примерно на такой же объем самостоятельной работы в компьютерном классе или на домашних компьютерах. Тематика работ, как и вся книга, ориентирована в основном на две методологии моделирования систем.

Первый цикл, состоящий из работ с 1 по 4, связан с моделированием систем на основе методологии сетей Петри. Здесь, помимо собственных программ, которые пишут студенты при выполнении работ, возможно использование программы CPN Tools. Краткая инструкция по работе с этой программой приводится в приложении А.

Аналогично, при исследовании цепей Маркова (работы с 5 по 7) предполагается умение работать с универсальным математическим пакетом MathCad.

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

В случае необходимости по материалам данного лабораторного практикума могут быть сформированы задания по курсовой работе.