АЛГОРИТМ
алгорифм,
одно из основных понятий (категорий) математики, не обладающих формальным
определением в терминах более простых понятий, а абстрагируемых непосредственно
из опыта. А. являются, напр., известные из начальной школы правила сложения,
вычитания, умножения и деления столбиком. Вообще, под А. понимается всякое
точное предписание, к-рое задаёт вычислительный процесс (наз. в этом случае
алгоритмически м), начинающийся с произвольного исходного данного (из нек-рой
совокупности возможных для данного А. исходных данных) и направленный на
получение полностью определяемого этим исходным данным результата; напр.,
в упомянутых А. арифметич. действий возможными результатами могут быть
натуральные числа, записанные в десятичной системе, а возможными исходными
данными - упорядоченные пары таких чисел. В содержание предписания, т.
о., помимо инструкции по развёртыванию алгорит-мич. процесса, должно входить
также: 1) указание совокупности возможных исходных данных (в. и. д.) и
2) правило, по к-рому процесс признаётся закончившимся ввиду достижения
результата.
Не предполагается,
что результат будет обязательно получен: процесс применения А. к конкретному
в. и. д. (т. е. алго-ритмич. процесс, развёртывающийся начиная с этого
данного) может также оборваться безрезультатно или не закончиться вовсе.
В случае, если процесс заканчивается (соответственно не заканчивается)
получением результата, говорят, что А. применим (соответственно неприменим)
к рассматриваемому в. и. д. (Можно построить такой А.
,
для к-рого не существует А., распознающего по произвольному возможному
для Я исходному данному, применим к нему Я или нет; такой А.
можно,
в частности, построить так, чтобы совокупностью его в. и. д. служил натуральный
ряд.)
Понятие А.
занимает одно из центральных мест в совр. математике, прежде всего вычислительной.
Так, проблема численного решения уравнений данного типа сводится к отысканию
А., к-рый всякую пару, составленную из произвольного уравнения этого типа
и произвольного рационального числа
, перерабатывает
в число (или набор чисел) меньше, чем на
,
отличающееся (отличающихся) от корня (корней) этого уравнения. Усовершенствование
вычислит, машин даёт возможность реализовать на них всё более сложные А.
Однако встретившийся в описывающей понятие А. формулировке термин "вычислительный
процесс" не следует понимать в узком смысле только цифровых вычислений.
Так, уже в школьном курсе алгебры говорят о буквенных вычислениях, да и
в арифметич. вычислениях появляются отличные от цифр символы: скобки, знак
равенства, знаки арифметич. действий. Можно пойти дальше и рассматривать
вычисления с произвольными символами и их комбинациями; именно таким широким
пониманием пользуются при описании понятия А. Так, можно говорить об А.
перевода с одного языка на другой, об А. работы поездного диспетчера (перерабатывающего
информацию о движении поездов в приказы) и др. примерах алгоритмич. описания
процессов управления; именно поэтому понятие А. является одним из центральных
понятий кибернетики. Вообще, исходными данными и результатами А. могут
служить самые разнообразные конструктивные объекты; напр., результатами
т. н. распознающих А. служат слова "да" и "нет".
Пример алгоритма.
В. и. д. и возможными результатами пусть служат всевозможные конечные (в
т. ч. пустая) последовательности букв а и b ("слова в алфавите {а, b}").
Условимся называть переход от слова X к слову Y "допустимым" в следующих
двух случаях (ниже Р обозначает произвольное слово);
1) X имеет
вид аР, а Y имеет вид Pb;
2) X имеет
вид baP, а Y имеет вид Раbа. Формулируется предписание: "взяв к.-л. слово
в качестве исходного, делай допустимые переходы до тех пор, пока не получится
слово вида ааР; тогда остановись, слово Р и есть результат". Это предписание
образует А., к-рый обозначим через С. Возьмём в качестве исходного данного
слово babaa. После одного перехода получим bаааЬа, после второго aabaaba.
В силу предписания мы должны остановиться, результат есть baaba. Возьмём
в качестве исходного данного слово baaba. Получим последовательно аbааbа,
baobab, abababa, bababab, babababa, ... Можно доказать, что процесс никогда
не кончится (т. е. никогда не возникает слово, начинающееся с аа, и для
каждого из получающихся слов можно будет совершить допустимый переход).
Возьмём теперь в качестве исходного дан-
ного слово
abaab. Получим baabb, abbaba, bbabab. Далее мы не можем совершить допустимый
переход, и в то же время нет сигнала остановки. Произошла т. н. "безрезультативная
остановка". Итак, С применим к слову babaa и неприменим к словам baaba
и abaab.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я