Интуитивное понятие алгоритма.

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

а) подготовиться к уроку по математике;

б) приготовить раствор для проявления фотопленки;

в) избавиться от лишнего веса.

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

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

Для разъяснения интуитивного понятия алгоритма рассмотрим несколько примеров.

В качестве первого примера рассмотрим один из самых древних и самых известных математических алгоритмов - алгоритм нахождения наибольшего общего делителя двух натуральных чисел. Этот алгоритм еще в III веке до нашей эры изложил (в геометрической форме) греческий ученый Евклид в теоретическом трактате по математике "Начала". Поэтому он носит название алгоритма Евклида. Алгоритм Евклида обсуждается практически в каждой книге по программированию.

Пример 1.1. Вычисление наибольшего общего делителя двух натуральных чисел m и n.

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

Алгоритм Евклида

1. Поместить в участок памяти с именем x число m; перейти к выполнению пункта 2.

2. Поместить в участок памяти с именем y число n; перейти к выполнению пункта 3.

З. Если выполняется условие , то перейти к выполнению пункта 5, иначе перейти к выполнению пункта 4.

4. Поместить в участок памяти с именем НОД значение из блока памяти x; перейти к выполнению пункта 8.

5. Если выполняется условие x > y, то перейти к выполнению пункта 6, иначе перейти к выполнению пункта 7;

6. Поместить в участок памяти с именем x значение выражения x - y; перейти к выполнению пункта 3.

7. Поместить в участок памяти с именем y значение выражения y - x; перейти к выполнению пункта 3.

8. Закончить работу.

Внимательное рассмотрение алгоритма Евклида показывает, что запись алгоритма распадается на отдельные команды. Каждая команда снабжена номером и представляет собой указание исполнителю выполнить некоторое законченное действие. Исполнение алгоритма начинается с команды, имеющей номер 1. Далее команды выполняются в соответствии с указаниями, сопровождающими каждую команду алгоритма.

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

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

Такая форма записи алгоритма часто используется во всякого рода инструкциях, правилах, рецептах и т.п. Она хороша в случае, когда алгоритм небольшой и когда для описания алгоритма отводится мало места. Недостатком такого оформления является его малая наглядность.

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

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

Рассмотренные примеры показывают, что выполнение алгоритма разбивается на последовательность законченных действий-шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего действия. Это свойство алгоритма называется дискретностью. Таким образом, дискретность означает, что алгоритм состоит из конечного числа описаний шагов и эти шаги выполняются в дискретном времени, то есть любые два последних шага разделены при исполнении конечным, ненулевым отрезком времени. Можно считать, что шаги выполняются в моменты времени t₀, t₁,…, а между этими моментами ничего не происходит.

Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.

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

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

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

- Да пойми же, гайками прикрепляется рельса к шпалам!

- Это мы понимаем...

А.Чехов "Злоумышленник"

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

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

Отмеченное свойство называется свойством определенности, или детерминированности.

Замечание. Часто под свойством детерминированности алгоритма понимается одновременное выполнение свойств точности и понятности.

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

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

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

Проиллюстрируем свойства алгоритма на примере алгоритма Евклида.

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

Вопросы для контроля:

1. Интуитивное понятие алгоритма.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: