АЛГОРИТМ

АЛГОРИТМ (алгорифм) — точное предписание о выполнении в определенном порядке некоторой системы операций, позволяющее решать совокупность задач определенного класса.

А. приводит от исходных данных к искомому результату через конечное число шагов (действий); при этом данные варьируются в известных границах.

Много различных А. рассматривается в алгебре и теории чисел, а также в других математических дисциплинах. Простейшими алгоритмами являются: правила, по которым выполняются арифметические действия, А. Евклида (см. Евклида алгоритм), А. извлечения квадратного корня и А. для вычисления определителей n-го порядка, правило Саррюса (см. Саррюса правило) — А. для вычисления определителей 3-го порядка, А. для вычисления ранга матриц, А. для определения числа действительных корней алгебраического уравнения—правило Штурма (см. Штурма правило) и т. д.

Слово А. возникло в результате искажения имени великого узбекского математика IX в. Хорезми (по-арабски — аль-Хорезми, что означает «из Хорезма», или латинизированное Algorithmi). Хорезми были написаны основополагающие труды по арифметике и алгебре, которые переведены с арабского языка на латинский в XII в.; по ним в Европе познакомились с индийской десятичной позиционной системой счисления (часто называемой арабской) и основными правилами алгебры.

Долгое время понятие А. в математике не имело точного определения как ввиду трудности уточнения объема этого понятия, так и ввиду того, что оно понадобилось лишь тогда, когда пришли к открытию отсутствия А. для решения некоторых задач. Точные определения А. были даны лишь в XX в. несколькими математиками. Эти определения, различные по форме, впоследствии оказались эквивалентными.

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

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