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

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

Такими свойствами являются:

ü дискретность (прерывность, раздельность) - алгоритм дол­жен представлять процесс решения задачи как последователь­ное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняет­ся только после того, как закончилось исполнение предыду­щего;

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

ü результативность (конечность) - алгоритм должен приво­дить к решению задачи за конечное число шагов;

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

Обычно говорят не о свойствах алгорит­ма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.

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

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

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

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

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

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

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

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