Математическая энциклопедия

Алгоритм

Алгоритм
АЛГОРИТМ,

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

 

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

Понятие А. занимает одно из центральных мест в современной математике, прежде всего вычислительной. Так, проблема численного решения уравнений данного типа заключается в отыскании А., к-рый всякую пару, составленную из произвольного уравнения этого типа и произвольного положительного рационального числа , перерабатывает в число (или набор чисел), отличающееся (отличающихся) от корня (корней) этого уравнения меньше, чем на . Усовершенствование цифровых вычислительных машин дает возможность реализовать на них все более сложные А. Однако встретившийся в описывающей понятие А. формулировке термин "вычислительный процесс" не следует понимать в узком смысле только цифровых вычислений: уже в школьном курсе алгебры говорят о буквенных вычислениях, да и в арифметич. вычислениях появляются отличные от цифр символы (скобки, знак равенства, знаки арифметич. действий). Целесообразно, таким образом, рассматривать А., оперирующие с произвольными символами и их комбинациями. Простейшим случаем такой комбинации является линейная последовательность символов, образующая слово, однако можно рассматривать и "нелинейные" комбинации - такие, как алгебраич. матрицы, знакосочетания в смысле Н. Бурбаки (N. Bour-baki), фразы того или иного языка с расставленными стрелками синтаксич. управления и, вообще, размеченные тем или иным способом графы. Наиболее общее интуитивное понимание состоит в том, что исходными данными и результатами А. могут служить самые разнообразные конструктивные объекты. Это открывает возможность широкого применения понятия А. Можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмич. описания процессов управления; именно поэтому понятие А. является одним из центральных понятий кибернетики.

Пример алгоритма. Пусть возможными исходными данными и возможными результатами служат всевозможные слова в алфавите . Условимся называть переход от слова Xк слову Y"допустимым" в следующих двух случаях (ниже Робозначает произвольное слово): 1) X имеет вид аР, а Y имеет вид Рb;2) Xимеет вид bаР, a Y имеет вид Раbа. Формулируется предписание: "взяв к.-л. слово в качестве исходного, делай допустимые переходы до тех пор, пока не получится слово вида ааР;тогда остановись, слово Ри есть результат". Это предписание образует А., к-рый обозначим . Возьмем в качестве исходного данного слово bаbаа. После одного перехода получим bаааbа, после второго ааbааbа. В силу предписания мы должны остановиться, результат есть bааbа. Возьмем в качестве исходного данного слово bааbа. Получим последовательно аbааbа, bааbаb, аbаbаbа, bаbаbаb, bаbаbаbа,.... Можно доказать, что процесс никогда не кончится (т. е. никогда не возникает слово, начинающееся с аа, и для каждого из получающихся слов можно будет совершить допустимый переход). Возьмем теперь в качестве исходного данного слово аbааb. Получим bааbb, аbbаbа, bbаbаb. Далее мы не можем совершить допустимый переход, и в то же время нет сигнала остановки. Произошла безрезультатная остановка. Итак, применим к слову bаbаа и неприменим к словам bааbа и аbааb.

Значение алгоритмов. А. встречаются в науке на каждом шагу: умение решать задачу "в общем виде" всегда означает, по существу, владение нек-рым А. Говоря, напр., об умении человека складывать числа, имеют в виду не то, что он для любых чисел рано или поздно сумеет найти их сумму, а то, что он владеет нек-рым единообразным приемом сложения, применимым к любым двум конкретным записям чисел, т. е., иными словами, А. сложения (примером такого А. и является известное правило сложения чисел столбиком). Понятие задачи "в общем виде" уточняется при помощи понятия массовая алгоритмическая проблема (м. а. п.). М. а. п. задается серией отдельных, единичных проблем и состоит в требовании найти единый А. их решения (когда такого А. не существует, говорят, что рассматриваемая м. а. п. неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода суть м. а. п.: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз. Ролью м. а. <п. и определяется как значение, так и сфера приложения понятия А.: напр., а алгебре возникают м. а. п. проверки алгебраич. равенств различных типов, в математич. логике - м. а. п. распознавания выводимости предложений из заданных аксиом и т. п. (для математич. логики понятие А. существенно еще и потому, что на него опирается центральное для математич. логики понятие исчисления, служащее обобщением и уточнением интуитивных понятий "вывода", и "доказательства"). Установление неразрешимости к.-л. м. а. п. (напр., проблемы распознавания истинности или доказуемости для к.-л. логнко-математич. языка) является важным познавательным актом, показывающим, что для решения конкретных единичных проблем данной серии принципиально необходимы специфические для каждой отдельной проблемы методы.

Содержательные явления, к-рые легли в основу образования понятия "А.", издавна занимали важное место в науке. С древнейших времен многие задачи математики заключались в поисках тех или иных конструктивных методов. Эти поиски, особенно усилившиеся в связи с созданием удобной символики, а также осмысления принципиального отсутствия искомых методов в ряде случаев (задача о квадратуре круга и подобные ей) - все это было мощным фактором развития научных знаний. Осознание невозможности решить задачу прямым вычислением привело к созданию в 19 в. теоретико-множественной концепции. Лишь после периода бурного развития этой концепции (в рамках к-рой вопрос о конструктивных методах в современном их понимании вообще не возникает) оказалось возможным в сер. 20 в. вновь вернуться к вопросам конструктивности, но уже на новом уровне, обогащенном выкристаллизовавшимся понятием А. Это понятие легло в основу конструктивного направления в математике.

Само слово "А." происходит от algoritmi, являющегося, в свою очередь, латинской транслитерацией арабского имени хорезмийского математика 9 в. аль-Хорезми.

В средневековой Европе А. назывались десятичная позиционная система счисления и искусство счета в ней, поскольку именно благодаря латинскому переводу (12 в.) трактата аль-Хорезми Европа познакомилась с позиционной системой.

Строение алгоритмического процесса. Алгоритмич. процесс есть процесс последовательного преобразования конструктивных объектов (к. о.), происходящий дискретными "шагами"; каждый шаг состоит в смене одного к. о. другим. Так, при применении А. к слову baaba возникают последовательно baaba, abaaba, bааbаb и т. д. А при применении, скажем, А. вычитания столбиком к паре (307, 49) последовательно возникнут такие к. о.:


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

Таким образом, наряду с совокупностями возможных исходных данных и возможных результатов для каждого А. имеется еще совокупность возможных промежуточных результатов, представляющая собой ту рабочую среду, в к-рой развивается алгорит-мич. процесс. Для А. все три совокупности совпадают, а для А. вычитания столбиком - нет: возможными исходными данными служат пары чисел, возможными результатами - числа (все в десятичной системе), а возможные промежуточные результаты суть "трехэтажные" записи вида где - запись числа в десятичной системе, - такая же запись или пустое слово, а р - запись числа в десятичной системе с допущением точек над нек-рыми цифрами. Как правило, для данного А. можно выделить 7 характеризующих его (не независимых) параметров: 1) совокупность возможных исходных данных, 2) совокупность возможных результатов, 3) совокупность возможных промежуточных результатов, 4) правило начала, 5) правило непосредственной переработки, 6) правило окончания, 7) правило извлечения результата.