Понятие алгоритма и его свойства
«Алгоритм» является базовым основополагающим понятием информатики, а алгоритмизация и программирование – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, даётся множеством самых разнообразных определений – от «наивно-интуитивных» («алгоритм – это план решения задачи») до «строго формализованных» (нормальные алгоритмы Маркова). Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники.
Термин «алгоритм (алгорифм)» появился в Средние века, когда европейцы знакомились со способами выполнения арифметических действий в десятичной системе счисления по книге узбекского математика Абу Джафара Муххамада ибн Мусы аль-Хорезми (783–850 г.) «Арифметика индусскими цифрами», получившей широкую известность. Слово «алгоритм» есть результат европейского произношения слов «аль-Хорезми» («аль-Хорезми» – человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана).
Единого определения понятия алгоритма нет. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем алгоритмом стали называть точное предписание, определяющее порядок действий, обеспечивающий получение требуемого результата из исходных данных за конечное число шагов.
Алгоритм (по Д. Э. Кнуту) – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.
Алгоритм (по А. Н. Колмогорову) – это система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Алгоритм (по А. А. Маркову) – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством.
Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин «вычислительный процесс» распространяется и на обработку других видов информации, например, символьной, графической или звуковой.
Алгоритм должен обладать следующими свойствами:
− дискретностью;
− массовостью;
− определённостью;
− результативностью;
− формальностью.
Дискретность (разрывность, раздельность). Каждый алгоритм состоит из отдельных законченных действий, т.е. делится на шаги.
Массовость – применимость алгоритма ко всем задачам некоторого класса, различающимся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Определённость (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определён и не должен допускать произвола в толковании. Также строго должен быть определён порядок выполнения отдельных шагов. Благодаря этому свойству многократное выполнение алгоритма при одних и тех же исходных данных даёт один и тот же результат.
Результативность (конечность) – свойство, состоящее в том, что любой алгоритм должен приводить к правильному решению задачи за конечное (может быть очень большое) число шагов, либо подавать сигнал о том, что данный алгоритм неприменим для решения поставленной задачи.
Формальность – это свойство указывает на то, что любой исполнитель, незнакомый с содержанием алгоритма, но способный воспринимать и выполнять инструкции алгоритма, действуя формально, т.е. отвлекаясь от содержания поставленной задачи и лишь строго выполняя инструкции, получает необходимый результат. Думать о том, какие действия и в какой последовательности нужно выполнить, должен разработчик алгоритма, а исполнитель формально (не думая, механически) поочерёдно исполняет предложенные команды и получает необходимый результат.