Современное состояние алгебры 2 страница

АЛГЕБРАИЧЕСКОЕ ВЫРАЖЕНИЕ, выражение, составленное из букв и цифр, соединённых знаками действий сложения, вычитания, умножения, деления, возведения в целую степень и извлечения корня (показатели степени и корня должны быть постоянными числами). А. в. наз. рациональным относительно нек-рых букв, в него входящих, если оно не содержит их под знаком извлечения корня, напр. [ris] рационально относительно а, b и с. А. в. наз. целым относительно нек-рых букв, если оно не содержит деления на выражения, содержащие эти буквы, напр. За/с + Ьс² - Зас/4 является целым относительно а и b. Если нек-рые из букв (или все) считать переменными, то А. в. есть алгебраическая функция.

АЛГЕБРАИЧЕСКОЕ ДОПОЛНЕНИЕ, см. в ст. Определитель.

АЛГЕБРАИЧЕСКОЕ УРАВНЕНИЕ, уравнение, получающееся при приравнивании двух алгебраических выражений. А. у. с одним неизвестным наз. д р о 6 н ы м, если неизвестное входит в знаменатель, и иррациональным, если неизвестное входит под знаком радикала. Всякое А. у. может быть преобразовано без потери корней к виду a₀x" + a_tx" ~^l + +... + а„ = 0. О решении таких ур-ний см. Алгебра и Численное решение уравнений. Д. К. Фаддеев.

АЛГЕБРАИЧЕСКОЕ ЧИСЛО, число а, удовлетворяющее алгебр. уравнению

[ris]где n< =1,

[ris]- целые (рациональные) числа. Число а наз. целым А. ч., если a₁ = 1. Если многочлен[ris]

[ris]не является произведением двух др. многочленов положит, степени с рациональными коэфф., то число n наз. степенью А. ч. а. Простейшие А.ч.- корни двучленного ур-ния xⁿ= a, где а-рациональное число. Напр., А. ч. будут рациональные числа, числа[ris] целыми А. ч. будут целые числа, числа

[ris]С понятием А. ч. тесно связаны два больших направления в теории чисел. 1) Арифметика А. ч. (алгебр.теория чисед), созданная Э. Куммером в сер. 19 в., изучает свойства А. ч. Целые А. ч. обладают рядом свойств, аналогичных свойствам целых рациональных чисел, однако теорема об единственности разложения числа на простые множители не имеет места в теории целых А. ч. Для сохранения единственности разложения Куммер ввёл в рассмотрение т. н. " идеальные" числа (см. Идеал). 2) Теория приближения А. ч. изучает степень приближения А. ч. рациональными числами или алгебр, же числами. Первым результатом в этом направлении была теорема Ж. Лиувилля, показывающая, что А. ч. " плохо" приближаются рациональными числами, точнее: если а - А. ч. степени п, то при любых целых рациональных р и q имеет место неравенство[ris], где С= =[ris]-постоянная, не зависящая от р и q; отсюда следует, что легко построить произвольное количество неалгебраических - трансцендентных чисел.

Лит.: Гекке Э., Лекции по теории алгебраических чисел, пер. с нем., М.- Л., 1940; Гельфонд А. О., Трансцендентные и алгебраические числа, М., 1952; Боревич 3. И., Шафаревич И. Р., Теория чисел, М., 1964. А. А. Карациба.

АЛГЕБРЫ ОСНОВНАЯ ТЕОРЕМА, название теоремы о существовании комплексных корней алгебр. уравнения a_axⁿ + a_ix^n-1+... + а_п = 0 с комплексными коэффициентами. См. Алгебра.

АЛГОЛ, сокращённое назв. ряда языков программирования. Образовано из начальных букв англ, слов algorithmic (алгоритмический) и language (язык). Разработан группой учёных разных стран в 1958-60. Окончат, вид языка, принятый на междунар. конференции в Париже (янв. 1960), получил назв. " Алгол-60" (в отличие от первоначального вида, названного " Алгол-58").

