М инистерство образования и науки РФ

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

Факультет автоматизации и информационных технологий

Кафедра системотехники

 

 

 

 

Расчетно-графическая работа

 

тема: «Методы анализа вычислительных систем»

(СТ 220301.023 РГР)

 

 

Руководитель:

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

(подпись)

_______________________________

(оценка, дата)

Выполнил:

Студент группы 22-01

___________________ Бекетов Р.В.

(подпись)

_______________________________

(дата сдачи)

 

 

Красноярск – 2011

М инистерство образования и науки РФ

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

Факультет автоматизации и информационных технологий

Кафедра системотехники

Учебная дисциплина: Теория Вычислительных Процессов и Систем

ЗАДАНИЕ

на расчетно-графическую работу

Тема: Методы анализа вычислительных систем

Вариант – 2

Студент: Бекетов Р.В.

группа 22-01

Дата выдачи: ___________2011г.

Срок выполнения:___________

Руководитель: Михайлов А.С.

Исходные данные:

1. Цепь Маркова

Данные:

1. Составить матрицу переходных вероятностей P

2. Вычислить векторы вероятностей X(t) попадания в каждое из состояний для 5 шагов при старте из заданного состояния

3. Выделить множество невозвратных состояний T и множество эргодических состояний Ť. Выписать матрицы переходных вероятностей Q и R для каждого из множеств

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

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

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

2. Сеть Петри

Данные:

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

2. Для начальной разметки Сети Петри составить дерево разметок на глубину до 5 шагов или до общего числа разметок, равного 100. При обнаружении повторяющихся разметок они помечаются значками Mpi, где i номер обнаруженной повторяющейся разметки, а построение дерева продолжается только из одной из них. Циклические разметки, т.е. повторяющиеся на одном пути в дереве, обозначаются Mci. Тупиковые разметки обозначаются Mti.

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

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

5. Найти инварианты Сети Петри.

Задание выдано ___________________

Руководитель: Михайлов А.С.

Реферат

Данная расчетно-графическая работа представляется собой моделирование вычислительных процессов с помощью цепей Маркова и сетей Петри

Расчетно-графическая работа содержит: 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

Введение

Теория вычислительных систем (ВС) – инженерная дисциплина, объединяющая методы решения задач исследования и функционального проектирования ЭВМ, вычислительных комплексов, систем и сетей.

Предметом теории ВС являются вычислительные системы с точки зрения их функционирования, производительности и стоимости.

Задачи ВС:

1. Задача анализа. Анализ ВС – определение свойств, присущих системе или классу систем. Оценка производительности и надежности системы с заданной конфигурацией, режимом функционирования и рабочей нагрузкой.

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

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

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

1. Расчет цепи Маркова

1. Начальное состояние:

2. Составим матрицу переходных вероятностей P:

3. Вычисляем векторы вероятностей X(t) попадания в каждое из состояний для 5 шагов при старте их начального состояния:

4. Выделяем множество невозвратных состояний:

Глядя на x100 мы определим невозвратные состояния: S1,S2,S3,S4.

5. Находим матрицу переходных состояний:

6. Среднее число тактов пребывания процесса:

7. Находим дисперсию числа тактов пребывания процесса:

Где,

8. Находим трудоемкость среднего числа пребываний:

9. Находим среднеквадратичное отклонение трудоемкости:

10. Находим среднеквадратичную трудоемкость среднего числа пребываний:

11. Вычисление предельных состояний

Находим разложение матрицы P:

P=U*λ*U^-1

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

13. Находим собственные числа:

14. Находим матрицу собственных чисел:

15. Находим предельную матрицу P:

16. Находим Х предельное:

И оно равно, найденному ранее, x100

2. Расчет сети Петри

1. Начальная разметка :

M0=(2 1 0 0 1 1)

2. Составляем матрицы F(p,t) и F (t,p):

3. Дерево разметок:

См. приложение А

4. Свободный язык сети Петри:

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}