Cтраница 2
Кроме проблемы эквивалентности, представляют интерес и другие алгоритмические проблемы. [16]
В работе [50] выяснена тесная связь между классическими алгоритмическими проблемами и понятием аппроксимируемости алгебры относительно соответствующих предикатов. После этого уже довольно просто решаются проблемы равенства и вхождения для нильпотентных групп, а также некоторые другие алгоритмические вопросы. Надо заметить, что развитие и применение идей, содержащихся в [50], и в настоящее время еще далеки от своего исчерпания. [17]
Полициклические группы-наиболее широкий класс групп, в котором все классические алгоритмические проблемы нашли положительное решение. [18]
Как уже отмечалось в § 1 1, среди алгоритмических проблем особое место занимают те, в которых требуется найти алгоритм для вычисления всех значений некоторой функции. [19]
Этот исторический промежуток - знаменуется трогим заданием математических алгоритмов и постановкой ряда Кфупных алгоритмических проблем, которые не поддавались решеник традиционными методами. В их числе знаменитые геометрические задачи древних греков - трисекция угла и квадратура круга, проблема разрешимости уравнений в радикалах, приведшая к созданию деории Галуа, а также ряд алгоритмически нерешаемых задач, На этом этапе произошло осознание понятия алгоритма как отдельного объекта изучения, что, в конечном итоге, привело к созданию строгой математической теории алгоритмов. [20]
В настоящей главе рассмотрены основы алгебраической теории полугрупп, включая теорию многообразий и алгоритмические проблемы, а также комбинаторные приложения и представления полугрупп преобразованиями. [21]
Свободные разрешимые группы являются ФА -, ФАС-группами, а потому в них положительно решаются алгоритмические проблемы равенства и сопряженности. Факторы нижнего центрального ряда свободной разрешимой группы являются свободными абелевыми группами. [22]
И наконец, хотя определение обычной диаграммы Вороного на случай пространства произвольной размерности очевидно, ее построение связано со значительными алгоритмическими проблемами. [23]
Если мы фиксируем некрое п и ограничиваемся рассмотрением проблемы вхождения в М только для первых га натуральных чисел, то мы получаем ограниченную алгоритмическую проблему. Величина К ( М, п) интуитивно выражает количество информации, к-рую надо иметь, чтобы можно было решить данную ограниченную проблему. В частности, множество М рекурсивно тогда и только тогда, когда К ( М, га) ограничено сверху нск-рой константой. [24]
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ - одно из основных понятий алгоритмов теории и ее приложений, Возникло в связи с тем, что неразрешимость ( и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, а путем сведения к исследуемой проблеме такой алгоритмич. Так, неразрешимость проблемы гомотонии путей в полиэдре доказывается путем сведения к ней проблемы равенства слов в соответствующей фундаментальной группе. [25]
Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами; к ней относятся, в частности, проблемы построения алгоритма, обладающего теми или иными свойствами - алгоритмические проблемы. [26]
Можно было привести еще много примеров алгоритмически не-р азрешимых проблем, с ними мы еще встретимся при изучении теории грамматик алгоритмических языков. К типу алгоритмических проблем относится и теорема Геделя о неполноте арифметической логики. Прежде всего уточним основные понятия, используемые в теореме Геделя. [27]
В заключительной части работы рассматриваются многообразия ассоциативных алгебр с тождеством лиевой нильпотентности фиксированного индекса. Внимание сосредоточено на разрешимости алгоритмических проблем в этих многообразиях. Показано, что алгоритмически разрешим вопрос о выполнимости тождества лиевой нильпотентности фиксированного индекса в конечно порожденной алгебре, в которой разрешима проблема равенства слов. Также доказано, что в многообразии лиево нильпотентных алгебр проблема равенства слов решается с помощью алгоритма, использующего технику базисов Гребнера. [28]
Соответственно двум возможным альтернативам, алгоритмическую проблему называют разрешимой или неразрешимой. Алгоритмические проблемы рассматриваются преимущественно для полугрупп, заданных тем или иным эффективным способом; наиболее типично их рассмотрение для полугрупп, заданных определяющими соотношениями. [29]
С другой стороны, примерно в то же время, А. Пуанкаре поставил проблему, которую обычно называют алгоритмической проблемой Пуанкаре. [30]