Понятие алгоритма и его свойства

АЛГОРИТМЫ И ИХ РАЗРАБОТКА

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

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

Любой алгоритм имеет пять особенностей.

1) Конечность алгоритма (финитность). Означает, что алго­ритм всегда должен заканчиваться после конечного числа шагов.

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

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

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

2) Определенность алгоритма. Каждый шаг алгоритма должен быть точно определен, то есть действия, которые необходимо про­извести должны быть недвусмысленно определены в каждом воз­можном случае.

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

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

3) Наличие входных данных. Алгоритм имеет некоторое число
входных величин, заданных ему до начала работы.

Иногда это число может равняться нулю, однако это означает, что входные величины должны быть описаны как часть алгоритма. Например, алгоритм сложения числа 777 с числом 333. В этом слу­чае шаги 1 и 2 должны быть записаны так:

Шаг 1. Записать число 777.

Шаг 2. Под ним записать число 333

………

То есть, если даже входные величины отсутствуют, то какие-то величины будут описаны в самом алгоритме. В противном случае алгоритм не может быть выполнен.

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

5) Эффективность алгоритма. Алгоритм, который выполняет действие за меньшее число шагов признается более эффективным.

Это связано с тем. что любая программа, в основе которой ле­жит тот или иной алгоритм, должна выполняться на реальном вы­числительном устройстве. Поэтому большое значение имеет время выполнения программы, на которое влияет количество шагов алго­ритма. Кроме того, программа занимает определенный объем в па­мяти компьютера. Поэтому количество шагов косвенно влияет на еще один показатель эффективности - размер программы.

Дата добавления: 2014-12-16