Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Теоретическая часть).pdf

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

1.4.3 Алгоритмическая конструкция «Цикл»

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

Повторяющийся участок вычисления называется циклом. Цикл организуют по определенным правилам. Циклический алгоритм состоит из подготовки цикла, тела цикла, условия продолжения цикла. В подготовку цикла входят действия, связанные с заданием исходных значений для параметра цикла (начальное и конечное значения, шаг параметра цикла). Иногда при подготовке цикла задаются начальные значения и другим величинам, использующимся в цикле.

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

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

При разработке алгоритма циклической структуры выделяют следующие понятия: параметр цикла – величина, с изменением которой связано многократное выполнение цикла; начальное и конечное значения параметров цикла; шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении. Зависимость, связывающая текущее и предыдущее значения параметра цикла, определяет закон изменения параметра цикла.

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

Все циклические процессы по признаку определения количества повторений разделяются на два класса.

Арифметическим называется циклический процесс, число повторений в котором может быть определено заранее, т.е. не зависит от результатов счёта в теле цикла.

Итерационным является циклический процесс, число повторений в котором зависит от результатов вычислений в теле цикла и не может быть определено заранее.

На приведенных ниже рисунках показаны примеры циклических процессов.

Рисунок 4 - Блок-схема цикла с предусловием

Рисунок 5 - Блок-схема цикла с постусловием

1.5 Анализ алгоритмов

---

1.5.1 Сравнительные оценки алгоритмов

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

Для оперирования с формальной моделью алгоритма рассматривают абстрактную машину, включающую: процессор, поддерживающий адресную память набор элементарных операций соотнесенных с языком высокого уровня. Допущения: каждая команда выполняется не более чем за фиксированное время; исходные данные алгоритма представляются N машинными словами по αθ битов каждое. На входе алгоритма Nα = N*α бит информации Программа, реализующая алгоритм состоит из М машинных инструкций по β битов Мβ = М*β бит информации. Дополнительные ресурсы абстрактной машины на реализацию алгоритма: Sd – память для хранения промежуточных результатов;θ Sγ – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов). При решении конкретной задачи, заданной

N+М+Sd+Sy

словами памяти алгоритм выполняет конечное количество «элементарных» операций абстрактной машины. В связи с этим вводится определение: Под трудоѐмкостью алгоритма Fa (n) для данного конкретного входа¬ для решения конкретной проблемы (задачи)¬ в данной формальной системе¬ понимается количество «элементарных» операций (n) совершаемых алгоритмом. Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной машины, требуемых алгоритмом для решения конкретных задач. Для различных областей применения веса ресурсов ci будут различны.

1.5.2 Классификация алгоритмов по виду функции трудоёмкости

1.Количественно-зависимые по трудоемкости алгоритмы Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fa(n), n=f(N) Пример: • алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.

2. Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется конкретными значениями обрабатываемых слов памяти: Fa(n), n=f(р1…,рi ) У таких алгоритмов на входе два числовых значения – аргумент функции и точность. Пример: • алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Классификация алгоритмов по виду функции трудоёмкости.

---

3. Количественно-параметрические по трудоемкости алгоритмы В большинстве практических случаев функция трудоемкости зависит от количества данных на входе, значений входных данных

Fa(n), n=f (N, р1…, рi )

Пример: • алгоритмы численных методов, в которых существует параметрически зависимый цикл по точности и цикл количественно зависимый по размерности. Среди параметрически - зависимых алгоритмов выделяют группу алгоритмов для которой количество операций зависит от порядка расположения исходных объектов.

Пример: • алгоритмы сортировки,

• алгоритмы поиска минимума/максимума в массиве.

1.6 Трудоемкость алгоритмов и временные оценки

1.6.1 Примеры анализа простых алгоритмов

Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и следовательно является количественно-зависимым. Применение методики анализа конструкции «Цикл 1» дает: Внутренний: f1(n)=1+3n+4n Внешний: f2(n)=1+3n+ n f1(n) Окончательно: F(n)=1+1+3n+n(1+3n+4n)=2+4n+7n 2= Θ( n 2 ) Под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n 2 значений.

Пример 2 Задача поиска максимума в массиве

< > Max = S(1) 2 For i = 2 to n n-1 If Max < S(i) 2 (< и S[i]) Max = S(i) 2 (= и S[i]) еnd if Next i Print (Max) < >

Данный алгоритм является количественно-параметрическим, поэтому для фиксированной размерности исходных данных необходимо проводить анализ для худшего, лучшего и среднего случая. Худший случай Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна: F(n)=2+1+3(n-1)+(n-1)(2+2)=7n-4= Θ(n) Лучший случай Минимальное количество переприсваиваний максимума - если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна: F(n)=2+1+3(n-1)+(n-1)(2)=5n-2= Θ(n)

