Понятие алгоритма
Лекция 7.1. Алгоритмизация
ДЕ 7. Алгоритмизация и программирование. Языки программирования высокого уровня
Слово «алгоритм» происходит от «algorithmi» – латинской формы описания имени великого узбекского математика IХ в. аль - Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами.
Понятие алгоритма – одно из фундаментальных понятий информатики.
Алгоритм – это формальное описание способа решения задачи, путем разбиения ее на конечную по времени последовательность действий (элементарных операций). Под словом «формальное» подразумевается, что описание должно быть абсолютно полным и учитывать все возможные ситуации, которые могут встретиться по ходу решения. Под элементарной операцией понимается действие, которое по определенным критериям (например, очевидности) не имеет смысла детализировать.
|
|
Алгоритм на выбранном языке программирования записывается с помощью команд описания данных, вычисления значений и управления последовательностью выполнения программ.
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создан, мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритма ряд обязательных требований, суть которых вытекает из приведенного выше неформального толкования понятия алгоритма. Сформулируем эти требования в виде перечня свойств, которым должны удовлетворять алгоритмы.
Дискретность (разрывность) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий. Говорят: «Делится на шаги».
Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е., рассмотрев значения дискриминанта, алгоритм находит либо два различных корня, либо два равных, либо делает вывод о том, что действительных корней нет.
Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен, и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. В алгоритмах недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге.
|
|
Результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное число шагов. Вывод о том, что решения не существует – тоже результат. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.