Свойства алгоритма. Лекция 5.1. Алгоритмизация

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

Лекция 5.1. Алгоритмизация

ДЕ5. Алгоритмизация и программирование. Языки программирования высокого уровня

Слово «алгоритм» происходит от «algorithmi» – латинской формы описания имени великого узбекского математика IХ в. аль - Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами.

Понятие алгоритма – одно из фундаментальных понятий информатики.

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-06