Пример ЛР1. Лабораторная работа 1 по дисциплине Компьютерные системы Методика расчета трудоемкости выполнения алгоритма

• Название: Лабораторная работа 1 по дисциплине Компьютерные системы Методика расчета трудоемкости выполнения алгоритма
• Дата: 15.04.2022
• Размер: 2.66 Mb.
• Имя файла: Пример ЛР1.pdf
• Тип: Лабораторная работа; #477416

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное образовательное учреждение высшего образования
«Крымский федеральный университет им. В.И. Вернадского»
Физико-технический институт
Кафедра компьютерной инженерии и моделирования
ЛАБОРАТОРНАЯ РАБОТА №1 по дисциплине
«Компьютерные системы»
«Методика расчета трудоемкости выполнения алгоритма»
Выполнил:
Cтудент 3 курса
Направления подготовки ИВТ
Группа ИВТ-б-о-192(1)
Мусаелян А.К
Проверил:
Руденко М.А.
Симферополь
2021

2
Цель работы: провести расчет трудоемкости заданного алгоритма на основе теории
Марковских цепей и сетевого подхода.
Вариант 4
Ход работы
Теоретические сведения
Трудоемкость алгоритма – это количество вычислительной работы, требуемой для реализации алгоритма.
Оценка трудоемкости алгоритмов проводится на основе теории марковских цепей и сетевого подхода.
Марковские цепи – это последовательность случайных событий с конечным или счетным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии. Распределение вероятностей переходов обычно представляется в виде матрицы.
Если цепь Маркова имеет N возможных состояний, то матрица будет иметь вид N x N, в которой запись (I, J) будет являться вероятностью перехода из состояния I в состояние J. Кроме того, такая матрица должна быть стохастической, то есть строки или столбцы в сумме должны давать единицу. В такой матрице каждая строка будет иметь собственное распределение вероятностей. Цепь Маркова имеет начальный вектор состояния, представленный в виде матрицы N x 1. Он описывает распределения вероятностей начала в каждом из N возможных состояний. Запись I описывает вероятность начала цепи в состоянии I.
Суть сетевого подхода состоит в выделении путей на графе алгоритма, соответствующих минимальной, средней и максимальной трудоемкости последовательности операторов. Эти пути могут быть выделены только на графах, не содержащих циклов. По этой причине методика сетевого подхода начинается с анализа трудоемкости алгоритмов, не содержащих циклы. Затем рассматривается прием исключения циклов из графа алгоритма путем замены их операторами с эквивалентной трудоемкостью. Этот прием позволяет распространить сетевой подход на любые алгоритмы, в том числе содержащие любое количество циклов.
Задание представлено в виде графа алгоритма работы системы, в таблице снизу указаны трудоемкости для каждой из операций.
Все вычисления выполнены в программе PTC Mathcad Express Prime 7.0.0.0

3
1. Расчет трудоемкости алгоритма методом марковских цепей.
Решение задачи определения трудоемкости алгоритма сводится к вычислению среднего числа n
1
,…,n
k-1
пребываний марковского процесса в невозвратных состояниях. Одним из способов расчета указанных величин является нахождение корней системы линейных алгебраических уравнений.
Запишу уравнения, составленные согласно графу, в дифференциальной форме:
{
𝑑𝑝
1
𝑑𝑡
= 1 − 𝑝
1
(𝑡)
𝑑𝑝
2
𝑑𝑡
= 𝑝
1
(𝑡) − 𝑝
2
(𝑡) + 0.31𝑝
10
𝑑𝑝
3
𝑑𝑡
= 0.22𝑝
2
(𝑡) − 𝑝
3
(𝑡)
𝑑𝑝
4
𝑑𝑡
= 𝑝
3
(𝑡) + 0.4𝑝
6
(𝑡) − 𝑝
4
(𝑡)
𝑑𝑝
5
𝑑𝑡
= 𝑝
4
(𝑡) − 𝑝
5
(𝑡)
𝑑𝑝
6
𝑑𝑡
= 𝑝
5
(𝑡) − 𝑝
6
(𝑡)
𝑑𝑝
7
𝑑𝑡
= 𝑝
2
(𝑡) − 𝑝
7
(𝑡)
𝑑𝑝
8
𝑑𝑡
= 𝑝
7
(𝑡) − 𝑝
8
(𝑡)
𝑑𝑝
9
𝑑𝑡
= 𝑝
8
(𝑡) + 0.6𝑝
6
(𝑡) − 𝑝
9
𝑑𝑝
10
𝑑𝑡
= 𝑝
9
(𝑡) − 𝑝
10
(𝑡)

4
Необходимо преобразовать составленную систему дифференциальных уравнений в СЛАУ:
{
−𝑝
1
(𝑡) = −1
𝑝
1
(𝑡) − 𝑝
2
(𝑡) + 0.31𝑝
10
= 0 0.22𝑝
2
(𝑡) − 𝑝
3
(𝑡) = 0
𝑝
3
(𝑡) + 0.4𝑝
6
(𝑡) − 𝑝
4
(𝑡) = 0
𝑝
4
(𝑡) − 𝑝
5
(𝑡) = 0
𝑝
5
(𝑡) − 𝑝
6
(𝑡) = 0
𝑝
2
(𝑡) − 𝑝
7
(𝑡) = 0
𝑝
7
(𝑡) − 𝑝
8
(𝑡) = 0
𝑝
8
(𝑡) + 0.6𝑝
6
(𝑡) − 𝑝
9
(𝑡) = 0
𝑝
9
(𝑡) − 𝑝
10
(𝑡) = 0
Составлена матрица коэффициентов и свободных членов
Найдено среднее число обращений к конкретному узлу
Найдена трудоемкость алгоритма методом марковских цепей
2. Расчет минимальной, средней и максимальной трудоемкости алгоритма сетевым методом.

5
Вычислю среднее число повторений первого и второго циклов.
𝑄ср = 𝑘1 + 1.449(𝑘2 + 0.22𝑘3 + 0.22 ∗ 1.667(𝑘4 + 𝑘5 + 𝑘6) + 0.78(𝑘7 + 𝑘8) + 𝑘9 + 𝑘10)
Чтобы вычислить Qmin необходимо сложить трудоемкость операторов, не входящих в циклы. Есть два варианта: 1-2-3-4-5-6-9-10 и 1-2-7-8-9-10. Для первого варианта трудоемкость равна
3450, для второго – 2780.
𝑄𝑚𝑎𝑥 = 𝑘1 + 𝑛𝑐2max⁡(𝑘2 + 𝑘3 + 𝑛𝑐1 max(𝑘4 + 𝑘5 + 𝑘6) + 𝑘9 + 𝑘10
nc1max=5, nc2max=5
Вывод: В ходе выполнения лабораторной работы была найдена средняя трудоемкость алгоритма, согласно двум методам – 4246. При помощи сетевого метода была найдена минимальная трудоемкость, которая соответствует операторам: 1-2-7-8-9-10. Максимальная трудоемкость зависит от количества прохода циклов алгоритма, количество которых может быть велико. В итоге получено значение 45530.
Для расчета параметров компьютерной системы выбрано значение средней трудоемкости.