- •Общие вопросы моделирования. Понятие модели. Классификация моделей. Модели физические, абстрактные, смешанные.
- •Виды моделей. Способ реализации моделирования и степень отражения в моделях времени и неопределенности.
- •Объект моделирования – вычислительная система. Основные задачи исследования объекта, их характеристика и методы решения.
- •Графовые модели алгоритмов и программ. Построение графовых моделей.
- •Эквивалентные преобразования графовых моделей алгоритмов и программ.
- •Марковские случайные процессы и их место при построении и исследовании вероятностных моделей объектов.
- •Дискретные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
- •Потоки событий. Основные понятия и определения. Простейший поток событий и потоки Эрланга.
- •Непрерывные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
- •Типовые графы состояний системы. Процесс “гибели и размножения”. Примеры объектных систем.
- •Типовые графы состояний системы. Циклический процесс. Примеры объектных систем.
- •Методы исследования немарковских случайных процессов, сводящихся к марковским.
- •Теория массового обслуживания и ее место при построении и исследовании вероятностных моделей объектов. Основные понятия и определения.
- •Системы массового обслуживания (смо). Обобщенная структура смо.
- •Основные параметры и характеристики смо.
- •Разомкнутые смо с очередью и нетерпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо с очередью и терпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо без потерь. Примеры объектных систем.
- •Замкнутые смо с простейшими потоками событий. Примеры объектных систем.
- •Смо с произвольными потоками событий. Случай бесприоритетной дисциплины обслуживания.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с относительным приоритетом.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с абсолютным приоритетом.
- •Сети массового обслуживания с простейшими потоками событий. Анализ разомкнутой сети. Примеры объектных систем.
- •Сети массового обслуживания с простейшими потоками событий. Анализ замкнутой сети. Примеры объектных систем.
- •Статистическое моделирование случайных процессов. Организация статистического моделирования. Моделирование базовых случайных величин (св).
- •Моделирование непрерывной случайной величины с произвольным распределением. Моделирование дискретной св. Моделирование случайных событий и потоков случайных событий.
-
Эквивалентные преобразования графовых моделей алгоритмов и программ.
Задача – получить сетевую модель. Данная задача решается в два этапа:
-
“СА -> ГМ” – преобразование схемы алгоритма в графовую модель определенного вида (псевдосетевую модель). Псевдосетевая модель отличается от сетевой только наличием контуров.
-
“ГМ -> СМ” – преобразование графовой модели в сетевую модель, то есть избавление от контуров.
Рассмотрим второй этап – построение сетевой модели (“СА -> ГМ”).
Из графовой модели сетевую модель можно получить с помощью системы эквивалентных преобразований. Система эквивалентных преобразований ориентированных графов устанавливает эквивалентность параметров исходного подграфа с параметрами простой ветви (две вершины, одна дуга).
Существует 3 правила эквивалентных преобразований:
-
Последовательные соединения одинаково направленных дуг.
mil = mis + msl – мат.ожидание
Dil = Dis + Dsl – дисперсия
pil = pis*psl
-
Параллельное соединение одинаково направленных дуг.
-
Элементарный контур.
Элементарный контур – это контур, в котором совпадают исходящая и входящая вершины и не содержится промежуточных вершин.
Исключение элементарного контура изменяет ресурсные параметры и вероятность прохождения для каждой дуги.
Для графовой модели применяется правило последовательного использования трех правил:
-
Есть ли промежуточные вершины?
-
ДА => Есть ли элементарный контур?
-
ДА => Применяем правило 3, вернуться к пункту 1.
-
НЕТ => Применяем правило 1, вернуться к пункту 1.
-
-
НЕТ => Есть ли параллельные дуги?
-
ДА => Применяем правило 2.
-
НЕТ => Конец
-
-
Циклы
-
Циклы с фиксированным числом повторений – известно n – число повторений, или мат.ожидание m(n).
-
Цикл с постусловием.
Всего событий n, нас устраивает одно, поэтому вероятность выхода из цикла:
Или
-
Цикл с предусловием.
Всего событий n+1, нас устраивает одно, поэтому вероятность выхода из цикла:
Или
-
Цикл с заранее не фиксированным числом повторений.
Рассмотрим вероятность выхода из цикла q(n):
n |
1 |
2 |
3 |
… |
k |
… |
N |
q(n) |
p |
(1-p)*p |
(1-p)2*p |
… |
(1-p)k-1*p |
… |
(1-p)N-1*p |
-
Если известно m(n), то
-
Если известно q(n), то
-
Разветвление в результате проверки неравенства (x<C) или (x>C).
x – переменная, , c = const.
Если х – непрерывная случайная величина (НСВ):
Если x – равномерная СВ:
-
Марковские случайные процессы и их место при построении и исследовании вероятностных моделей объектов.
Состояние – это внутренняя характеристика объекта/процесса, позволяющая определить текущие или будущие реакции объекта/процесса на предполагаемые внешние воздействия.
Последовательность смены состояний образует случайный процесс (примеры случайных процессов – процесс отказов аппаратуры, процесс поступления заявок на обслуживание). Если фактором случайности пренебречь нельзя, строится стохастическая (вероятностная) модель.
Случайный процесс называется марковским, если для любого произвольного момента t0 поведение этого объекта или процесса в будущем определяется только текущим состоянием объекта в момент t0 и не зависит от того, как мы попали в это состояние (то есть не зависит от предыстории). Пример – счетчик Гейгера (количество заряженных частиц N).