Определение основных параметров реализации алгоритмов на ЭВМ

ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1

«Определение основных параметров реализации алгоритмов на ЭВМ»

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

Рабочее место: Работы выполняются на ПЭВМ. При выполнении работы используется программный комплекс для исследования моделей систем обработки данных.[pic 1]

Рассчитаем основные параметры реализации на ЭВМ алгоритма двумя методами: сетевым и марковским. Граф-схема исходного алгоритма представлена на рис. 1.6, где V0 и Vk обозначают соответственно начальную и конечную вершины графа, Vαi - вершины, соответствующие операторам счета, а Vjβi - вершины, соответствующие операторам обращения к файлам ([pic 2]).

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

Пусть операторы счета Vαi, число которых равно m0=8 ([pic 3]), характеризуются следующими показателями количества операций θVi:

Операторы обращения к файлам Vjβi (где j - номер файла, к которому осуществляется обращение) задаются средним количеством информации li, передаваемой при выполнении данного оператора:

Число операторов ввода-вывода при обращении к каждому из трех файлов (F=3) для данного алгоритма равно: m1=3 (вершины V1β1, V1β2, V1β8); m2=3 (вершины V2β3, V2β4, V2β5); m3=2 (вершины V3β6, V3β7).

Области изменения параметров ветвления алгоритма Xi примем следующие:

X1 = (-2;4); X2 = (-3;3);

а области изменения параметров циклов (максимальное значение счетчиков Ii) Ki примем равными

К1 = 15, К2 = 40, К3 = 10.

При этом счетчики циклов Ii в начале реализации алгоритма устанавливаются в единицу, т.е. I1= I2= I3=1.

Марковский метод

Чтобы уменьшить размерность системы линейных уравнений для определения вероятности выполнения операторов, осуществим объединение последовательных операторов алгоритма. В результате такого преобразования образуется укрупненная граф-схема алгоритма. В один общий оператор могут входить только те вершины ГСА, которые при любых условиях выполнения алгоритма реализуются последовательно. На рис. 1.7 представлена укрупненная ГСА исходного алгоритма, на которой через Аi обозначены операторные вершины.