Задания для самостоятельной работы 1 страница

1. По информационному каналу с помехами осуществляется передача блоков данных в дуплексном режиме от источника И к приемнику П. Это означает, что, получив очередной блок от И, П посылает «квитанцию» И для проверки. Если И подтверждает правильность передачи, то данный блок считается переданным, в противном случае передача повторяется. Число попыток не ограничено. Рассматривая канал как цепь Маркова, где - вероятность правильной передачи И®П, а – то же для передачи П®И. Оценить:

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

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

в) математическое ожидание и среднеквадратичное отклонение числа повторных передач блоков при N=1000 =0,99, =0,.995;

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

2. Триггер с тремя входами - , , и двумя выходами и (рисунок 3.11) может находиться в двух состояниях:

и .

Рис. 3.11

Переход из одного состояния в другое зависит от входного сигнала в момент и определяется следующей схемой:

при

(сброс на 0)

при

(установка 1)

при

(счетный вход)

Предположим теперь, что вероятности правильного перехода при входных сигналах , , равны соответственно , , , а , , - вероятности ложного срабатывания. Рассматривая последовательность смены состояний , , (выходное слово) - при последовательности входных сигналов , ... (входном слове), оценить:

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

б) то же при входном слове и ;

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

3. Составьте имитационную модель в системе AnyLogic для моделирования системы обслуживания заявок с очередью и отказами, рассмотренной в п. 3.3. Проведите исследование процесса с помощью модели.

4. Составьте имитационную модель в системе AnyLogic для моделирования жизненного цикла информационных ресурсов, рассмотренную в п. 3.4. Проведите исследование процесса с помощью модели.

5. Выведите формулы и решите задачу выбора эффективного портфеля по методике п. 3.5 при наличии трех ценных бумаг со следующими параметрами:

Глава 4 Сетевые модели поддержки принятия решений

Сетевые модели систем (N-схемы), о которых упоминалось в п. 1.6, широко применяются в системах поддержки принятия решений.

Среди моделей этого класса выделился подход, основанный на использовании сетей специального вида, предложенный Карлом Петри в 1962 году для моделирования асинхронных информационных потоков в системах обработки данных. Эта методология, получившая название сетей Петри, была развита в последующие годы многочисленными исследователями и получила широкое распространение.

Большой вклад в развитие теории сетей петри внесли отечественные ученые, в частности, математики из Новосибирского научного центра во главе с В.Е. Котовым [18].

В последние годы получила распространение теория так называемых сетей петри высокого уровня, которая изложена, например, в трехтомной работе Курта Йенсена [42]. Эта разновидность сетей Петри позволяет моделировать весьма сложные дискретные динамические системы, а их описание представлено с помощью специализированного алгоритмического языка.

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

В первом параграфе главы изложены первоначальные сведения, связанные с определением, функционированием и некоторыми свойствами обыкновенных сетей Петри, которые мы будем сокращенно обозначать либо СП, либо PN (Petri Nets). Там же рассмотрены некоторые расширения таких сетей, в частности сети с ингибиторными связями ИСП (IPN).

Второй параграф содержит описание так называемых раскрашенных сетей Петри в нотации К. Йенсена, обозначаемых как РСП, либо CPN (Coloured Petri Nets), а также некоторых их расширений.

Третий параграф посвящен моделированию с помощью сетей Петри элементов вычислительных систем и программ. Здесь собраны примеры применения сетей Петри для моделирования.

Кроме сетей Петри в данной главе рассмотрен еще один вид сетевых моделей, носящих название GERT-сетей, которые позволяют рассчитывать вероятностные характеристики моделируемых процессов при заданных функциях распределения вероятностей на отдельных дугах.

4.1 Обыкновенные сети Петри

4.1.1 Формальное определение

Сеть Петри - это математическая модель дискретных динамических систем (параллельных программ, операционных систем, ЭВМ и их устройств, сетей ЭВМ), ориентированная на качественный анализ и синтез таких систем (обнаружение блокировок, тупиковых ситуаций и узких мест, автоматический синтез параллельных программ и компонентов ЭВМ и др.).

Формально в терминах теории систем [18, 28,42] сеть Петри (Petri Net – PN) - это набор элементов (кортеж)

. (4.1)

В этом определении

- множество дискретных моментов времени;

- непустое множество элементов сети, называемых позициями (местами);

- непустое множество элементов сети, называемых переходами.

Множества позиций и переходов не пересекаются:

.

- функция инцидентности,

, (4.2)

где - кратность дуги.

M₀ - начальная маркировка позиций: .

Функция инцидентности может быть представлена в виде и фактически задает два отображения:

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

2) т.е. для каждого перехода указываются связанные с ним позиции (также с учетом кратности).

Эти функции, в общем случае зависящие от времени, могут быть представлены матрицами инцидентности

Смена маркировок (начиная с ) происходит в результате срабатывания переходов сети. Переход может сработать (может быть запущен) при маркировке М, если для всех выполняется условие

, (4.6)

