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

Понятие «алгоритм» является одним из основных понятий информатики и математики. Название алгоритм происходит от Algorithmi – латинской формы написания имени великого учёного средневекового Востока Мухаммеда ибн Мусса Аль Хорезми. Его годы жизни приблизительно с 783 по 850 гг. Он сформулировал правила выполнения арифметических действий над многозначными числами.

Что же будем понимать под алгоритмом?

Задача 1. Даны два натуральных числа[1] a и b. Напишите алгоритм нахождения НОД(a, b) – наибольшего общего делителя a и b.

Решение. a и b – входные данные задачи. По существу, мы имеем не одну задачу, а бесконечное множество однотипных задач, столько, сколько существует различных пар натуральных чисел (a; b). Возникает вопрос: существует ли общий метод, позволяющий для любой частной задачи, получаемой подстановкой вместо a и b конкретной пары натуральных чисел, за конечное число шагов определить НОД(a, b).

Для решения задачи необходимо иметь последовательность каких-то действий над входными данными и результатами предыдущих действий, если такие уже имеются, позволяющих найти НОД(a, b). Желательно, чтобы набор этих действий был невелик и в то же время достаточен для нахождения наибольшего общего делителя для любых a, bÎN. Тогда должно существовать нечто такое, обозначим его «А», что после каждого действия оно должно указывать, что делать дальше: либо окончить процесс и указать результат, либо перейти к выполнению следующего определенного действия.

Вот это «А» и принято называть алгоритмом.

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

Алгоритмом решения поставленной задачи для выбранного исполнителя является, например, алгоритм Евклида.

Шаг 1. Сравни два числа a и b. Обозначь большее число через r, а меньшее через r₁. Найди остаток r₂ от деления r на r₁. Сравни r₂ с нулем, если r₂ равно нулю, то НОД(a, b) присвой значение r₁ и иди на шаг 3, иначе иди на шаг 2.

Шаг 2. Переменной r присвой значение r₁, а r₁ – значение r₂. Найди остаток от деления r на r₁ и обозначь его r₂. Сравни r₂ с нулем, если r₂ равно нулю, то НОД(a, b) присвой значение r₁ и иди на шаг 3, иначе иди на шаг 2.

Шаг 3. Процесс вычисления НОД(a, b) закончи.

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

Под алгоритмом будем понимать понятное и точное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.[2]