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

Г.А. Доррер

 

А.С. Михайлов

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

 

 

 

Красноярск 2015

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ Р ОССИЙСКОЙ ФЕДЕРАЦИИ

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

 

 

Г.А. Доррер

                                            

А.С. Михайлов

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

 

 

Утверждено редакционно-издательским советом СибГТУ

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

09.03.01 «Информатика и вычислительная техника»

профиль подготовки «Программное обеспечение вычислительной техники и автоматизированных систем»,

09.03.02 «Информационные системы и технологии»

профиль подготовки «Информационные системы и технологии в промышленности»,

09.03.04 «Программная инженерия»

 профиль подготовки «разработка программно-информационных систем»

 

Очной, заочной, очно-заочной форм обучения

 

 

Красноярск 2015

Доррер, Г.А. Теория вычислительных процессов и систем: Лабораторный практикум для студентов направлений подготовки09.03.01 «Информатика и вычислительная техника» профиль подготовки «Программное обеспечение вычислительной техники и автоматизированных систем», 09.03.02 «Информационные системы и технологии» профиль подготовки «Информационные системы и технологии в промышленности», 09.03.04 «Программная инженерия» профиль подготовки «разработка программно-информационных систем»/ Г.А. Доррер, А.С. Михайлов. – Красноярск: СибГТУ, 2015. - 73с.

 

Лабораторный практикум содержит 8 лабораторных работ по основным темам курса «Теория вычислительных процессов и систем»: цепи Маркова, обыкновенные и раскрашенные сети Петри. Тематика лабораторных работ имеет профессиональную направленность. В конце каждой лабораторной работы имеются контрольные вопросы для проверки усвоения темы.

 

 

Рецензенты:

 

Канд. техн. наук, доцент С.А. Яркова, (КрИЖТ ИрГУПС);

канд. техн. наук, доцент Т.Г. Зингель, (научно-методический совет СибГТУ).

 

© ФГБОУ ВПО “Сибирский государственный технологический университет”, 2015

© Доррер Г.А.,

©Михайлов А.С.

 

 

Содержание

 

1 Цепи Маркова. 6

Лабораторная работа № 1. Моделирование динамики систем на основе цепей Маркова с дискретным временем (часть 1) 19

Лабораторная работа № 2. Моделирование динамики систем на основе цепей Маркова с дискретным временем (часть 2) 24

Лабораторная работа № 3. Моделирование динамики систем на основе цепей Маркова с непрерывным временем. 26

2 Сетевые модели. 28

Лабораторная работа № 4 Моделирование систем с помощью обыкновенных сетей Петри 43

Лабораторная работа № 5 Моделирование систем с помощью ингибиторных сетей Петри 47

3 Раскрашенные (цветные) сети Петри (CPN) 49

Лабораторная работа № 6 Моделирование систем с помощью раскрашенных сетей Петри 61

Лабораторная работа № 7. Исследование раскрашенных сетей Петри с временным механизмом. 66

Лабораторная работа № 8. Разработка и исследование модели деятельности 70

Библиографический список. 72

 

 

Введение

Данный практикум по «Теории вычислительных процессов и систем» дает возможность получить практические навыки работы с современными программными пакетами в области моделирования вычислительных процессов и систем.

Практикум предназначен для изучения дисциплины «Теория вычислительных процессов и систем» студентами направлений 09.03.01, 09.03.02, 09.03.04 очной формы обучения, которая изучается в 5 семестре. Он также может быть использован при изучении дисциплины «Теория информационных процессов и систем» студентами направления 09.03.02 очной и очно-заочной (дистанционной) форм обучения.

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

Успешное освоение лабораторного практикума способствует формированию у студента следующих профессиональных компетенций:

для направления 09.03.01

ПК-2 - освоение методики использования программных средств для решения практических.

для направления 09.03.02

ПК-5 - способность проводить моделирование процессов и систем;

ПК-12 - способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные);

ПК-24 - способность обосновывать правильность выбранной модели, сопоставляя результаты экспериментальных данных и полученных решений.

для направления 09.03.04

ПК-13 - готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности;

ПК-14 - готовность обосновывать принимаемые проектные решения, осуществлять постановку и выполнение экспериментов по проверке их корректности и эффективности.

 

Для выполнения лабораторных работ необходима компьютерная аудитория с программным обеспечением, содержащим пакет CPN-Tools, MathCad и выходом в Интернет.