Осн. символами А. являются десятичные цифры, строчные и заглавные лат. буквы, знаки препинания, знаки матем. и логич. операций, прочие спец. знаки и нек-рые англ, слова (в частности, begin и end). Из осн. символов в А. по определённым правилам образуются конструкции - числа и выражения (арифметич., логич. и др.), описания, примечания и операторы, к-рые, в свою очередь, в сочетании с осн. символами образуют более сложные операторы и т. д. Алгоритм, заданный на А., наз. алгол-программой. С помощью спец. программы он преобразуется в программу на языке конкретной цифровой вычислит, машины.

Лит.: Алгоритмический язык АЛГОЛ-60, пер. с англ., М., 1965; Лавров С. С., Универсальный язык программирования (АЛГОЛ-60), 2 изд., М., 1967.

АЛГОЛЬ, В - Персея, затменная переменная звезда, переменность к-рой открыта в 1669. Блеск А. изменяется от 2, 2 до 3, 5 визуальной звёздной величины с периодом 2, 867 суток. Расстояние от Солнца - 36 парсек. Переменные звёзды с кривой изменения блеска, как у А., составляют класс звёзд типа Алголя.

АЛГОНКИНСКИЕ ЯЗЫКИ, одна из основных семей языков североамериканских индейцев. В результате истребления племён А. я. сохранились лишь в немногих местах в США и Канаде, гл. обр. в р-не Великих озёр и южнее. Распадаются на 5 осн. групп: языки т. н. " черноногих" индейцев; чейенн; арапахо; центральная и восточная группы; калифорнийская группа. Наиболее обширны центр, н вост. группы, к к-рым относятся языки собственно алгонкинский, оджибве, оттава (в р-не оз. Верхнего и Гурон), кри (на Лабрадоре), делаварский (в Пенсильвании и в штатах Нью-Йорк и Нью-Джерси), фоке (долина Миссисипи), а также ныне исчезнувшие языки могикан, массачусет-ский и др. Языки т. н. " черноногих" индейцев (блэкфут) распространены в Канаде, у подножия Скалистых гор и в сев. части Монтаны; шейен - в ю.-в. части Миннесоты и с.-в. части Юж. Дакоты; арапахо - в вост. части Сев. Дакоты и в юж. части Монтаны; калифорнийская группа (Калифорния) представлена двумя языками - вийот и юрок. В грамматич. отношении А. я. характеризуются ярко выраженной инкорпорацией (см. Инкорпорирующие языки). В А. я. элементы, соответствующие второстепенным членам предложения, зависящие от глагольного сказуемого, входят в состав последнего как морфы, в результате чего одна словоформа соответствует целому предложению.

Лит.: Boas Fr.. Handbook of American Indian languages, pt 1, Wash., 1911; Pilling J. C., Bibliography of the Algonquian languages, Wash., 1891.

АЛГОНКИНЫ, группа родств. но языку (см. Алгонкинские языки) индейских племён, древнейших насельников Сев. Америки, охотников, рыболовов и ранних земледельцев, живших в прошлом на большом пространстве от Атлантич. побережья до Скалистых гор. Территориально различаются 4 группы А.: сев.-восточная (кри, монтанье, наскапи, мик-маки и др.); приатлантическая (абенаки, наррагансеты, массачусеты, поухатаны и др.), почти полностью уничтоженная на первых же этапах колонизации материка европейцами; центральная (могиканы, делавары, Майами, иллинойсы, отта-вы, оджибве, шауни, собств. алгонкины, меномини и др.), оставившая о себе память в топонимике; западная (" черноно-гие", чейенны, арапахо, ацина). Остатки алгонкинских племён разбросаны по резервациям США (100 тыс. чел.) и Канады (75 тыс. чел.; 1961). К А.в языковом отношении близки племена Тихоокеанского побережья Сев. Америки селиши (числ. в США 12 тыс. чел., в Канаде 15 тыс. чел.) и вакаши (в Канаде 6 тыс. чел.).

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

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

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

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

