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

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

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

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

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

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

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

Следует иметь в виду, что это - не определение в математическом смысле слова, но довольно подробное описание понятия алгоритма, раскрывающее его сущность. Описание может быть другим. Так, в школьном учебнике по информатике [l] понятие алгоритма дается в следующей форме: «Под алгоритмом понимают понятное и точное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи».

Понятие алгоритма является одним из основных понятий современной математики и является объектом исследования специального раздела математики - теории алгоритмов.

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

Столетия эти правила были очень сложны и не удивительно поэтому, что производить вычисления с большими числами могли только люди с высшим образованием. Так, чтобы научиться арифметическому делению в средние века требовалось закончить университет. Да еще не всякий университет мог научить этой премудрости. Нужно было непременно ехать в Италию: тамошние математики добились большого искусства в делении. Если напомнить, что в те времена пользовались непозиционной (римской) системой счисления, станет ясно, почему деление миллионных чисел было доступно лишь бородатым мужам, посвятившим этому всю свою жизнь.

С введением позиционной системы счисления все изменилось. В IX веке узбекский математик Мухаммед ибн Муса ал-Хорезми («ал-Хорезми» означает «Хорезмиец») описал правила выполнения четырех арифметических действий в десятичной системе счисления. Новые правила были значительно проще и сейчас ими владеют уже школьники младших классов. Поразительная простота указанных правил стимулировала их повсеместное распространение. Эти правила были изложены Мухаммедом в книге по математике, изданной в 825 году, где, кроме того, приводились многочисленные рецепты решения различных задач.

По латинским переложениям арифметического трактата ал-Хорезми средневековая Европа знакомилась с индийской позиционной системой счисления и с искусством счета в этой системе. При переводе имя автора переделали в Алгоритми. Ссылки на рецепты решений из книги Мухаммеда европейские авторы начинали со слов: «Так говорил Алгоритми ...». С течением времени сами рецепты для решения математических задач стали называть алгоритмами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1.2. Умножение натуральных чисел столбиком [2].

1. Записать множимое.

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

3. Провести черту под множителем (под ней будут записываться частные суммы).

4. Взять очередную цифру множителя, начиная с единиц.

5. Если очередная цифра множителя равна нулю, пропустить ее и перейти к пункту 7.

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

7. Если очередная цифра не была последней, перейти к пункту 4.

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

Пример 1.3. Инструкция по приготовлению проявителя. Содержимое большого пакета растворить в 300 мл. воды при температуре I8-20^○ C; затем добавить содержимое малого пакета. Объем раствора довести до 500 мл. Раствор профильтровать.

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

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