Номера вариантов лабораторных работ определяет преподаватель.

Цепи Маркова

Цель работы

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

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

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

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

1) Изучить теоретический материал по ЦМ по учебнику
(п. 3.1) или лекциям.

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

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

4) Составить алгоритм имитационного моделирования динамики ЦМ, написать и отладить программу на языке высокого уровня. Один из возможных вариантов алгоритма приведен ниже.

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

Оформление отчета по работе

Отчет по лабораторной работе должен содержать:

· титульный лист с указанием всех исполнителей и номера группы;

· исходные данные по ЦМ – граф состояний и матрицу переходных вероятностей;

· матрицу переходных вероятностей P и вектор начальных условий X (0);

· таблицу векторов X (t), t =0,1,…15, полученных по формуле  и график , j =1,… n, t =0,…15;

· листинг программы имитационного моделирования ЦМ;

· таблицу векторов X (t), полученных с помощью имитационной программы при различном числе экспериментов (N =100, 2000, 2000) и график , j =1,… n, t =0,…15. Оценить влияние числа N на точность имитационного моделирования.

 

Алгоритм

1. Создаем два массива X и Y длиной n. Заполняем массив X нулями. полагаем t_k =1.

2. Полагаем t =0 и помещаем 1 в позицию j ₀  массива Y, остальные элементы этого массива – нули.

3. Выполняем основной шаг алгоритма – определяем номер очередного состояния j. Прибавляем 1 к элементу Y [ j ]. Увеличиваем t на 1.

4. Повторяем шаг 3 до тех пор, пока .

5. Пересчитываем X:= X + Y.

6. Повторяем шаги 2 – 5 N раз.

7. Вычисляем значения X [ j ] = X [ j ] / N, j =1,.. n, которые являются оценками среднего числа пребываний процесса в j -м состоянии.

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

9. Повторяем шаги 1-7 для всех , .

 

Основной шаг алгоритма

Пусть в момент времени t система находится в состоянии S_k. Определим номер состояния, в которое система перейдет в момент t +1. Выделим k – ю строку матрицы P:

p_k = [ p_{k 1}, p_{k 2} ,…, p_kn ],

С помощью датчика случайных чисел генерируем случайное число r (t),  с равномерным законом распределения.Тогда номер состояния j определится условием:

Иными словами, j – это номер элемента строки p_k, для которого сумма  при возрастании j от 1 до n впервые не меньше r (t).

Исходные данные к работе

 

Таблица	mмах 1/с		5	10	7	1	2	4	0.1	1.2	8	5	12	10	7	0.2	2	4	8	15	0.5	1.2	2.5	8	10.5	8	15
	Трудоемкости, С,	С7	-	-	2	2	2	3	-	-	-	-	1	1	1	-	-	5	6	3	8	-	-	-	-	7	3
		С6	2	3	7	3	6	3	6	2	7	1	9	3	8	1	3	2	3	6	7	6	1	5	8	2	6
		С5	7	8	4	3	7	3	9	3	8	2	9	6	7	6	7	1	2	6	7	8	1	5	8	3	6
		С4	7	6	6	4	6	4	7	5	8	4	7	6	6	6	9	3	4	7	6	8	3	6	7	3	8
			10	9	3	5	5	4	5	7	6	6	3	6	9	9	6	3	4	7	6	4	5	6	7	4	2
		С	5	4	5	2	4	3	3	9	3	8	5	8	9	5	3	8	7	8	1	3	5	7	1	5	7
		С	3	4	2	1	3	2	1	6	2	5	1	2	1	2	3	5	6	5	1	2	6	4	1	5	7
	Вероятности перехода Рk ´10	Р10	1	2	3	3	1	2	-	-	-	-	2	8	7	3	5	4	4	1	2	-	-	-	-	5	3
		Р9	3	2	1	1	1	1	5	6	5	1	1	9	7	1	5	2	2	2	2	3	3	2	1	5	4
		Р8	3	2	3	3	5	2	5	1	5	4	2	3	1	2	6	3	3	1	3	2	3	4	3	4	3
		Р7	2	5	1	2	1	5	2	5	2	5	5	3	3	1	1	3	4	2	6	2	3	3	3	4	2
		Р6	5	3	3	3	5	1	5	5	3	2	3	2	4	7	3	5	1	6	2	3	3	2	3	4	3
		Р5	5	3	2	4	2	2	3	4	3	2	4	3	5	4	3	3	7	3	4	3	4	3	2	4	3
		Р4	4	1	7	8	2	2	3	4	5	3	3	3	5	3	5	6	5	1	1	6	1	3	4	1	1
		Р3	7	2	5	3	3	4	3	4	2	5	4	3	2	1	2	4	2	1	6	2	6	3	4	6	7
		Р2	3	5	2	3	2	3	4	4	5	4	2	3	1	5	2	3	1	5	1	7	1	3	2	4	1
		Р1	3	4	2	3	2	3	3	4	2	3	5	2	5	2	3	1	3	4	5	2	8	4	4	3	4
	Схема,вход		A1	А2	Б1	Б2	В1	В2	Г1	Г2	Д1	Д2	Е1	Е2	Е3	А1	А2	Б1	Б2	В1	В2	Г1	Г2	Д1	Д2	Е1	Е2
	№ вар		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

 