Пример алгоритма. В. и. д. и возможными результатами пусть служат всевозможные конечные (в т. ч. пустая) последовательности букв а и 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.

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

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

особого конструктивного направления в математике.

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

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

[ris]

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

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

суть " трёхэтажные" записи вида[ris], где

q - есть запись числа в десятичной системе, r - такая запись или пустое слово, ар - запись числа в десятичной системе с допущением точек над нек-рыми цифрами. Работа А. начинается подготовительным шагом, на к-ром возможное исходное данное преобразуется в начальный член ряда сменяющих друг друга промежуточных результатов; это преобразование происходит на основе специального, входящего в состав рассматриваемого А. " правила начала". Это правило для[ris]состоит в применении тождественного преобразования, а для А. вычитания - в замене пары[ris]

на запись -[ris], Затем применяется " правило непосредственной переработки", осуществляющее последоват. преобразования каждого возникающего промежуточного результата в следующий. Эти преобразования происходят до тех пор, пока нек-рое испытание, к-рому подвергаются все промежуточные результаты по мере их возникновения, не покажет, что данный промежуточный результат является заключительным; это испытание производится на основе спец. " правила окончания". Напр., для С правило окончания состоит в проверке, не начинается ли промежуточный результат на ая. (Если ни для какого из возникающих промежуточных результатов правило окончания не даёт сигнала остановки, то либо к каждому из возникающих промежуточных результатов применимо правило непосредственной переработки, и алгоритмич. процесс продолжается неограниченно, либо же к нек-рому промежуточному результату правило непосредств. переработки оказывается неприменимым, и процесс оканчивается безрезультатно.) Наконец, из заключительного промежуточного результата - также на основе спец. правила - извлекается окончательный результат; для С это извлечение состоит в отбрасывании первых двух букв а, а для А. вычитания - в отбрасывании всего, кроме самой нижней строчки цифр. (Во многих важных случаях правило начала и правило извлечения результата задают тождественные преобразования и потому отдельно не формулируются.) Т. о., для каждого А. можно выделить 7 характеризующих его (не независимых!) параметров: 1) совокупность возможных исходных данных, 2) совокупность возможных результатов, 3) совокупность промежуточных результатов, 4) правило начала, 5) правило непосредств. переработки, 6) правило окончания, 7) правило извлечения результата.

" Уточнения" понятия А. Возможны дальнейшие " уточнения" понятия А.„ приводящие, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из указанных 7 параметров А.точно описывается нек-рый класс, в пределах к-рого этот параметр может меняться. Выбор этих классов и отличает одно уточнение от другого. Во многих уточнениях все классы, кроме двух - класса совокупностей промежуточных результатов и класса правил непосредств. переработки, - выбираются единичными, т. е. все параметры, кроме указанных двух, жёстко фиксируются. Поскольку 7 параметров однозначно определяют нек-рый А., то выбор 7 классов изменения этих параметров определяет нек-рый класс А. Однако такой выбор может претендовать на название " уточнения", лишь если имеется убеждение, что для произвольного А., имеющего допускаемые данным выбором совокупности возможных исходных данных и возможных результатов, может быть указан равносильный ему А. из определённого данным выбором класса А. Это убеждение формулируется для каждого уточнения в виде основной гипотезы, к-рая - при современном уровне наших представлений - не может быть предметом матем. доказательства.

Первые уточнения описанного типа предложили в 1936 амер. математик Э. Л. Пост и англ, математик А. М. Тьюринг (см. Тьюринга машина). Известны также уточнения, сформулированные сов. математиками А. А. Марковым (см. Нормальный алгоритм) и А. Н. Колмогоровым (последний предложил трактовать конструктивные объекты как топологич. комплексы определённого вида, что дало возможность уточнить свойство " локальности" преобразования). Для каждого из предложенных уточнений соответствующая осн. гипотеза хорошо согласуется с практикой. В пользу этой гипотезы говорит и то, что, как можно доказать, все предложенные уточнения в нек-ром естественном смысле эквивалентны друг другу.

