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

Свойства алгоритмов

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

Алгоритм и его свойства.

Лекция 13. ОСНОВНЫЕ ПОНЯТИЯ АЛГОРИТМА.

Вопросы:

1. Алгоритм и его свойства.

2. Формы записи алгоритма.

3. Базовые алгоритмические структуры.

Литература:

1. [1], c. 187-195

2. [4], c. 127, 299-301.

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

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

Более строгое определение алгоритма дано в [1].

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

Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации.

К основным свойствам алгоритмов относятся следующие свойства.

Понятность. Имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

Дискретность (прерывность, раздельность). Алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов.

Определенность. Каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола.

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

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

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

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

Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

Третье правило – алгоритм должен быть дискретным. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, должно быть конечным.

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

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

Дата добавления: 2014-01-04