т.е. если каждая входная позиция для данного перехода содержит как минимум столько фишек, какова кратность ведущей к дуги.

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

, (4.7)

i=1,...,n, j=1,...,m, , .

Иными словами, переход t изымает из каждой своей входной позиции число фишек, равное кратности входных дуг и посылает в каждую свою выходную позицию число фишек, равное кратности выходных дуг.

Если может сработать несколько переходов, то срабатывает один, любой из них. Функционирование сети останавливается, если при некоторой маркировке (тупиковая маркировка) ни один из ее переходов не может сработать. При одной и той же начальной маркировке сеть Петри может порождать, в силу недетерминированности ее функционирования, различные последовательности срабатывания ее переходов. Эти последовательности образуют слова в алфавите T.

множество всевозможных слов, порождаемых сетью Петри, называют языком сети Петри. Две сети Петри эквивалентны, если порождают один и тот же язык.

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

4.1.2 Графы сетей Петри

Формальное определение сети Петри, изложенное выше, полностью определяет ее функционирование.

Однако при решении конкретных инженерных задач удобнее и нагляднее графическое представление этих сетей.

Поэтому ниже функционирование сетей Петри изложено с позиции теории графов.

Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф сети Петри.

Этот граф содержит:

- позиции (места), обозначаемые кружками;

- переходы, обозначаемые планками;

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

Благодаря наличию кратных дуг сеть Петри есть мультиграф. Благодаря двум типам вершин граф называется двудольным. Поскольку дуги имеют направление, граф является ориентированным. Пример такого мультиграфа показан на рисунке 4.1.

рис. 4.1. Пример сети Петри

Для сети, изображенной на этом рисунке, матрицы инцидентности имеют вид:

, .

Начальная маркировка, как видно из рисунка 4.1, .

Нетрудно видеть, что матричное и графовое представления взаимно однозначно соответствуют друг другу.

В случае большой кратности дуг эту кратность можно указывать цифрами на соответствующей дуге.

4.1.3 Пространство состояний сети Петри

Состояние сети Петри определяется ее маркировкой. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т.е. . Изменение в состоянии, вызванное запуском перехода, определяется функцией перехода d или функцией следующего состояния. Когда эта функция применяется к маркировке M и переходу (если он разрешен), то в соответствии с (4.7) получается новая маркировка . Она, как уже говорилось, получается изъятием фишек из позиции p_i таких, что и помещением фишек в позиции такие, что . Процесс создания новых маркировок продолжается до тех пор, пока в сети Петри при данной маркировке существует хоть один разрешенный переход. Если же при некоторой маркировке ни один переход не разрешен, то такая маркировка называется тупиковой.

При выполнении сети Петри получается две последовательности:

1) последовательность маркировок

;

2) последовательность запущенных переходов

.

Эти две последовательности связаны следующим соотношением

. (4.8)

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

Множество достижимости сети Петри PN с маркировкой М есть множество всех , достижимых из М.

Маркировка М^¢ принадлежит , если существует какая-либо последовательность запусков переходов, изменяющих М на М^¢.

Множество достижимости для сети P c маркировками М есть наименьшее множество маркировок, определенных следующим образом:

a) ;

б) если и для некоторого , то .

Вернемся к примеру на рисунке 4.1. При начальной маркировке могут сработать переходы (в результате получаем ) и (получается маркировка ). Каждая из полученных маркировок порождает новые, в результате чего получается дерево маркировок, фрагмент которого показан на рисунке 4.2. Обратим внимание на то, что в дереве маркировок могут встречаться повторяющиеся маркировки. В этом случае дальнейшее построение дерева ведется только для одной из них.

= 0	= 1	= 2	= 3	= 4
M0=[2 2 0]	t 1: [2 3 0]
		t 1: [2 4 0]
			t 1: [2 5 0]
				t 1: [2 6 0]
				t 2: [1 3 1]
			t 2: [1 2 1]
				t 1: [1 3 1]
				t 2: [0 0 2]
				t 3: [2 4 0]
				t 4: [2 2 0]
		t 2: [1 1 1]
			t 1: [1 2 1]	повтор
			t 3: [2 3 0]
				t 1: [2 4 0]
				t 2: [1 1 1]
			t 4: [2 1 0]
				t 1: [2 2 0]
	t 2: [1 0 1]
		t 1: [1 1 1]	повтор
		t 3: [2 2 0]	повтор
		t 4: [2 0 0]
			t 1: [2 1 0]	повтор

рис. 4.2. Дерево маркировки сети Петр, показанной на рисунке 4.1

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

Так, язык рассматриваемой сети включает слова

{l, t₁, t₂, t₁ t₁, t₁ t₂, t₂ t₁, t₂ t₃, t₂ t₄, t₁ t₁ t₁, t₁ t₁ t₂, t₁ t₂ t₁,

t₁ t₂ t₃, t₁ t₂ t₄, t₂ t₁ t₁, t₂ t₃ t₁, t₂ t₄ t₁, t₁ t₁ t₁ t₁, t₁ t₁ t₁ t₂, t₁ t₁ t₂ t₁,