История развития алгоритмов

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

Термин «алгоритм» происходит от algorithmi — латинского написания имени аль-Хорезми (великого математика IX в.), который сформулировал правила выполнения арифметических действий¹.

Одно из первых интуитивных понятий алгоритма можно сформулировать следующим образом: «Алгоритм — это строгая система правил, которая определяет последовательность действий над некоторыми объектами и после конечного числа шагов приводит к достижению поставленной цели»^[1][2]. Другими словами, набор правил считается алгоритмом, если разные исполнители, не знающие сущности задачи, будут при строгом соблюдении этого набора правил действовать одинаково и достигнут одного и того же результата.

Английский математик А. Тьюринг сформулировал одно из первых формальных определений алгоритма^[3]. В 1936 г. он описал схему абстрактной машины и то, что она умеет делать, назвал алгоритмом. На основе многочисленных экспериментов на своих машинах Тьюринг подтвердил широкие возможности его конструкции и выдвинул тезис: «Всякий алгоритм может быть реализован соответствующей машиной Тьюринга». Данный тезис является формальным определением алгоритма и главной гипотезой теории алгоритмов по Тьюрингу.

В конце 1940;х гг. советский математик А. А. Марков предложил следующую основную гипотезу теории алгоритмов: «Всякий алгоритм нормализуем»^[4]. По Маркову определение алгоритма сформулировано таким образом: «Алгоритм — эго точное предписание, которое задает вычислительный процесс, начинающийся с произвольного (но выбранного из фиксированной для данного алгоритма совокупности) исходного данного и направленный на получение полностью определяемого этим исходным данным результата»^[5].

Более общее уточнение понятия алгоритма предложил советский ученый А. Н. Колмогоров^[6]. В его формулировке алгоритма содержатся два важных момента: итеративность алгоритмического процесса и локальность каждого отдельного шага.

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

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

• [1] Могилев А. В., Пак II. И., Хеннер Е. К. Информатика.
• [2] Успенский В. Л., Семенов А. Л. Теория алгоритмов: основные открытия и приложения.М.: Наука, 1987.
• [3] Марков А. А., Нагорный II. М. Теория алгорифмов. 2-е изд. М.: ФАЗИС, 1996.
• [4] Там же.
• [5] D Там же.
• [6] Успенский В. Л., Семенов А. Л. Теория алгоритмов: основные открытия и приложения.