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

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

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

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс», Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальность.

Дискретность (разрывность — противоположно непрерывности) — это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

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

Определенность (детерминированность, точность) — свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: „Прямо пойдешь — голову потеряешь, направо пойдешь — жену найдешь, налево пойдешь — разбогатеешь“. Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.

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

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

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

• 1. совокупность возможных исходных данных;
• 2. совокупность возможных промежуточных результатов;
• 3. совокупность результатов;
• 4. правило начала;
• 5. правило непосредственной переработки;
• 6. правило окончания;
• 7. правило извлечения результата.

Пример. Алгоритм вычисления корней квадратного уравнения.

.

Исходные данные — коэффициенты уравнения: а — при второй степени неизвестного; b — при первой степени неизвестного; с — при нулевой степени неизвестного.

Искомый результат — значения корней уравнения х₁ и х₂.

Предписание:

• 1. Вычислить значение дискриминанта по формуле .
• 2. Если, то вычислить значения корней уравнения по формулам:

3. Если, то уравнение не имеет корней.

Приведенное предписание обладает всеми свойствами алгоритма:

• · дискретностью — предписание разбито на этапы (шаги выполнения);
• · однозначностью — однозначно указано как обозначаются коэффициенты, дискриминант, корни, приведены формулы для вычисления дискриминанта и корней уравнения;
• · результативностью — при выполнении предписания получается результат — значения корней уравнения или заключение, что уравнение не имеет решения;
• · массовостью — в предписании составлено для общего случая (указаны не конкретные значения коэффициентов).