Исходные данные представлены в виде таблицы и набора схем. По указанному преподавателем номеру варианта в таблице выбирается соответствующая строка. Второй столбец таблицы указывает код схемы и стартовое состояние (например, Г1 – схема Г, старт происходит из состояния S 1). Далее указаны вероятности перехода между состояниями в десятых долях (т.е. указанное в таблице значение  означает, что ). Этими вероятностями помечены дуги на схеме. Некоторые дуги не помечены – соответствующие вероятности определяются из условия, что сумма вероятностей на дугах, отходящих от каждого узла, равна единице. Следующая группа столбцов задает трудоемкости отдельных процессов  в секундах. В последнем столбце указаны величины  (1/с), которая используется в лабораторной работе №3

 

 

 

Б

 

 

P4

В

 

Г

P5

 

Д

 

Е

Контрольные вопросы

1 Дайте определение дискретной цепи Маркова.

2 Какими свойствами обладают матрица переходных вероятностей?

3 Как рассчитываются вероятности нахождения однородной цепи Маркова в определенном состоянии через нужное число тактов?

4 Что такое начальное состояние цепи?

5 Дайте определение однородной цепи Маркова?

Лабораторная работа № 2. Моделирование динамики систем на основе
цепей Маркова с дискретным временем (часть 2)

 

Цели работы

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

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

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

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

1. Изучить теоретический материал по ЦМ по учебному пособию
[1] или лекциям.

2. Для системы заданной в Лабораторной работе №1, провести следующие вычисления.

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

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

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

2.4. Получить оценку строки матрицы , соответствующей заданному стартовому состоянию с помощью модификации программы, составленной в Лабораторной работе №1. Модификация алгоритма заключается в следующем.

1. Выполнение шага 3 прекращается, если очередное состояние  относится к эргодическому множеству: .

2. Исключается шаг 8. на печать выводится результат шага 7.

3. Расчет ведется только для максимального значения , .

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

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

Оформление отчета по работе

Отчет по лабораторной работе должен содержать:

· титульный лист с указанием всех исполнителей и номера группы;

· исходные данные по ЦМ – граф состояний и матрицы переходных вероятностей ; , ;

· матрицу средних значений  и оценку средней трудоемкости процесса ;

· оценку строки матрицы , полученную путем имитационного моделирования;

· матрицу дисперсий  и оценку среднеквадратичного отклонения трудоемкости s_Q;

· листинг модифицированной программы имитационного моделирования ЦМ с подсчетом среднего числа пребываний процесса в различных состояниях;

· оценки предельных вероятностей пребывания процесса в состояниях эргодического множества:

а) путем прямого возведения матрицы  в высокую степень,

б) путем спектрального разложения матрицы.

 

Контрольные вопросы

1 Как определить какие состояния будут невозвратными?

2 Дайте определения невозвратных и эргодических состояний?

3 Как определить число среднее число пребываний цепи  в каком-то невозвратном состоянии?

4 Как имитационно смоделировать фундаментальную матрицу?

5 Что такое трудоемкость процесса исполняемого цепью Маркова?

6 Что такое предельное состояние цепи Маркова?

7 Сформулируйте основные шаги алгоритма нахождения предельного состояния.

Лабораторная работа № 3. Моделирование динамики систем на основе
цепей Маркова с непрерывным временем

 

Цели работы

- освоить основные положения теории конечных цепей Маркова (ЦМ) с непрерывнымвременем.

