М инистерство образования и науки РФ
ФГБОУ ВПО «Сибирский государственный технологический университет»
Факультет автоматизации и информационных технологий
Кафедра системотехники
Расчетно-графическая работа
тема: «Методы анализа вычислительных систем»
(СТ 220301.023 РГР)
Руководитель:
__________________ Михайлов А.С.
(подпись)
_______________________________
(оценка, дата)
Выполнил:
Студент группы 22-01
___________________ Бекетов Р.В.
(подпись)
_______________________________
(дата сдачи)
Красноярск – 2011
М инистерство образования и науки РФ
ФГБОУ ВПО «Сибирский государственный технологический университет»
Факультет автоматизации и информационных технологий
Кафедра системотехники
Учебная дисциплина: Теория Вычислительных Процессов и Систем
ЗАДАНИЕ
на расчетно-графическую работу
Тема: Методы анализа вычислительных систем
Вариант – 2
Студент: Бекетов Р.В.
группа 22-01
Дата выдачи: ___________2011г.
Срок выполнения:___________
Руководитель: Михайлов А.С.
Исходные данные:
Цепь Маркова
Данные:
Составить матрицу переходных вероятностей P
Вычислить векторы вероятностей X(t) попадания в каждое из состояний для 5 шагов при старте из заданного состояния
Выделить множество невозвратных состояний T и множество эргодических состояний Ť. Выписать матрицы переходных вероятностей Q и R для каждого из множеств
Для заданного начального состояния вычислить среднее число тактов пребывания процесса в каждом из невозвратных состояний путем вычисления матрицы T, а так же среднюю трудоемкость вычислительного процесса до попадания во множество эргодических состояний.
Оценить средне квадратичное отклонение от среднего числа пребывания процесса во множестве невозвратных состояний и соответствующее средне квадратичное отклонение трудоемкости вычислений .
Оценить предельные вероятности пребывания процесса во множестве эргодических состояний (за исключением поглощающих) путем приведения матрицы R к диагональной форме.
Сеть Петри
Данные:
Составить список позиций и переходов, матрицы инцидентности F(p,t) и F(t,p) для данной Сети Петри
Для начальной разметки Сети Петри составить дерево разметок на глубину до 5 шагов или до общего числа разметок, равного 100. При обнаружении повторяющихся разметок они помечаются значками Mpi, где i номер обнаруженной повторяющейся разметки, а построение дерева продолжается только из одной из них. Циклические разметки, т.е. повторяющиеся на одном пути в дереве, обозначаются Mci. Тупиковые разметки обозначаются Mti.
Выписать все получение слова свободного языка Сети Петри, начиная с пустого слова. Аналогично п.2 указать повторения, циклы, тупики.
Оценить свойства Сети Петри: ограниченность, консервативность, безопасность, живость.
Найти инварианты Сети Петри.
Задание выдано ___________________
Руководитель: Михайлов А.С.
Реферат
Данная расчетно-графическая работа представляется собой моделирование вычислительных процессов с помощью цепей Маркова и сетей Петри
Расчетно-графическая работа содержит: 17 листов, 4 картинки, одно приложение, 3 использованных литературных источника.
Цель работы: расчет цепей Маркова и сетей Петри
Метод исследования: MATCAD 14
Оглавление
Реферат 5
Введение 8
1. Расчет цепи Маркова 9
1.1 Начальное состояние: 9
1.2 Составим матрицу переходных вероятностей P: 9
1.3 Вычисляем векторы вероятностей X(t) попадания в каждое из состояний для 5 шагов при старте их начального состояния: 9
1.4 Выделяем множество невозвратных состояний: 9
1.5 Находим матрицу переходных состояний: 9
1.6 Среднее число тактов пребывания процесса: 10
1.7 Находим дисперсию числа тактов пребывания процесса: 10
1.8 Находим трудоемкость среднего числа пребываний: 10
1.9 Находим среднеквадратичное отклонение трудоемкости: 11
1.10 Находим среднеквадратичную трудоемкость среднего числа пребываний: 11
1.11 Вычисление предельных состояний 11
1.12 Находим собственный вектор собственных чисел: 11
1.13 Находим собственные числа: 12
1.14 Находим матрицу собственных чисел: 12
1.15 Находим предельную матрицу P: 12
1.16 Находим Х предельное: 12
2. Расчет сети Петри 13
2.2 Составляем матрицы F(p,t) и F (t,p): 13
2.3 Дерево разметок: 13
2.4 Свободный язык сети Петри: 13
2.5 Определяем свойства сети Петри: 14
2.6 Определяем свойства переходов сети Петри: 14
2.7 Находим инварианты сетей Петри: 14
Заключение 17
Список используемых источников 18
Приложение А 19
Введение
Теория вычислительных систем (ВС) – инженерная дисциплина, объединяющая методы решения задач исследования и функционального проектирования ЭВМ, вычислительных комплексов, систем и сетей.
Предметом теории ВС являются вычислительные системы с точки зрения их функционирования, производительности и стоимости.
Задачи ВС:
Задача анализа. Анализ ВС – определение свойств, присущих системе или классу систем. Оценка производительности и надежности системы с заданной конфигурацией, режимом функционирования и рабочей нагрузкой.
Задача синтеза. Выбор структуры системы, вектора параметров характеристик системы и стратегии управления вычислительными процессами оптимизирующих значение критерия эффективности системы при наличии зависимостей критерия структуры, параметров и стратегии управления.
Цепь Маркова - последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого.
Сеть Петри – это математическая модель дискретных динамических систем (параллельных программ, операционных систем, ЭВМ и их устройств, сетей ЭВМ), ориентированная на качественный анализ и синтез таких систем (обнаружение блокировок, тупиковых ситуаций, и узких мест, автоматический синтез параллельных программ и компонентов ЭВМ и др.)
Расчет цепи Маркова
Начальное состояние:
Составим матрицу переходных вероятностей P:
Вычисляем векторы вероятностей X(t) попадания в каждое из состояний для 5 шагов при старте их начального состояния:
Выделяем множество невозвратных состояний:
Глядя на x100 мы определим невозвратные состояния: S1,S2,S3,S4.
Находим матрицу переходных состояний:
Среднее число тактов пребывания процесса:
Находим дисперсию числа тактов пребывания процесса:
Где,
Находим трудоемкость среднего числа пребываний:
Находим среднеквадратичное отклонение трудоемкости:
Находим среднеквадратичную трудоемкость среднего числа пребываний:
Вычисление предельных состояний
Находим разложение матрицы P:
P=U*λ*U^-1
Находим собственный вектор собственных чисел:
Находим собственные числа:
Находим матрицу собственных чисел:
Находим предельную матрицу P:
Находим Х предельное:
И оно равно, найденному ранее, x100
Расчет сети Петри
Начальная разметка :
M0=(2 1 0 0 1 1)
Составляем матрицы F(p,t) и F (t,p):
Дерево разметок:
См. приложение А
Свободный язык сети Петри:
L(N)={λ, t1, t2, t3 ,t5 ,t6 ,t1t5 ,t1t6 ,t2t1 ,t2t2 ,t2t3 ,t2t5 ,t2t6 ,t3t4 ,t3t5 ,t3t6 ,t5t1 ,t5t2 ,t5t3 ,t6t1 ,t6t2 ,t6t3 ,t1t6t1 ,t1t6t2 ,t1t6t3 ,t2t1t1 ,t2t1t2 ,t2t1t3 ,t2t1t5 ,t2t1t6 ,t2t2t1 ,t2t2t2 ,t2t2t3 , t2t2t5 ,t2t2t6 ,t2t3t1 ,t2t3t2, t2t3t4 ,t2t3t5 ,t2t3t6 ,t2t5t1 ,t2t5t2 , t2t5t3 ,t2t5t4 , t2t6t1 , t2t6t2 , t2t6t3 ,t3t4t5 , t3t4t6 , t3t5t4 , t3t6t1 , t3t6t2 , t3t6t4 , t5t2t1 , t5t2t2 , t5t2t3 , t5t2t4 , t5t2t5 ,t2t5t6, t5t3t4, t6t1t1, t6t1t2, t6t1t3, t6t2t1, t6t2t2, t6t2t3, t6t3t1, t6t3t2, t6t3t4}