Алгоритм,

Алгорифм, Ч точное предписание, к-рое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из нек-рой совокупности возможных для данного А. исходных данных) и направленный на получение полностью определяемого этим исходным данным результата. А. являются, напр., известные из начальной школы правила сложения, вычитания, умножения и деления столбиком; в этих А. возможными результатами служат натуральные числа, записанные в десятичной системе, а возможными исходными данными — упорядоченные пары таких чисел.  Вообще говоря, не предполагается, что результат будет обязательно получен: процесс применения А. к конкретному возможному исходному данному (т. е. алгоритмич. процесс, развертывающийся начиная с этого данного) может также оборваться безрезультатно (в этом случае говорят, что произошла безрезультатная остановка) или не закончиться вовсе. В случае, если процесс заканчивается (соответственно не заканчивается) получением результата, говорят, что А. применим (соответственно неприменим) к рассматриваемому возможному исходному данному. (Можно построить такой А. , для к-рого не существует А., распознающего по произвольному возможному для исходному данному, применим к нему или нет; такой А. можно, в частности, построить так, чтобы совокупностью его возможных исходных данных служил натуральный ряд.) Понятие А. занимает одно из центральных мест в современной математике, прежде всего вычислительной. Так, проблема численного решения уравнений данного типа заключается в отыскании А., к-рый всякую пару, составленную из произвольного уравнения этого типа и произвольного положительного рационального числа , перерабатывает в число (или набор чисел), отличающееся (отличающихся) от корня (корней) этого уравнения меньше, чем на . Усовершенствование цифровых вычислительных машин дает возможность реализовать на них все более сложные А. Однако встретившийся в описывающей понятие А. формулировке термин "вычислительный процесс" не следует понимать в узком смысле только цифровых вычислений: уже в школьном курсе алгебры говорят о буквенных вычислениях, да и в арифметич. вычислениях появляются отличные от цифр символы (скобки, знак равенства, знаки арифметич. действий). Целесообразно, таким образом, рассматривать А., оперирующие с произвольными символами и их комбинациями. Простейшим случаем такой комбинации является линейная последовательность символов, образующая слово, однако можно рассматривать и "нелинейные" комбинации — такие, как алгебраич. матрицы, знакосочетания в смысле Н. Бурбаки (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-м случае — проблемы перевода отдельных фраз. Ролью м. а. "Уточнения" понятия алгоритма. Понятие А. в его общем виде принадлежит к числу основных первоначальных понятий математики, не допускающих определения в терминах более простых понятий. Возможные уточнения понятия А. приводят, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в -том, что для каждого из указанных 7 параметров А. точно описывается нек-рый класс, в пределах к-рого этот параметр может меняться. Выбор таких классов и отличает одно уточнение от другого. Поскольку 7 параметров однозначно определяют нек-рый А., то выбор 7 классов изменения этих параметров определяет нек-рый класс А. Однако такой выбор может претендовать на название "уточнения", лишь если имеется убеждение, что для произвольного А., имеющего допускаемые данным выбором совокупности возможных исходных данных и возможных результатов, может быть указан равносильный ему А. из определенного данным выбором класса А. Это убеждение формулируется для каждого уточнения в виде основной гипотезы, к-рая — при современном уровне наших представлений — не может быть предметом математич-доказательства. Первые уточнения описанного типа предложили в 1936 Э. Л. Пост (Е. L. Post, см. [5]) и А. М. Тьюринг (А. М. Turing, см. [3], [4]), их конструкции во многом предвосхитили идеи, заложенные в основу современных цифровых вычислительных машин. Известны также уточнения, сформулированные А. А. Марковым (см. [10], [11], Нормальный алгорифм).и А. Н. Колмогоровым (см. [ 12], [ 13]; последний предложил трактовать конструктивные объекты как топологич. комплексы определенного вида, что дало возможность уточнить свойство "локальности" преобразования). Для каждого из предложенных уточнений соответствующая основная гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит и то, что, как можно доказать, все предложенные уточнения в нек-ром естественном смысле эквивалентны друг другу. В качестве примера рассмотрим уточнение, предложенное А. М. Тьюрингом. В своем оригинальном виде это уточнение заключалось в описании нек-рой абстрактной вычислительной машины, состоящей из: 1) бесконечной ленты, разбитой на следующие друг за другом в линейном порядке ячейки, причем в каждой ячейке записан к.-л. символ из так наз. "внешнего алфавита" машины, и 2) каретки, находящейся в каждый момент в нек-ром "состоянии" (из заданного конечного списка состояний), способной перемещаться вдоль ленты и изменять содержимое ячеек; А. вычислений на такой машине ("тыорингов А.") задается в виде программы, управляющей действиями каретки. Более подробное и точное описание см. в статье Тьюринга машина;здесь приводится модернизированное изложение конструкции Тьюринга в терминах, указанных выше 7 параметров. Чтобы задать тыорингов А., надо указать: а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Дбуквой и выделенными в Чбуквами и , б) набор пар вида , где , а Тесть один из трех знаков — , 0, +, причем предполагается, что в этом наборе (наз. программой) нет 2 пар с одинаковыми первыми членами. Параметры А. задаются так: возможными исходными данными и возможными результатами служат слова в Б, а возможными промежуточными результатами — слова в алфавите содержащие не более одной буквы из Ч. Правило начала: исходное слово Рпереводится в слово . Правило окончания: заключительным является промежуточный результат, содержащий со. Правило извлечения результата: результатом объявляется цепочка всех тех букв заключительного промежуточного результата, к-рая идет вслед за w и предшествует первой букве, не принадлежащей Б. Правило непосредственной переработки, переводящее , состоит в следующем. Приписываем к Аслева и справа букву ; затем в образовавшемся слове часть вида , где , , заменяем на слово Qпо следующему правилу: в программе ищется пара с первым членом ; пусть второй член этой пары есть ; если есть -, то ; если Тесть 0, то ; если Тесть +, то Возникающее после этой замены слово и есть А'. Лит. см. [3]-[5], [10]-[13] при СТ. Алгоритмов теория, В. А. Успенский.