В информатику понятие алгоритма пришло из математики.

Приведенное определение не явля­ется определением в математическом смысле слова, поскольку в нем ис­пользованы другие неопределенные понятия — «система предписаний», «формальное выполнение» и др. Это описание понятия «алгоритм», рас­крывающее его сущность. (Рассмотри­те пример 1.1.) Описание можно уточ­нить, указав общие свойства, которые характерны для алгоритмов. К ним относятся: дискретность, детермини­рованность (определенность), понят­ность, результативность, конечность, массовость.Дискретность. Алгоритм разбивает­ся на отдельные действия (шаги). Вы­полнение очередного действия возмож­но только после завершения преды­дущего. При этом набор промежуточ­ных данных конечен и получается по определенным правилам из данных предыдущего действия. Команда яв­ляется специальным указанием для исполнителя, предписывающим ему произвести каждое отдельное действие. Команды, которые относят к системе команд исполнителя, называ­ют простыми; другие команды могут быть определены через простые.

Детерминированность. Если алго­ритм неоднократно применить к од­ним и тем же исходным данным, то каждый раз должны получаться одни и те же промежуточные результаты и один и тот же выходной результат. Данное свойство означает, что резуль­тат выполнения алгоритма опреде­ляется только входными данными и командами самого алгоритма и не за­висит от исполнителя алгоритма.

Понятность. Алгоритм не должен содержать команд, смысл которых ис­полнитель может воспринимать неод­нозначно. Запись алгоритма должна быть четкой, полной и понятной. У исполнителя не должно возникать не­обходимости в принятии каких-либо самостоятельных решений.

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

Конечность. Реализуемый по за­данному алгоритму процесс должен остановиться через конечное число шагов и выдать искомый результат. Это свойство тесно связано со свой­ством результативности.

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

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

Если разработанная последователь­ность действий не обладает хотя бы од­ним из перечисленных выше свойств, то она не может считаться алгорит­мом. Для понимания свойств алго­ритма рассмотрите примеры 1.2 и 1.3.

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

В рамках теории алгоритмов про­исходит анализ различных алгорит­мов решения задачи для выбора наи­более эффективного (оптимального). Разработка инструментов для анализа эффективности алгоритмов — одна из задач теории алгоритмов.

Любой алгоритм нужно проверять на правильность работы (пример 1.4).

Пример 1.1. Алгоритм «Решето Эра­тосфена» позволяет получить простые числа, не превосходящие N.

1. Выпишем подряд все натуральные числа от 2 до N.
2. Возьмем первое число 2 и зачер­кнем каждое второе число, начиная от­счет со следующего за двойкой числа.
3. Возьмем первое незачеркнутое число, которое больше 2 (число 3), и за­черкнем каждое третье число, начиная отсчет от числа, стоящего после 3 (учи­тывая и ранее зачеркнутые числа).
4. Продолжим действия до тех пор, пока первое незачеркнутое число не окажется больше N .
5. В результате незачеркнутыми ока­жутся все простые числа, не превос­ходящие N, и только они.

Решето Эратосфена

Необходимость построения формаль­ного определения алгоритма привела к появлению в 20—30-х гг. XX в. тео­рии алгоритмов. Для определения раз­личными математиками были предло­жены: •     машина Тьюринга; •     машина Поста; •     нормальный алгоритм Маркова. Существовали и другие определения алгоритма. Впоследствии было доказа­но, что все они эквивалентны. Алан Мэтисон Тьюринг (1912— 1954) — английский логик и матема­тик, оказавший существенное влияние на развитие информатики. Предложен­ная им в 1936 г. абстрактная вычисли­тельная Машина Тьюринга позволила формализовать понятие алгоритма, которое используется в теоретиче­ских и практических исследованиях. Алан Мэтисон Тьюринг Эмиль Леон Пост (1897—1954) — американский математик и логик. Из­вестен своими трудами по математиче­ской логике. Предложил абстрактную вычислительную машину — машину Поста (1936). Эмиль Леон Пост

Пример 1.2. Часто рецепты приго­товления каких-либо блюд называют алгоритмами. В данном случае нару­шается свойство детерминированности, поскольку при приготовлении блюда разными людьми результат может быть разным (например, он может зависеть от того, на какой плите готовили, или от качества продуктов). Кроме того, в рецептах часто бывают фразы «посо­лить по вкусу», «добавить 2—3 лож­ки сахара» и т. д., которые нарушают свойство понятности.

Пример 1.3. Задача может иметь ре­шение, но сформулировать алгоритм решения этой задачи не всегда удается. Если человеку предложить фотографии животных, то он достаточно быстро сможет разделить их на две группы: дикие и домашние. Однако сформули­ровать алгоритм, согласно которому он это сделал, на сегодняшний день не представляется возможным. Некоторые задачи классификации сегодня успеш­но решаются системами искусственного интеллекта с помощью методов машин­ного обучения. Однако характерной чертой таких методов является не пря­мое решение задачи, а процесс обуче­ния в ходе анализа множества решений сходных задач.

Пример 1.4. Способы проверки алго­ритма на правильность работы:

• математическое доказательство;
• использование специально подо­бранных тестов.