5.1. Определение алгоритма

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

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

п1. {Нахождение остатка} r:=m mod n.

п2. {Замена} m:=n; n:=r.

п3. {Остановка?} Если n0, то переход к п1.

п4. {Остановка процесса} m - искомое число.

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

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

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

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

В алгоритме Евклида конструктивными объектами являются пары чисел. Смена конструктивных объектов, например, для чисел m=10, n =4 выглядит так: (10, 4)  (4, 2)  (2, 0).

Как правило, для заданного алгоритма можно выделить семь независимых параметров: 1) совокупность исходных данных, 2) совокупность промежуточных результатов, 3) совокупность результатов, 4) правило начала, 5) правило непосредственной переработки, 6) правило окончания, 7) правило извлечения результата. Для алгоритма Евклида эти параметры таковы.

1. I = {(m, n)| m  n}.

2. P = {(m, n)| m  n}.

3. R = {m|m > 0}.

4. Ввести пару чисел (m, n) таких, что m  n.

5. (m, n)  (n, m mod n).

6. Если в паре (m, n) n = 0, то останов.

7. Результатом является первое число пары (m, 0). Вывод m на устройство вывода.

Основные свойства алгоритма

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

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

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

Дискретность - вычислительный процесс, предопределенный алгоритмом, можно расчленить на отдельные этапы и элементарные операции.