Нижегородский Государственный Технический Университет
им.
Кафедра «Вычислительные системы и технологии»
Лабораторная работа №1
«Расчет вычислительной сложности алгоритмов»
Выполнил:
студент группы М14-ИВТ-3
Проверил:
Нижний Новгород
2015 год
Задание №2
Найти оценку средней трудоемкости алгоритма с использованием методов теории марковских цепей. Операторы сочленений и переходов имеют нулевую трудоемкость. Каждую ненулевую трудоемкость необходимо увеличить на 929.
Выполнение.
Увеличим трудоемкости и перерисуем блоксхему:
Представим заданную организацию в виде графа:
Запишем систему из семи уравнений вида 
и решим её:
Средняя трудоемкость алгоритма рассчитывается по формуле 
. Вычислим её с использованием полученных данных: 
Задание №4
Найти оценку средней трудоемкости алгоритма с использованием метода последовательных упрощений. Операторы сочленений и переходов имеют нулевую трудоемкость. Каждую ненулевую трудоемкость необходимо увеличить на 929.
Выполнение.
Увеличим трудоемкости и перерисуем блоксхему:
Исключим последовательные сочленения J и K (правило последовательных связей), а также оператор перехода L (правило параллельных связей):
Исключим сочленение E по правилу последовательных связей и объединим последовательно соединённые операторы:
Исключим сочленение A и функциональный оператор рядом с ним по правилу последовательных связей:
Исключим оператор перехода F по правилу параллельных связей:
Вычислим полученные трудоемкости функциональных операторов:
Исключим цикл первого ранга B=>(J, K,E, A) по правилу циклов:
Исключим цикл первого ранга C=>(J, K,E, A) по правилу циклов:
Исключим цикл первого ранга D=>(J, K,E, A) по правилу циклов:
Объединим функциональные операторы по правилу последовательных связей и получим ответ:
Задание №5
Найти оценки минимальной, средней и максимальной трудоемкостей алгоритма с использованием сетевого подхода. Операторы сочленений и переходов имеют нулевую трудоемкость. Каждую ненулевую трудоемкость необходимо увеличить на 929.
Выполнение.
Увеличим трудоемкости и перерисуем блоксхему:
Представим заданную организацию в виде графа с выделенными циклами:
Цикл C1:
Среднее число повторов цикла: 
; 
Минимальное число повторов цикла: 
; 
Максимальное число повторов цикла: 
; 
Средняя трудоемкость тела цикла: 
Минимальная трудоемкость тела цикла: 
Максимальная трудоемкость тела цикла:
Средняя эквивалентная трудоемкость тела цикла:
Минимальная эквивалентная трудоемкость тела цикла:
Максимальная эквивалентная трудоемкость тела цикла:
Цикл C2:
Среднее число повторов цикла: 
; 
Минимальное число повторов цикла: 
; 
Максимальное число повторов цикла: 
; 
Средняя трудоемкость тела цикла: 
Минимальная трудоемкость тела цикла: 
Максимальная трудоемкость тела цикла:
Средняя эквивалентная трудоемкость тела цикла:
Минимальная эквивалентная трудоемкость тела цикла:
Максимальная эквивалентная трудоемкость тела цикла:
Заменим циклы эквивалентными трудоемкостями и получим граф:
Средняя трудоемкость: 
Минимальная трудоемкость:
Максимальная трудоемкость:
Вывод
При выполнении лабораторной работы были освоены основные способы оценки минимальной, средней и максимальной вычислительной сложности алгоритмов, а также были решены нетривиальные задачи с использованием возможных способов решения.
