Большая Советская Энциклопедия (АЛ) - БСЭ БСЭ

  Лит.: Народы Америки, т. 1, М., 1959.

  Ю. П. Аверкиева.

Алгоритм

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

  Понятие А. занимает одно из центральных мест в современной математике, прежде всего вычислительной. Так, проблема численного решения уравнений данного типа сводится к отысканию А., который всякую пару, составленную из произвольного уравнения этого типа и произвольного рационального числа e, перерабатывает в число (или набор чисел) меньше, чем на e, отличающееся (отличающихся) от корня (корней) этого уравнения. Усовершенствование вычислительных машин даёт возможность реализовать на них всё более сложные А. Однако встретившийся в описывающей понятие А. формулировке термин «вычислительный процесс» не следует понимать в узком смысле только цифровых вычислений. Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, да и в арифметических вычислениях появляются отличные от цифр символы: скобки, знак равенства, знаки арифметических действий. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно таким широким пониманием пользуются при описании понятия А. Так, можно говорить об А. перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и др. примерах алгоритмического описания процессов управления; именно поэтому понятие А. является одним из центральных понятий кибернетики. Вообще, исходными данными и результатами А. могут служить самые разнообразные конструктивные объекты; например, результатами т. н. распознающих А. служат слова «да» и «нет».

  Пример алгоритма . В. и. д. и возможными результатами пусть служат всевозможные конечные последовательности букв a и b («слова в алфавите {a, b}»). Условимся называть переход от слова Х к слову Y «допустимым» в следующих двух случаях (ниже Р обозначает произвольное слово): 1) Х имеет вид аР, а Y имеет вид Pb; 2) X имеет вид baP, а Y имеет вид Paba. Формулируется предписание : «взяв какое-либо слово в качестве исходного, делай допустимые переходы до тех пор пока не получится слово вида aaP; тогда остановись, слово Р и есть результат». Это предписание образует А., который обозначим через Â. Возьмем в качестве исходного данного слово babaa. После одного перехода получим baaaba, после второго aabaaba. В силу предписания мы должны остановиться, результат есть baaba. Возьмём в качестве исходного данного слово baaba. Получим последовательно abaaba, baabab, abababa, bababab, babababa, ... Можно доказать, что процесс никогда не кончится (т. е. никогда не возникает слово, начинающееся с aa и для каждого из получающихся слов можно будет совершить допустимый переход). Возьмём теперь в качестве исходного данного слово abaab. Получим baabb, abbaba, bbabab. Далее мы не можем совершить допустимый переход, и в то же время нет сигнала остановки. Произошла т.н. «безрезультативная остановка». Итак, Â применим к слову babaa и неприменим к словам baaba и abaab.

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

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

  Само слово «А.» происходит от algorithmi, являющегося, в свою очередь, латинской транслитерацией арабского имени хорезмийского математика 9 в. аль-Хорезми . В средневековой Европе А. называется десятичная позиционная система счисления и искусство счёта в ней, поскольку именно благодаря латинскому переводу (12 в.) трактата аль-Хорезми Европа познакомилась с позиционной системой.

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