Средний случай Элементарное усреднение Fc(n) =(Fх(n)+ Fл(n) )/2= 6n-3= Θ(n). ?

1.6.2 Переход к временным оценкам

Сравнение двух алгоритмов по их функции трудоемкости вносит некоторую ошибку в получаемые результаты. Основные причины этой ошибки: различная частотная встречаемость элементарных операций;θ различие во времени их выполнения на реальном процессоре.θ Таким образом, возникает задача перехода от функции трудоемкости к оценке времени работы алгоритма на конкретном процессоре.

Дано: F(A) - трудоёмкость алгоритма требуется определить время работы программной реализации алгоритма – T(A).

---

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

Различные времена выполнения реальных машинных команд; различие во времени выполнения однородных команд в зависимости от значений операндов и типов данных; неоднозначности компиляции исходного текста, обусловленные как самим компилятором, так и его настройками.

1.6.3 Конструирование алгоритма

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

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

Анализ и проверка правильности алгоритмов могут проводиться путем:

- проверки результатов выполнения на конкретных исходных данных,

- логического анализа конечных результатов относительно постановки задачи.

Совокупность контрольных исходных данных, служащих для проверки правильности алгоритма, называется алгоритмическим тестом.

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

Анализ алгоритма включает в себя анализ:

- логической структуры,

- выполнения,

- правильности.

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

Практическая часть

Задача 1. Даны x,y,z. Вычислить a, b если

Постановка задачи.

Входные данные –значения x, y, z, а также функции а и b

Выходные данные – значение функции a и bдля различных значений аргумента х,y,z

Цель реализации алгоритма: нахождение значенийa и b при заданных значениях x, y, z.

---

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

Словесное описание алгоритма.

Начало

1. Ввести x, y, z;
2. a:=y+(x/(y*y+(x*x/(y+(x*x*x/3)))));
3. b:=(1+sqr(sin(z/2)/cos(z/2)));
4. Вывод (a, b).

Конец

Текст программы приведен ниже

Program zadacha1;

Var

x, y, z:real;

a, b:real;

begin

writeln(‘vvedite x,y,z’);

readln(x,y,z);

a:=y+(x/(y*y+(x*x/(y+(x*x*x/3)))));

b:=(1+sqr(sin(z/2)/cos(z/2)));

writeln(‘a=’,a:7:3,’b=’,b:7:3);

end.

Задача 2. Даны действительные числа x, y. Определить принадлежит ли точка с координатами х и у заштрихованной части плоскости.

У1

-11х

-1

Постановка задачи.

Входные данные –значения x, y.

Выходные данные – нужно определить принадлежит ли точка с координатами х и у заштрихованной плоскости.

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

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

Словесное описание алгоритма.

Начало

1. Читаем с экранаx и y
2. Определяем положение заданной точки относительно первогоотрезка (1,0;0,1)

Положение определяем, считаяпроизведениевекторов проходящих через:

1-й вектор начальная – конечная точка отрезка,

2-й вектор начальная точка отрезка – заданная точка.

Произведение > 0 => точка лежит слева от отрезка,

Произведение < 0 => справа,

Произведение = 0 =>лежит на отрезке.

1. Аналогично считаем для оставшихся отрезков.
2. Если для все отрезков точка находится слева, значит она внутри области,

Если хоть для одного справа, значит вне области , ну и если лежит на отрезке, то на границе области.

1. Выводим ответ.

Конец

(Направление отрезков против часовой стрелки)

Текст программы приведен ниже

programzadacha2;

var

x,y,z: real;

function location(xlin1,ylin1,xlin2,ylin2: real): integer;

var

tmp: real;

begin

tmp := (xlin2-xlin1)*(y-ylin1) - (ylin2-ylin1)*(x-xlin1);

if tmp < 0 then location:= -1

else if tmp > 0 then location:= 1

else location:= 0;

end;

begin

repeat

write('x = ');

Readln(x);

write('y = ');

Readln(y);

if ((location(1,0,0,1)> 0) and (location(0,1,-1,0)>0) and (location(-1,0,0,-1)> 0) and (location(0,-1,1,0)>0))

then writeln('tochka prinadlegit oblasti')

else if ((location(1,0,0,1)< 0) or (location(0,1,-1,0)<0) or (location(-1,0,0,-1)< 0) or (location(0,-1,1,0)<0))

then writeln('tochka ne prinadlegit oblasti')

else writeln('tochka na granice oblasti');

---