- научиться составлять и исследовать модели вычислительных систем на основе этой теории.

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

· изучить теоретический материал по учебникам [1], [2], [3] или лекциям.

· создать ЦМ с непрерывным временем на базе модели, рассмотренной в Лабораторных работах №1 и №2. Для этого:

· по заданному номеру варианта из таблицы в Лабораторной работе №1, взять величину  и для всех дуг графа цепи Маркова рассчитать плотности вероятностей переходов .

· составить матрицу p (формула (3.42)).

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

· решить уравнение Колмогорова с заданными начальными условиями с помощью пакета MathCad. Решение вести до получения установившихся значений вектора . Оценить временную шкалу решения исходя из величины . Сравнить график решения с аналогичным графиком, полученным в Лабораторной работе №1, п. 3.

·  Вычислить установившиеся значения вектора  путем решения системы линейных уравнений, полученных из уравнения Колмогорова при  с учетом условия . Сравнить решение с результатом п. 3.

Оформление отчета по работе

Отчет по лабораторной работе должен содержать:

· титульный лист с указанием всех исполнителей и номера группы;

· исходные данные по ЦМ – граф состояний с указанием плотностей вероятностей переходов ;

· матрицу p;

· уравнение Колмогорова в матричном и компонентном виде и начальные условия;

· график решения – все компоненты вектора  с разметкой временной шкалы;

· систему уравнений для вычисления установившегося значения  и ее решение.

 

Контрольные вопросы

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

2 Как составляется уравнение Колмогорова по графу цепи?

3 Как в пакете MathCad получить решение уравнения Колмогорова?

4 Что такое интенсивность непрерывной цепи Маркова?

5 Как сравнивать результаты выполнения лабораторных работ №1 и №3?

Сетевые модели

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

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

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

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

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

 

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

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

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

.                                                             (2.1)

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

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

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

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

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

.

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

,                                      (2.2)

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

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

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

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

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

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

 

 ,                                                (2.3)

 

 .                                                  (2.4)

 

Из вершины - позиции  ведет дуга в вершину - переход  тогда и только тогда, когда . В этом случае говорят, что  - выходной переход позиции .

Множество всех позиций  для которых - выходной переход, будем обозначать . Иными словами, .

Аналогично из каждой вершины перехода  дуга ведет в вершину - позицию , тогда и только тогда, когда . При этом говорят, что - выходная позиция перехода .

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

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

.                                                                  (2.5)

Начальная маркировка   определяет стартовое состояние сети Петри.

Динамика поведения моделируемой системы описывается в терминах функционирования сетей Петри. Как было сказано, сеть функционирует в дискретном времени  в асинхронном режиме, переходя от одной маркировки к другой.

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

,                                                                   (2.6)

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

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

,                                            (2.7)

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

 

р исунок 2.1 Пример сети Петри

 

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

 ,  .

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

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

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

 

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

1) Изучить теоретический материал по учебнику [1], [2] или лекциям. Получить свой вариант задания

2) Составить программу, моделирующую изменение маркировок и построение свободного языка обыкновенной сети Петри.

3) Для заданного варианта задания:

1. Составить список позиций и переходов, матрицы инцидентности F (p,t)  и F (t,p) и начальную маркировку для указанного варианта схемы СП.

2. Для начальной маркировки PN, указанной в таблице, составить дерево разметок на глубину до 5 шагов или до общего числа маркировок, равного 100. При обнаружении повторяющихся маркировок они помечаются значками Mp_i, где i - номер обнаруженной повторяющейся маркировки, а построение дерева продолжается только из одной из них. Циклические маркировки, т.е. повторяющиеся на одном пути в дереве, обозначаются Mc_i. Тупиковые маркировки обозначаются Mt_i.

3. Выписать все полученные слова свободного языка PN, начиная с пустого слова. Аналогично п.2 указать повторения, циклы и тупики.

4. Оценить свойства PN: ограниченность, консервативность, безопасность, живость.

 

Оформление работы

Оформленный отчет по лабораторной работе должен содержать:

- титульный лист с указанием фамилий исполнителей, группы и номера варианта;

- исходную схему с начальной маркировкой;

- матрицы инцидентности;

- дерево маркировок;

- словарь свободного языка PN;

- анализ свойств рассматриваемой PN;

- листинг программы.

Таблица исходных данных

 

№ вари-анта

№ схемы

Начальная маркировка M0