4. Алгоритм и его свойства

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

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

Слово алгоритм происходит от algorihmi – латинской формы написания имени великого математика IX века Аль-Хорезми, который сформулировал правила выполнения арифметических действий. Благодаря латинскому переводу трактата Аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления. В средневековой Европе алгоритмом называлась десятичная позиционная система счисления. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.

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

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

Алгоритм – конечная система правил, которая определяет последовательность действий над некоторыми объектами, и после конечного числа шагов приводит к достижению поставленной цели.

4.2. Понятие исполнителя алгоритма

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

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

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

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

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

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

1. Понятность алгоритма для исполнителя. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и выполнить, а какие – нет. Очевидно, что составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ.

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

3. Детерминированность (определенность, точность). Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Это означает, что одна и та же команда, будучи выполнена разными исполнителями, после исполнения каждым из них должна давать одинаковый результат. Запись алгоритма должна быть четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных составителем алгоритма. Алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. Итак, определенность алгоритма означает, что алгоритм должен предусматривать определенный порядок выполнения действий, и состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств.

4. Результативность. При точном выполнении всех предписаний алгоритма исполнитель должен получить определенный результат за конечное число шагов. Вывод о том, что решения не существует – тоже результат. Следовательно, результативность означает возможность получения результата после выполнения конечного количества операций.

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

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

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

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

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