В качестве примера приведём (в модернизированном виде) уточнение, предложенное Тьюрингом. Чтобы задать тьюрингов А., надо указать; а) попарно непересекающиеся алфавиты Б, Д, Ч с выделенной в Д буквой [ris] и выделенными в Ч буквами[ris]) набор пар вида[ris], где[ris] а Т есть один из знаков -, 0, +, причём предполагается, что в этом наборе (наз. программой) нет 2 пар с одинаковыми первыми членами. Параметры А. задаются так; возможными исходными данными и возможными результатами служат слова в Б, а промежуточными результатами - слова в [ris], содержащие не более одной буквы из Ч. Правило начала: исходное слово Р переводится в слово [ris]. Правило окончания; заключительным является промежуточный результат, содержащий w. Правило извлечения результата: результатом объявляется цепочка всех тех букв заключительного промежуточного результата, которая идёт вслед за со и предшествует первой букве, не принадлежащей Б. Правило непосредств. переработки, переводящее А в А', состоит в следующем. Приписываем к А слева и справа букву [ris]; затем в образовавшемся слове часть вида [ris] где[ris] заменяем на слово [ris]по следующему правилу: в программе ищется пара с первым членом [ris] пусть второй член этой пары есть nTq; если Т есть ~, то [ris] если Т есть 0, то [ris] если Т есть +, то [ris] Возникающее после этой замены слово и есть А'.

См. также ст. Алгоритмов теория и лит. при этой статье. В. А. Успенский.

АЛГОРИТМИЗАЦИЯ ПРОЦЕССОВ, алгоритмическое описание процессов, описание процессов на языке матем. символов для получения алгоритма, отображающего элементарные акты процесса, их последовательность и взаимосвязь. Алгоритмы, получающиеся путём А. п., предназначаются, как правило, для реализации на ЭВМ.

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

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

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

Лит.: Глушков В. М., Синтез цифровых автоматов, М., 1962; Бусленко Н. П., Математическое моделирование производственных процессов на цифровых вычислительных машинах, М., 1964; Алгоритмизация производственных процессов [Доклады семинара], в. 1, К., 1966.

Н. П. Бусленко.

АЛГОРИТМОВ ТЕОРИЯ, раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия " алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма Л. Э. Я. Брауэра и Г. Вейля. Началом систематич. разработки А. т. можно считать 1936, когда А. Чёрч опубл. первое уточнение понятия вычислимой функции (предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клиии, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма. Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров.

Основные понятия А. т. Областью применимости алгоритма наз. совокупность тех объектов, к которым он применим. Про алгоритм Я говорят, что он: 1) " вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и Я перерабатывает всякий х из своей области применимости в f(x); 2) " разрешает множество А относительно множества X", коль скоро он применим ко всякому x из X и перерабатывает всякий x из [ris] з слово " да", а всякий x из Х\Л в слово " нет"; 3)" пе-речисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция наз. вычислимой, если существует вычисляющий её алгоритм. Множество наз. разрешимым относительно X, если существует разрешающий его относительно X алгоритм (см. Разрешимое множество). Множество наз. перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).

Детальный анализ понятия " алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у к-рого больщее множество служит множеством исходных данных, а меньшее - областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида < x, f(x)>. (IV) Подмножество А перечислимого множества X тогда и только тогда разрешимо относительно X, когда А и Х\А перечислимы. (V) Если Л и В перечислимы, то[ris] также перечислимы.

(VI) В каждом бесконечном перечислимом множестве X существует перечислимое подмножество с неперечислимым дополнением [ в силу (IV) это перечислимое подмножество будет неразрешимым относительно X].

(VII) Для каждого бесконечного перечислимого множества X существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма [ris] с неразрешимой областью применимости.

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

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